Pos - скорость.

← →
NAlexey (2004-02-18 15:06) [0]

Слышал высказывания что здесь что Pos работает достаточно медленно. Так ли это? Если да, то какая альтернатива?

← →
Игорь Шевченко (2004-02-18 15:10) [1]

> то какая альтернатива?

Не слушать здесь высказывания...

← →
Radionov Alexey (2004-02-18 15:14) [2]

>NAlexey © (18.02.04 15:06)
Нормально работает. Есть, конечно, реализации много быстрее для поиска подстроки в строке.

А какие именно высказывания? Может, контекст оных прояснит суть?

← →
NAlexey (2004-02-18 15:20) [3]

>Radionov Alexey © (18.02.04 15:14) [2]
>А какие именно высказывания? Может, контекст оных прояснит суть?
Вот как раз насчет того что для поиска подстроки в строке не пользоваться Pos.

← →
Radionov Alexey (2004-02-18 15:22) [4]

>NAlexey © (18.02.04 15:20) [3]
Тогда, если длина строки и подстроки "в разумных пределах", то про альтернативу Игорь уже сказал. :))

← →
NAlexey (2004-02-18 15:24) [5]

Понятно.

← →
Skier (2004-02-18 15:25) [6]

> то какая альтернатива?

альтернатива здесь http://www.podgoretsky.com/ddp.html
"Использование ассемблера в Дельфи, Гуйдо Гайбелс"

← →
Sha (2004-02-18 15:26) [7]

> Игорь Шевченко © (18.02.04 15:10) [1]
Я бы не был столь категоричным :)

← →
Anatoly Podgoretsky (2004-02-18 15:27) [8]

Есть группа новоестей в Борланд - BASM там как раз занимаются разработкой эквивалентов для RTL

← →
NAlexey (2004-02-18 15:27) [9]

>Skier © (18.02.04 15:25) [6]
К сожалению не имею свободного доступа ко всем сайтам, нельзяли привести здесь то что там написано.

>Sha © (18.02.04 15:26) [7]
Всмысле?

← →
Radionov Alexey (2004-02-18 15:28) [10]

>Skier © (18.02.04 15:25)
Сразу за ассемблер - наподобие "шапками закидаем" :))

Есть у Вирта, (или у Кнута, или у обоих - не помню :) ) описание алгоритма быстрого поиска подстроки в строке со временем работы
O(Length(Str)/Length(SubStr))

← →
Skier (2004-02-18 15:30) [11]

Если только невозможно иначе, то вы не должны использовать инструкции, которые оперируют словами, более правильно использовать те, которые работают с переменными типа двойное слово. Байтовый доступ еще может иногда использоваться, но остерегайтесь использовать операции со словами. Ниже пример использования 32-битного алгоритма для поиска символа в строке. Идея основана на генерации уникального значения, если и только если символ найден. Поскольку пример обрабатывает строку по четыре байта за раз, то это значительно быстрее, чем обработка по одному байту за раз, несмотря на дополнительное усложнение, поскольку требуется обрабатывать сразу четыре байта.

function ScanStrForChar(C: Char; S: String): Integer; register; asm push EBX push EDI push ESI test EDX,EDX jz @notfound mov ESI,[EDX-4] test ESI,ESI jz @notfound add ESI,EDX mov ah,al mov di,ax shl EDI,16 or di,ax mov EAX,EDX lea EDX,[EAX+3] @L1: cmp EAX,ESI ja @notfound mov EBX,[EAX] xor EBX,EDI add EAX,4 lea ECX,[EBX-$01010101] not EBX and ECX,EBX and ECX,$80808080 jz @L1 mov EBX,ECX shr EBX,16 test ECX,$8080 jnz @L2 mov ECX,EBX @L2: lea EBX,[EAX+2] jnz @L3 mov EAX,EBX @L3: shl cl,1 sbb EAX,EDX inc EAX @ending: pop ESI pop EDI pop EBX ret @notfound: xor EAX,EAX jmp @ending end;

В зависимости от длины обрабатываемых строк, функция может быть быстрее стандартной функции pos раза в два. Заметим, что должна прочитать от одного до трех символов в конце строки, но в текущей версии компилятор всегда размещает строки по модулю четыре, так что, это не приносит проблем, но нельзя гарантировать, что в следующих версиях это будет так же. Вы можете устранить эту проблему, путем расчета остатка символов в конце строки по модулю четыре и обработать остаток побайтно.

← →
Sha (2004-02-18 15:33) [12]

> NAlexey © (18.02.04 15:27) [9]
> Всмысле?

Можешь попробовать это :)

function Sha_Pos(const SubStr: string; const Str: string): integer; var len, lenSub: integer; ch: char; p, pSub, pStart, pEnd: pchar; label Ret, Ret0, Ret1, Next0, Next1; begin; p:=pointer(Str); pSub:=pointer(SubStr); //if need pure Pascal uncomment this paragraph //and comment out the next 3 paragraphs { len:=length(Str); lenSub:=length(SubStr); pEnd:=p+len; pStart:=p; pEnd:=pEnd-lenSub; if (len<=0) or (lenSub<=0) or (p>pEnd) then begin; Result:=0; exit; end; } if (p=nil) or (pSub=nil) then begin; Result:=0; exit; end; len:=pinteger(p-4)^; lenSub:=pinteger(pSub-4)^; if (len<lenSub) or (lenSub<=0) then begin; Result:=0; exit; end; pEnd:=p+len; pStart:=p; pEnd:=pEnd-lenSub; ch:=pSub[0]; if lenSub=1 then begin; repeat; if ch=p[0] then goto Ret0; if ch=p[1] then goto Ret1; p:=p+2; until p>pEnd; Result:=0; exit; end; repeat; if ch=p[0] then begin; len:=lensub; repeat; if psub[len-1]<>p[len-1] then goto Next0; if psub[len-2]<>p[len-2] then goto Next0; len:=len-2; until len<2; goto Ret0; Next0:end; if ch=p[1] then begin; len:=lensub; repeat; if psub[len-1]<>p[len] then goto Next1; if psub[len-2]<>p[len-1] then goto Next1; len:=len-2; until len<2; goto Ret1; Next1:end; p:=p+2; until p>pEnd; Result:=0; exit; Ret1: inc(pEnd); p:=p+2; if p<=pEnd then goto Ret; Result:=0; exit; Ret0: inc(p); Ret: Result:=p-pStart; end;

