Извините, ничего не найдено.

Не расстраивайся! Лучше выпей чайку!
Регистрация
Справка
Календарь

Вернуться   forum.boolean.name > Программирование в широком смысле слова > Алгоритмика

Алгоритмика Об алгоритмах вообще; методы, обсуждения способов решения

Ответ
 
Опции темы
Старый 15.11.2016, 15:51   #1
DarkInside
Разработчик
 
Аватар для DarkInside
 
Регистрация: 08.08.2011
Сообщений: 505
Написано 191 полезных сообщений
(для 369 пользователей)
Быстрая работа со строками

Тк мой редактор работает с документами word, в нем очень много строковых переменных. Сейчас он делает свое дело примерно за 5 минут, что никуда не годится. 3 секунды - норм. Подозреваю, что самое быстрое - оперировать со строками в бинарном виде. Есть какие-то приемы для повышения быстродействия?
(Offline)
 
Ответить с цитированием
Старый 15.11.2016, 21:40   #2
Randomize
[object Object]
 
Аватар для Randomize
 
Регистрация: 01.08.2008
Адрес: В России
Сообщений: 4,354
Написано 2,470 полезных сообщений
(для 6,850 пользователей)
Ответ: Быстрая работа со строками

Ничего не понятно. Что за редактор? Где ты это делаешь и что пытаешься получить?
"Обычные" способы работы со строками какие, если не "бинарные"?
__________________
Retry, Abort, Ignore? █
Intel Core i7-9700 4.70 Ghz; 64Gb; Nvidia RTX 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
DarkInside
Разработчик
 
Аватар для DarkInside
 
Регистрация: 08.08.2011
Сообщений: 505
Написано 191 полезных сообщений
(для 369 пользователей)
Ответ: Быстрая работа со строками

В блице, допустим есть много-много операций типа Left, Right, Mid, Instr. Они все тяжелые. Если например строки преобразовать в банки и Left, Right и тд выделять как диапазон значений в банках, проводить там нужные операции, а в конце опять преобразовывать в строки. Это будет быстрее? Или есть какие-то другие способы быстро проделать нужные операции над строками.
(Offline)
 
Ответить с цитированием
Старый 15.11.2016, 23:41   #4
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Ответ: Быстрая работа со строками

Общо сказать сложно. Конкретную задачу, как правило, можно оптимизировать сведя работу к двиганию указателей, игре с chr(0), и многократному использованию памяти. Но это требует определённой сноровки и может сделать код менее гибким для последующих изменений (преждевременная оптимизация).
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
DarkInside (15.11.2016)
Старый 16.11.2016, 01:32   #5
DarkInside
Разработчик
 
Аватар для DarkInside
 
Регистрация: 08.08.2011
Сообщений: 505
Написано 191 полезных сообщений
(для 369 пользователей)
Ответ: Быстрая работа со строками

Ну вот же: https://ru.wikipedia.org/wiki/%D0%90...83%D1%80%D0%B0
(Offline)
 
Ответить с цитированием
Старый 16.11.2016, 02:46   #6
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Ответ: Быстрая работа со строками

Ссылку сейчас смотреть некогда, просто уточню: у нас речь сейчас об алгоритмической (аналитической) или вычислительной (практической) оптимизации? Понятия связанные, но всё же.
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Старый 16.11.2016, 03:08   #7
DarkInside
Разработчик
 
Аватар для DarkInside
 
Регистрация: 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
h1dd3n
Бывалый
 
Аватар для h1dd3n
 
Регистрация: 19.06.2008
Сообщений: 679
Написано 264 полезных сообщений
(для 450 пользователей)
Ответ: Быстрая работа со строками

Ну дак блин ты сразу пиши что тебя надо то. Если бы ты сразу написал что тебе нужен быстрый поиск подстроки тебе бы сразу дали направление. Быстрого Left, right которые учитывают культуру не существует. Быстрый left, right без учета культуры это memcpy на строках где символ в памяти имеет фиксированную длину. + во многих случаях можно со строкой работать без её копирования (это дает прирост скорости).
__________________
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
DarkInside (17.11.2016)
Старый 17.11.2016, 16:12   #9
DarkInside
Разработчик
 
Аватар для DarkInside
 
Регистрация: 08.08.2011
Сообщений: 505
Написано 191 полезных сообщений
(для 369 пользователей)
Ответ: Быстрая работа со строками

Тут вот какая вещь по поводу Left, Right. В некоторых языках (в том числе в блице) скорость их выполнения мало зависит от длины строки, а в некоторых ЯП на коротких строках Left, Right работают быстрее, а на длинных медленнее.
Значит всё-таки можно короткие строки ускорить в десятки раз.
(Offline)
 
Ответить с цитированием
Старый 17.11.2016, 17:19   #10
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Ответ: Быстрая работа со строками

От длины строки и не должна зависеть. Зависит от длины подстроки образуемой.
Если ты в Си и исходная строка тебе более не нужна, то:
left - просто ставишь терминирующий байт после последнего в подстроке;
right - ставишь указатель на начало подстроки.
(ну и про очистку памяти потом не забыть надо)
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
DarkInside (17.11.2016)
Старый 17.11.2016, 18:33   #11
DarkInside
Разработчик
 
Аватар для DarkInside
 
Регистрация: 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
impersonalis
Зануда с интернетом
 
Аватар для impersonalis
 
Регистрация: 04.09.2005
Сообщений: 14,014
Написано 6,798 полезных сообщений
(для 20,935 пользователей)
Ответ: Быстрая работа со строками

Эксперимент поставлен некорректно.
С таким же успехом можно сделать вывод, что в PB работает сборщик мусора, включившийся после того, как ты понавыделял память - непонятно: на провис повлияло копирование длинных строк или общее количество копирований? Ну и ещё по мелочи ("прогрев", адекватность синонимов, статистическая устойчивость по моменту вызова и количеству вызовов, условия по загрузке цп, памяти)
Если ты исследуешь зависимость от одного параметра - так и варьируй его сперва в одном приложении и в широком диапазоне. А потом уже проделывай аналогичное в других языках.
__________________
http://nabatchikov.com
Мир нужно делать лучше и чище. Иначе, зачем мы живем? tormoz
А я растила сына на преданьях
о принцах, троллях, потайных свиданьях,
погонях, похищениях невест.
Да кто же знал, что сказка душу съест?
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
DarkInside (17.11.2016)
Старый 17.11.2016, 19:03   #13
DarkInside
Разработчик
 
Аватар для DarkInside
 
Регистрация: 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
DarkInside
Разработчик
 
Аватар для DarkInside
 
Регистрация: 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
pax
Unity/C# кодер
 
Аватар для pax
 
Регистрация: 03.10.2005
Адрес: Россия, Рязань
Сообщений: 7,568
Написано 3,006 полезных сообщений
(для 5,323 пользователей)
Ответ: Быстрая работа со строками

Поставь задержку на секунду к примеру перед подсчетом для "прогрева".
__________________
Blitz3d to Unity Wiki
(Offline)
 
Ответить с цитированием
Сообщение было полезно следующим пользователям:
DarkInside (21.11.2016)
Ответ


Опции темы

Ваши права в разделе
Вы не можете создавать темы
Вы не можете отвечать на сообщения
Вы не можете прикреплять файлы
Вы не можете редактировать сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Часовой пояс GMT +4, время: 19:14.


vBulletin® Version 3.6.5.
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Перевод: zCarot
Style crйe par Allan - vBulletin-Ressources.com