Есть ли в Дельфи функция поиска суб строки в строке

← →
Beglec (2003-03-05 00:53) [0]

Есть:
function Pos(SubSTR,STR)
Но данная функция медленная!!!
А есть что либо более быстрое.

← →
MBo (2003-03-05 01:07) [1]

сам напиши.
или посмотри www.optimalcode.com

← →
Palladin (2003-03-05 01:08) [2]

на основании чего ты заявляешь что она медленная?

← →
Beglec (2003-03-05 01:28) [3]

более 100 раз в секунду проверяется всякие строки на соответствие искомому
это занимает много процессорного времени, что вызывает определенные трудности.
Как убираю данную функцию все работает быстро.
Процедура Pos является слабым звеном.
Вот и спрашиваю, может чего быстрее есть

← →
Opuhshii (2003-03-05 07:23) [4]

Возможно "слабым звеном" является алгоритм,... :)

← →
Beglec (2003-03-05 09:21) [5]

Как он может быть слабым?

Тектовые строки не моя программа подает. Она их получает от чужеродного продукта.
А процедура самая что ни на есть простая

if pos(substr,str)>0 then inc(Counter);

Это что сложный алгоритм????

В тем более выше было, что если делаешь так
//if pos(substr,str)>0 then inc(Counter);
То все оки доки, скорость возрастает на много процентов.

← →
stone (2003-03-05 09:27) [6]

function StrPos(const Str1, Str2: PChar): PChar;

Description

StrPos returns a pointer to the first occurrence of Str2 in Str1. If Str2 does not occur in Str1, StrPos returns nil.

Note: If the source string contains international characters, use AnsiStrPos instead.

← →
Opuhshii (2003-03-05 09:50) [7]

>Как он может быть слабым?
может, все может быть,..

"более 100 раз в секунду проверяется всякие строки на соответствие искомому",..
мда,.. нужно ли это? более 100 раз в секунду ?

>Но данная функция медленная!!!
посмотрите как она устроена,..
может быть сможете оптимизировать её под свои нужды,.. :)

>if pos(substr,str)>0 then inc(Counter);
>Это что сложный алгоритм????

ах, если это весь алгоритм, то да,. я согласен.
если закоментировать эту строку, скорость возрастает на Очень много процентов!

← →
Beglec (2003-03-05 10:25) [8]

-> Opuhshii
Соглашусь, что алгоритмы бывают слабыми. От их очень многое зависит

if pos(substr,str)>0 then inc(Counter);
Данная строка действительно является единственной в процедуре.

А вообще лучше бы дело сказал, а не ловил бы сорказм.

← →
Юрий Зотов (2003-03-05 10:34) [9]

Действительно, это так. К сожалению, Pos реализует, наверное, самый простой (но и самый медленный) из известных агоритмов поиска подстроки. Ищите сторонние модули - например, QString (кажется, так он называется). Писать самому нет большого смысла, легче найти уже готовый и отлаженный.

И еще: если в качестве Substr и/или Str используется TStrings.Text, то это будет ОЧЕНЬ большим замедлением - при каждом обращении к этому свойству текст будет генериться заново. Если текст не меняется, присвойте его 1 раз какой-то строковой переменной и используйте ее.

← →
Dimka Maslov (2003-03-05 10:41) [10]

> Stone по замерам StrPos медленнее Pos. В них реализован один и тот же алгоритм - сначала ищем первый символ подстроки, потом сравниваем с одной подстрокой. Проблема в том, что функции Pos длина строки известна, а StrPos её ещё надо вычислить. Беда же функции Pos заключается в том, что она ищет только с первого символа.

Вот пример быстрой функции:
http://delphibase.endimus.com/?action=viewfunc&topic=strsearch&id=10394

Однако её эффективность проявляется только при длинных строках, на которотких она проигрывает Pos, но работает быстрее чем StrPos
(опять же при условии, что поиск ведётся с первого символа).

← →
Opuhshii (2003-03-05 10:53) [11]

Дело,. хм,. оставь все как есть и проси денег на 4х-процессорный P4 с 4Gb ram :) и pos"ы в разные потоки,.. и в хелп про SetThreadAffinityMask :))

вообщем решение искать вам,... :)

← →
Anatoly Podgoretsky (2003-03-05 11:39) [12]

if pos(substr,str)>0 then inc(Counter);

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

← →
Beglec (2003-03-05 16:50) [13]

->Anatoly Podgoretsky
Наглядный пример статистики.
Задача:
Нужно посчитать сколько пришло правильных строк по сети.
Пропускная способность при использовании Pos = 10 Mb в минуту.
Пропускная спосбность не используя метод Pos = 80 Мб в минуту.

