Оптимизация функции

← →
opium (2014-04-15 17:31) [0]

Начал профилировать код и заметил, что довольно много времени уходит на функцию:
function PosEx_end(const SubStr, S: String; Offset: Cardinal = MaxInt): Integer; var I, X: Integer; LenSubStr: Integer; begin LenSubStr := Length(SubStr); if LenSubStr = 0 then raise Exception.Create("Строка поиска должна быть не пустой."); if Offset >= MaxIntD2 then I := Length(S) - LenSubStr + 1 else I := Offset; while I >= 1 do begin if S[I] = SubStr[1] then begin X := 1; while (X < LenSubStr) and (S[I + X] = SubStr[X + 1]) do Inc(X); if (X = LenSubStr) then Exit(I); end; Dec(I); end; Result := 0; end;
Ищет подстроку в строке с конца, с заданной позиции. Есть идеи как ее можно оптимизировать по скорости?
Delphi XE3

← →
MBo_Moskow (2014-04-15 17:54) [1]

перевернуть строки и использовать PosEx

← →
opium (2014-04-15 17:55) [2]

Пробовал. Получается еще медленнее.

← →
MBo_Moskow (2014-04-15 18:06) [3]

Приведенный код работает за произведение длин O(n*m) времени в худшем случае, а предложенный способ почти линейный (если Posex нормально реализована, сейчас заглянуть не могу). Возможно, переворот реализован неправильно?

← →
opium (2014-04-15 18:12) [4]

Функцию переворота использовал системную из StrUtils:
function ReverseString(const AText: string): string;
var
I: Integer;
P: PChar;
begin
SetLength(Result, Length(AText));
P := PChar(Result);
for I := High(AText) downto Low(AText) do
begin
P^ := AText[I];
Inc(P);
end;
end;

Если я правильно понимаю, даже если PosEx линейный, то сложность получается О(n+m+n)

← →
Rouse_ © (2014-04-15 19:01) [5]

Вот это на CompareMem заменить, первое что видно:

> X := 1;
> while (X < LenSubStr) and (S[I + X] = SubStr[X + 1])
> do
> Inc(X);
> if (X = LenSubStr) then
> Exit(I);

остальное вроде все ровненько.
Но ИМХО все равно реверс строки и PosEx пошустрее должен быть.

← →
тупой компилятор (2014-04-15 20:30) [6]

посмотреть реализацию PosEx и сменить направление цикла?

← →
Rouse_ © (2014-04-15 21:28) [7]

> тупой компилятор (15.04.14 20:30) [6]

Ну если свободно владеешь асмом - то как вариант.

← →
Sapersky (2014-04-15 22:41) [8]

Тогда уж лучше разворачивать вариант с SSE4.2, от Агнера Фога, например.

← →
тупой компилятор (2014-04-15 23:37) [9]

интересно было бы сравнить, насколько это лучше

← →
Sapersky (2014-04-16 00:35) [10]

Где-то в 6 раз на Ansi-строках.

Оптимизация функции Найти похожие ветки