|
Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения |
15.11.2016, 15:51
|
#1
|
Разработчик
Регистрация: 08.08.2011
Сообщений: 505
Написано 191 полезных сообщений (для 369 пользователей)
|
Быстрая работа со строками
Тк мой редактор работает с документами word, в нем очень много строковых переменных. Сейчас он делает свое дело примерно за 5 минут, что никуда не годится. 3 секунды - норм. Подозреваю, что самое быстрое - оперировать со строками в бинарном виде. Есть какие-то приемы для повышения быстродействия?
|
(Offline)
|
|
15.11.2016, 21:40
|
#2
|
[object Object]
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,361
Написано 2,473 полезных сообщений (для 6,856 пользователей)
|
Ответ: Быстрая работа со строками
Ничего не понятно. Что за редактор? Где ты это делаешь и что пытаешься получить?
"Обычные" способы работы со строками какие, если не "бинарные"?
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 4090 3070
AMD Ryzen 7 3800X 4.3Ghz; 64Gb; Nvidia 1070Ti
AMD Ryzen 7 1700X 3.4Ghz; 8Gb; AMD RX 570
AMD Athlon II 2.6Ghz; 8Gb; Nvidia GTX 750 Ti
|
(Offline)
|
|
15.11.2016, 22:03
|
#3
|
Разработчик
Регистрация: 08.08.2011
Сообщений: 505
Написано 191 полезных сообщений (для 369 пользователей)
|
Ответ: Быстрая работа со строками
В блице, допустим есть много-много операций типа Left, Right, Mid, Instr. Они все тяжелые. Если например строки преобразовать в банки и Left, Right и тд выделять как диапазон значений в банках, проводить там нужные операции, а в конце опять преобразовывать в строки. Это будет быстрее? Или есть какие-то другие способы быстро проделать нужные операции над строками.
|
(Offline)
|
|
15.11.2016, 23:41
|
#4
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: Быстрая работа со строками
Общо сказать сложно. Конкретную задачу, как правило, можно оптимизировать сведя работу к двиганию указателей, игре с chr(0), и многократному использованию памяти. Но это требует определённой сноровки и может сделать код менее гибким для последующих изменений (преждевременная оптимизация).
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
16.11.2016, 01:32
|
#5
|
Разработчик
Регистрация: 08.08.2011
Сообщений: 505
Написано 191 полезных сообщений (для 369 пользователей)
|
Ответ: Быстрая работа со строками
|
(Offline)
|
|
16.11.2016, 02:46
|
#6
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: Быстрая работа со строками
Ссылку сейчас смотреть некогда, просто уточню: у нас речь сейчас об алгоритмической (аналитической) или вычислительной (практической) оптимизации? Понятия связанные, но всё же.
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
16.11.2016, 03:08
|
#7
|
Разработчик
Регистрация: 08.08.2011
Сообщений: 505
Написано 191 полезных сообщений (для 369 пользователей)
|
Ответ: Быстрая работа со строками
И то и другое. Главное, чтоб работало быстрее. Нужна быстрая альтернатива функциям Left, Right, Instr.
Вот алгоритм Бойера-Мура на практике, де-факто самый быстрый алгоритм поиска подстроки в строке (Реализация на FreeBasic с вставкой Asm):
Быстрее в 10 раз обычного Instr.
#INCLUDE "crt.bi"
Function InStrZ naked( start As Integer, _
s1 As Zstring Ptr, _
s2 As Zstring Ptr ) As Integer
Asm
mov ecx, [esp+8] '' get pointer to s1
mov edx, [esp+12] '' get pointer to s2
movzx eax, Byte Ptr [ecx] '' get first char
test eax, eax '' test for null string
jz 0f '' return zero
movzx eax, Byte Ptr [edx] '' get first char
test eax, eax '' test for null string
jz 0f '' return zero
push ecx '' preserve ecx around call
''--------------------------------------------
'' The extra '+4' below is to correct for the
'' effect of the 'push ecx' above on ESP.
''--------------------------------------------
Add ecx, [esp+4+4] '' correct for start position
dec ecx '' correct for change in base
push edx '' push pointer to s2
push ecx '' push corrected pointer to s1
Call StrStr '' call CRT strstr function
Add esp, 8 '' remove parameters from stack
pop ecx '' recover ecx
test eax, eax '' test for substring not found
jz 0f '' return zero
Sub eax, ecx '' subtract address of s1 data
inc eax '' adjust return value to base 1
0:
ret 12 '' return and remove parameters from stack
End Asm
End Function
|
(Offline)
|
|
16.11.2016, 21:29
|
#8
|
Бывалый
Регистрация: 19.06.2008
Сообщений: 679
Написано 264 полезных сообщений (для 450 пользователей)
|
Ответ: Быстрая работа со строками
Ну дак блин ты сразу пиши что тебя надо то. Если бы ты сразу написал что тебе нужен быстрый поиск подстроки тебе бы сразу дали направление. Быстрого Left, right которые учитывают культуру не существует. Быстрый left, right без учета культуры это memcpy на строках где символ в памяти имеет фиксированную длину. + во многих случаях можно со строкой работать без её копирования (это дает прирост скорости).
__________________
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
17.11.2016, 16:12
|
#9
|
Разработчик
Регистрация: 08.08.2011
Сообщений: 505
Написано 191 полезных сообщений (для 369 пользователей)
|
Ответ: Быстрая работа со строками
Тут вот какая вещь по поводу Left, Right. В некоторых языках (в том числе в блице) скорость их выполнения мало зависит от длины строки, а в некоторых ЯП на коротких строках Left, Right работают быстрее, а на длинных медленнее.
Значит всё-таки можно короткие строки ускорить в десятки раз.
|
(Offline)
|
|
17.11.2016, 17:19
|
#10
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: Быстрая работа со строками
От длины строки и не должна зависеть. Зависит от длины подстроки образуемой.
Если ты в Си и исходная строка тебе более не нужна, то:
left - просто ставишь терминирующий байт после последнего в подстроке;
right - ставишь указатель на начало подстроки.
(ну и про очистку памяти потом не забыть надо)
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
17.11.2016, 18:33
|
#11
|
Разработчик
Регистрация: 08.08.2011
Сообщений: 505
Написано 191 полезных сообщений (для 369 пользователей)
|
Ответ: Быстрая работа со строками
Значит в PureBasic 5.5 какая-то функция Left интересная.
В общем, примерно вот такой код:
For i = 0 to 30000
s$ = s$ + str(i)
next
t = millisecs()
For i = 0 to 30000
sl$ = left(s$, i)
next
print millisecs() - t
Blitz3D: 44 мс
FreeBasic: 28 мс (Строки Си)
PureBasic: 3840 мс
Но если уменьшаем количество итераций в обоих циклах допустим до 300 (точно не помню до скольки), то результаты будут такие:
Blitz3D: 12 мс
FreeBasic: 9 мс
PureBasic: 2 мс
Может, конечно, ошибка какая-то, хз. Может в PB что-то заглючило от слишком длинной строки.
InStr тоже бывает двух типов:
- Зависит от длины строк (выигрывает на коротких строках) - Алгоритм Кнута — Морриса — Пратта
- Не зависит от длины - Алгоритм Ахо — Корасик
Может с Left такая же история?
|
(Offline)
|
|
17.11.2016, 19:00
|
#12
|
Зануда с интернетом
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений (для 20,935 пользователей)
|
Ответ: Быстрая работа со строками
Эксперимент поставлен некорректно.
С таким же успехом можно сделать вывод, что в PB работает сборщик мусора, включившийся после того, как ты понавыделял память - непонятно: на провис повлияло копирование длинных строк или общее количество копирований? Ну и ещё по мелочи ("прогрев", адекватность синонимов, статистическая устойчивость по моменту вызова и количеству вызовов, условия по загрузке цп, памяти)
Если ты исследуешь зависимость от одного параметра - так и варьируй его сперва в одном приложении и в широком диапазоне. А потом уже проделывай аналогичное в других языках.
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
17.11.2016, 19:03
|
#13
|
Разработчик
Регистрация: 08.08.2011
Сообщений: 505
Написано 191 полезных сообщений (для 369 пользователей)
|
Ответ: Быстрая работа со строками
В общем, всё сложно... Ладно, всё-равно я в принципе уверен, что FB быстрее работает(через библиотеку Си), по крайней мере во всех других тестах (вычисления, перевод чисел в строку) он работал процентов на 20 в среднем быстрее, его и буду юзать. Хотя вот FindString в PB работает даже быстрее раза в 1.5, чем InStr в FB.
Я просто не знал, что от длины строк не зависит, хотел с большой длиной потестить.
В итоге по сравнению с блицем прирост производительности со строками максимум в 1.5 - 2 раза, не такой уж он и медленный. Остается делать ставки на многопоточность, ну и сам код упрощать. Я то думал, что блиц тормоз, о чем тут на форуме твердят постоянно. Думал щас как возьму крутой транслятор бейсика в Си с последующей компиляцией на GCC и скорость в 100 раз быстрее будет.
Хрен там!
|
(Offline)
|
|
18.11.2016, 12:36
|
#14
|
Разработчик
Регистрация: 08.08.2011
Сообщений: 505
Написано 191 полезных сообщений (для 369 пользователей)
|
Ответ: Быстрая работа со строками
Щозанах Сегодня запускаю похожий код, результаты совсем другие:
Blitz3D - 1 мс
FreeBasic - 2140 мс
PureBasic - 19 мс
Импер, объясни поподробнее, как правильно писать код то? Или где об этом почитать? 3000 символов - не такая же большая строка, 1-2 страницы А4.
Код:
Blitz3D:
For i = 1 To 3000
d$ = d$ + "a"
Next
TimerStart = MilliSecs()
For i = 1 To 3000
k$ = Left(d$, i)
Next
tend = MilliSecs() - TimerStart
Print tend
WaitKey()
FreeBasic:
Dim d As String
Dim k As String
Dim tend As Double
For i As Integer = 0 To 3000
d = d + "a"
Next
Dim TimerStart As Double = Timer()
For i As Integer = 0 To 3000
k = Left(d, i)
Next
tend = Timer() - TimerStart
Print tend
Sleep
PureBasic:
st.s = ""
sl.s = ""
For i = 0 To 3000
st.s = st.s + "a"
Next
t = ElapsedMilliseconds()
For i = 0 To 3000
sl.s = Left(st.s, i)
Next
tend = ElapsedMilliseconds() - t
If OpenConsole()
PrintN(Str(tend))
Input()
EndIf
UPD: Перезагрузил комп, FB - 0,8 мс.
Последний раз редактировалось DarkInside, 18.11.2016 в 19:08.
|
(Offline)
|
|
21.11.2016, 17:36
|
#15
|
Unity/C# кодер
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений (для 5,323 пользователей)
|
Ответ: Быстрая работа со строками
Поставь задержку на секунду к примеру перед подсчетом для "прогрева".
|
(Offline)
|
|
Сообщение было полезно следующим пользователям:
|
|
Ваши права в разделе
|
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения
HTML код Выкл.
|
|
|
Часовой пояс GMT +4, время: 10:35.
|