вот мне и приходится искать более быстрый вариант Pos.

← →
Dms (2003-03-05 16:54) [14]

Есть быстрые алгоритмы поиска. Обратись к первоисточникам (к Кнуту)

← →
Smithson (2003-03-05 17:06) [15]

Держи. На длинных строках и некоротких substr работает сильно быстрее

Function substr(Pattern, S: String; var arFound: TArrayOfInteger; Num: Integer = 1; UpperChars: Boolean = false): Integer; var Lambda: array[char] of integer; PatternLen: Integer; fIndex, q, I, J, N: Integer; Begin { Расчитать переходы при заданых стоп-символах } fillchar(Lambda, SizeOF(lambda), 0); PatternLen := length(Pattern); N := length(S); if (PatternLen = 0) or (N = 0) or (N < PatternLen) then begin Result := 0; exit end; if UpperChars then begin S := AnsiUpperCase(S); Pattern := AnsiUpperCase(Pattern); end; for I := 1 to PatternLen do lambda[Pattern[I]] := I; fIndex := 0; if Num <> 1 then begin SetLength(arFound, N); fillchar(arFound[0], SizeOF(arFound), 0); end; q := 0; while q <= N-PatternLen do begin J := PatternLen; while (j > 0) and (Pattern[J] = S[q+J]) do Dec(J); if J = 0 then begin // Совпадение if Num = 1 then begin // Нужно только первое совпадение Result := Q+1; exit end; arFound[fIndex] := Q+1; Inc(fIndex); Q := Q+(PatternLen+1-Lambda[S[Q+PatternLen+1]]); // Смещение на новую позицию end else begin // Облом if j - Lambda[S[Q+J]] <= 0 then Inc(Q) else Q := Q+J-Lambda[S[Q+J]]; end; end; if Num = 0 then begin // нужен весь массив вхождений Result := fIndex; exit end; if Num < 0 then begin // надо найти n-ое вхождение с конца J := fIndex+Num; if J < 0 then Result := 0 // Нет такого else Result := arFound[J]; end else begin// надо n-ое вхождение с начала if Num-1 > fIndex-1 then Result := 0 // Нет такого вхождения else Result := arFound[Num-1]; end; End;

← →
Mystic (2003-03-05 17:13) [16]

Для оптимизации мало исходных данных.

1) SubStr у тебя одна и та же строка, или нет? Если одна и та же, то можно произвести оптимизацию, предварительно создав вспомогательные таблицы для этой строки. Например, если мы ищем строку abcdef при этом шестой символ оказывается g, то можно смело переходить к двенадцатому символу.

2) Соотношение длины SubStr к длине Str.

3) Примерно, какие строки ищутся и какие строки приходят. В самом тяжелом варианте (ищем последовательноть ababab, а приходят в основном ababaababaababaababa...) соптимизировать будет непросто (если возможно)

← →
Anatoly Podgoretsky (2003-03-05 17:57) [17]

Beglec © (05.03.03 16:50)
Общии слова, можно сказать у тебя плохой алгоритм, одну дыру я тебе показал, наверно у тебя их много.

← →
VaS (2003-03-05 19:34) [18]

Юрий Зотов: Насчет скорости TStrings.Text. Оно сделано через move() и весьма шустро работает.

← →
Anatoly Podgoretsky (2003-03-05 19:58) [19]

VaS © (05.03.03 19:34)
Это свойство

← →
Beglec (2003-03-05 20:53) [20]

-> Anatoly Podgoretsky - прочитай внимательно саму задачу.
В программе данная фигня только одна и без процедуры ни как!!! потому как она срабатывает по событию. И дык у меня тоже нет.

-> Mystic спосибо за действительно хоть что то стоящее. Но суть в том, что как раз у меня 3 вариант и есть.

← →
Юрий Зотов (2003-03-05 23:11) [21]

> VaS © (05.03.03 19:34)
> Насчет скорости TStrings.Text.

"Весьма шустро" - это что означает? По сравнению с чем шустро? Или сколько это в миллисекундах? Или еще что-то?

Могу сообщить - писал я как-то одну программу, где этого сначала не учел. Выполнялась она 43 минуты. После замены обращений к свойству Text на обращения к стринговой пременной - 6 минут. Более в программе ничего не менялось, только это.

Есть разница?

По-моему, есть. В семь с лишним раз. Причем это уже конкретные цифры, а не "весьма шустро".

Легкоатлеты тоже бегают весьма шустро. Но по сравнению с пешеходом, а не с самолетом. То есть - время достижения бегуном соседнего переулка вполне приемлемо. А время достижения им же Монголии - недопустимо велико.

