forum.boolean.name
Страница 1 из 2 1 2 >
Показывать 64 сообщений этой темы на одной странице

forum.boolean.name (http://forum.boolean.name/index.php)
-   Алгоритмика (http://forum.boolean.name/forumdisplay.php?f=21)
-   -   Быстрая работа со строками (http://forum.boolean.name/showthread.php?t=20481)

DarkInside 15.11.2016 15:51
Быстрая работа со строками
 
Тк мой редактор работает с документами word, в нем очень много строковых переменных. Сейчас он делает свое дело примерно за 5 минут, что никуда не годится. 3 секунды - норм. Подозреваю, что самое быстрое - оперировать со строками в бинарном виде. Есть какие-то приемы для повышения быстродействия?

Randomize 15.11.2016 21:40
Ответ: Быстрая работа со строками
 
Ничего не понятно. Что за редактор? Где ты это делаешь и что пытаешься получить?
"Обычные" способы работы со строками какие, если не "бинарные"?

DarkInside 15.11.2016 22:03
Ответ: Быстрая работа со строками
 
В блице, допустим есть много-много операций типа Left, Right, Mid, Instr. Они все тяжелые. Если например строки преобразовать в банки и Left, Right и тд выделять как диапазон значений в банках, проводить там нужные операции, а в конце опять преобразовывать в строки. Это будет быстрее? Или есть какие-то другие способы быстро проделать нужные операции над строками.

impersonalis 15.11.2016 23:41
Ответ: Быстрая работа со строками
 
Общо сказать сложно. Конкретную задачу, как правило, можно оптимизировать сведя работу к двиганию указателей, игре с chr(0), и многократному использованию памяти. Но это требует определённой сноровки и может сделать код менее гибким для последующих изменений (преждевременная оптимизация).

DarkInside 16.11.2016 01:32
Ответ: Быстрая работа со строками
 
Ну вот же: https://ru.wikipedia.org/wiki/%D0%90...83%D1%80%D0%B0

impersonalis 16.11.2016 02:46
Ответ: Быстрая работа со строками
 
Ссылку сейчас смотреть некогда, просто уточню: у нас речь сейчас об алгоритмической (аналитической) или вычислительной (практической) оптимизации? Понятия связанные, но всё же.

DarkInside 16.11.2016 03:08
Ответ: Быстрая работа со строками
 
И то и другое. Главное, чтоб работало быстрее. Нужна быстрая альтернатива функциям 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

h1dd3n 16.11.2016 21:29
Ответ: Быстрая работа со строками
 
Ну дак блин ты сразу пиши что тебя надо то. Если бы ты сразу написал что тебе нужен быстрый поиск подстроки тебе бы сразу дали направление. Быстрого Left, right которые учитывают культуру не существует. Быстрый left, right без учета культуры это memcpy на строках где символ в памяти имеет фиксированную длину. + во многих случаях можно со строкой работать без её копирования (это дает прирост скорости).

DarkInside 17.11.2016 16:12
Ответ: Быстрая работа со строками
 
Тут вот какая вещь по поводу Left, Right. В некоторых языках (в том числе в блице) скорость их выполнения мало зависит от длины строки, а в некоторых ЯП на коротких строках Left, Right работают быстрее, а на длинных медленнее.
Значит всё-таки можно короткие строки ускорить в десятки раз.

impersonalis 17.11.2016 17:19
Ответ: Быстрая работа со строками
 
От длины строки и не должна зависеть. Зависит от длины подстроки образуемой.
Если ты в Си и исходная строка тебе более не нужна, то:
left - просто ставишь терминирующий байт после последнего в подстроке;
right - ставишь указатель на начало подстроки.
(ну и про очистку памяти потом не забыть надо)

DarkInside 17.11.2016 18:33
Ответ: Быстрая работа со строками
 
Значит в 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 такая же история?

impersonalis 17.11.2016 19:00
Ответ: Быстрая работа со строками
 
Эксперимент поставлен некорректно.
С таким же успехом можно сделать вывод, что в PB работает сборщик мусора, включившийся после того, как ты понавыделял память - непонятно: на провис повлияло копирование длинных строк или общее количество копирований? Ну и ещё по мелочи ("прогрев", адекватность синонимов, статистическая устойчивость по моменту вызова и количеству вызовов, условия по загрузке цп, памяти) :mad:
Если ты исследуешь зависимость от одного параметра - так и варьируй его сперва в одном приложении и в широком диапазоне. А потом уже проделывай аналогичное в других языках.

DarkInside 17.11.2016 19:03
Ответ: Быстрая работа со строками
 
В общем, всё сложно... Ладно, всё-равно я в принципе уверен, что FB быстрее работает(через библиотеку Си), по крайней мере во всех других тестах (вычисления, перевод чисел в строку) он работал процентов на 20 в среднем быстрее, его и буду юзать. Хотя вот FindString в PB работает даже быстрее раза в 1.5, чем InStr в FB.

Я просто не знал, что от длины строк не зависит, хотел с большой длиной потестить.

В итоге по сравнению с блицем прирост производительности со строками максимум в 1.5 - 2 раза, не такой уж он и медленный. Остается делать ставки на многопоточность, ну и сам код упрощать. Я то думал, что блиц тормоз, о чем тут на форуме твердят постоянно. Думал щас как возьму крутой транслятор бейсика в Си с последующей компиляцией на GCC и скорость в 100 раз быстрее будет.
Хрен там! :-D

DarkInside 18.11.2016 12:36
Ответ: Быстрая работа со строками
 
Щозанах :4to: Сегодня запускаю похожий код, результаты совсем другие:

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 мс.

pax 21.11.2016 17:36
Ответ: Быстрая работа со строками
 
Поставь задержку на секунду к примеру перед подсчетом для "прогрева".


Часовой пояс GMT +4, время: 11:41.
Страница 1 из 2 1 2 >
Показывать 64 сообщений этой темы на одной странице

vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot