Скачать: CL | DM;

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

← →
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-строках.

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.47 MB
Время: -0.964 c