Задачи бывают разные - вот в чем дело. А в данном случае - если уж человека не устраивает скорость Pos, значит, его задача именно из серии Монголии, а не соседнего переулка.

← →
Beglec (2003-03-05 23:16) [22]

->Юрий Зотов полностью согласен.

Прога работает, только нужно чуть чуть ее ускорить :)

← →
Юрий Зотов (2003-03-05 23:46) [23]

> Beglec

Все же советую попробовать библиотеку QStrings. Думаю, подойдет.
http://www.google.com.ru/search?q=QStrings

← →
Anatoly Podgoretsky (2003-03-06 12:03) [24]

Пока не будет приведена конкретность в виде кода говорить трудно, но явно соновная проблема не в POS, но тебе посоветовали самые быстврые библиотеки, попробуй.

← →
Sha (2003-03-06 12:40) [25]

> Beglec © (05.03.03 20:53)
> Но суть в том, что как раз у меня 3 вариант и есть.

Хочешь получить дельный совет, давай условия конкретно.
Устал смотреть, как народ их у тебя вытягивает.

← →
Beglec (2003-03-06 16:15) [26]

Показываю код
procedure GetData(Data: TPacketType);
begin
if Pos("192.168.",Data.IPSender)>0 then Inc(InternetMb,Data.PacketSize);
end;

Из-за данной процедуры лаги по сети. Ping=50-100
Убираю строчку.
Лаги пропадают. Ping 5-10

Куда еще яснее и понятнее!?

← →
Anatoly Podgoretsky (2003-03-06 16:19) [27]

Что такое Data.IPSender, Data.PacketSize из за них может быть сильное торможение.

← →
Anatoly Podgoretsky (2003-03-06 16:24) [28]

Но ты хотя бы переписал процедуру так
procedure GetData( const Data: TPacketType);

← →
Beglec (2003-03-06 17:12) [29]

-> Anatoly Podgoretsky
Data.IPSender: string;
Data.PacketSize: integer;

простая типизированная запись.

ДА БЛИН. не в const дело!!!
IPSender: string;
Pos("192.168.",IPSender) - Вот в чем вопрос!

← →
Basilio (2003-03-06 17:27) [30]

На порядки возрастает скорость обработки строк, если строковые аргументы функций и процедур объявлены как const или var.
Если сама процедура выглядит так:
procedure DoStep(s,substr:string); begin if pos(substr,s)>0 then inc(counter); end;
то она работает раз в десять медленнее, чем
procedure DoStep( const s,substr:string); begin if pos(substr,s)>0 then inc(counter); end;
а при комментировании строки может сработать ещё и оптимизатор - в этом случае будет безразлично, как объявлены параметры.

← →
Basilio (2003-03-06 17:33) [31]

Тоже относится и к динамическим массивам и к структурам, содержащим строки/динамические массивы

← →
Anatoly Podgoretsky (2003-03-06 17:33) [32]

Beglec © (06.03.03 17:12)
Это как же не в этом, без этого у тебя происходит копирование записи на стек, а с const передается только ссылка на эту запись. Учите основы. И чувствуется по всему ходу обсуждения, что у тебя таких неоптимальных мест много, но ты как партизан выдаешь необходимую информацию только под пыткой.

← →
Beglec (2003-03-06 20:41) [33]

->Anatoly Podgoretsky
Вот чайник.
15 лет программирую и незнал такой фишки :((((
Как говорится век живи век учить.

Можно сказать, из данного вопроса узнал больше чем расчитывал получить :)
Признаю, что я кретин.

← →
Anatoly Podgoretsky (2003-03-06 20:44) [34]

И то хорошо, но если бы ты в самом начале привел достаточное количество кода, то получил бы раньше.

← →
Fredericco (2003-03-06 21:38) [35]

procedure TForm1.Button1Click(Sender: TObject);
var
i,j:integer;
c:cardinal;
s:string;
begin
s:=StringOfChar("d",60000);
s:=s+"lo wfkdsmfklkmmfkldsmfkldsmfdsfm";
c:=GetTickCount;
for j:=1 to 100 do
i:=Pos("lo w",s);
Memo1.Lines.Add(FloatToStr(GetTickCount-c)+":"+IntToStr(i));
end;

Результат 21:60001.

Медлено?..

← →
Anatoly Podgoretsky (2003-03-06 21:47) [36]

5000 сравнений на строке в 60 кб, при отягтящих обстоятельства.
Просканировано свыше 300 000 000 символов за секунду, неплохо конечно.

Есть ли в Дельфи функция поиска суб строки в строке Найти похожие ветки