← →
NAlexey (2004-02-18 15:34) [13]

>Skier © (18.02.04 15:30) [11]
Спасибо.

Объясню почему меня интересует этот вопрос: При отрисовке экранного элемента, у меня интенсивно используется Pos, работает не достаточно быстро, хотелось бы попробывать оптимизировать. Начал по порядку. Вот и хотел бы выяснить добавит ли это выигрыша в скорости?

← →
zamkom (2004-02-18 15:36) [14]

NAlexey © (18.02.04 15:34) [13]
Есть алгоритм Бойера-Муна для поиска строки в тексте вот ссылка
http://www.rsdn.ru/article/alg/textsearch.xml

← →
NAlexey (2004-02-18 15:37) [15]

>Sha © (18.02.04 15:33) [12]
Спасибо, сравню три метода. Pos, от Skier и твой.

← →
Delirium (2004-02-18 15:37) [16]

Вообще варианты здесь ...
http://delphibase.endimus.com/?action=viewtopic&topic=strsearch

← →
NAlexey (2004-02-18 15:37) [17]

>zamkom © (18.02.04 15:36) [14]
К сожалению не имею свободного доступа ко всем сайтам, нельзяли привести здесь то что там написано.

← →
Skier (2004-02-18 15:38) [18]

>NAlexey © (18.02.04 15:37) [15]

> Спасибо, сравню три метода. Pos, от Skier и твой.

Не от Skier-а, а от Гуйдо Гайбелса !

← →
NAlexey (2004-02-18 15:41) [19]

>Skier © (18.02.04 15:38) [18]
О да!

← →
Sha (2004-02-18 15:49) [20]

> Skier ©

Кажется в твоей реализации есть небольшая неточность:
по-моему, алгоритм может найти символ за пределами строки.

← →
Skier (2004-02-18 15:53) [21]

>Sha © (18.02.04 15:49) [20]

>
> Кажется в твоей реализации есть небольшая неточность:

не в моей.

> по-моему, алгоритм может найти символ за пределами строки.

ты текст после кода читал ?

← →
Sha (2004-02-18 15:58) [22]

> Skier © (18.02.04 15:53) [21]

>> по-моему, алгоритм может найти символ за пределами строки.
> ты текст после кода читал ?

Читал. Там написано:
> В зависимости от длины обрабатываемых строк, функция может
> быть быстрее стандартной функции pos раза в два. Заметим, что
> должна прочитать от одного до трех символов в конце строки, но
> в текущей версии компилятор всегда размещает строки по модулю
> четыре, так что, это не приносит проблем, но нельзя
> гарантировать, что в следующих версиях это будет так же. Вы
> можете устранить эту проблему, путем расчета остатка символов
> в конце строки по модулю четыре и обработать остаток побайтно.

А теперь прочти еще раз мой текст:
по-моему, алгоритм может найти символ за пределами строки.
Причем здесь следующие версии?

← →
Игорь Шевченко (2004-02-18 16:01) [23]

Sha © (18.02.04 15:26)

Смотрим цитату автора:

> При отрисовке экранного элемента, у меня интенсивно используется
> Pos, работает не достаточно быстро, хотелось бы попробывать
> оптимизировать.

Овчинка выделки не стоит. IMHO.

← →
Sha (2004-02-18 16:04) [24]

← →
NAlexey (2004-02-18 16:06) [25]

Хм... Точно, все три варианта показали в моем случае одинаковые результаты. Такчто Игорь Шевченко сразу ответил на вопрос.

← →
Sha (2004-02-18 16:08) [26]

← →
NAlexey (2004-02-18 16:11) [27]

← →
Владислав (2004-02-18 16:56) [28]

Начиная с процессоров PentiumPro, алгоритм стандартного Pos (здесь я скажу за библиотеку Delphi 6, но думаю, что предыдущие версии такие же, а последующие - черт его знает) работает с большими потерями.
Он может выиграть только в том случае, если первое вхождение первого символа подстроки в строке оказалось удачным (то есть оказалось вхождением подстроки).
Алгоритм начинает просто проигрывать, если таких вхождений много, но это еще не первый символ искомой подстроки.
Опять же, было правильно сказано, что для небольших строк (порядка нескольких килобайт), все эти условия не весомы, и оптимизация имеет смысл только при ОЧЕНЬ частом вызове функции Pos.
Оптимизация... Не поверишь... Для старших процессоров (PentiumPro и выше) простой перебор символов в цикле и их сравнение. Быстро работате функция из библиотеки QStrings. Ее мне так и не удалось обогнать, хоть и пытался :)
Прочие не пробывал.

Pos - скорость. Найти похожие ветки