| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL | | Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

	« предыдущая ветвь | форум | следующая ветвь »

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

opium ©   (2014-04-15 17:31:00) 

Начал профилировать код и заметил, что довольно много времени уходит на функцию:
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

---

Sapersky   (2014-04-16 00:35:00) [1]

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

---

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

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

---

Sapersky   (2014-04-15 22:41:00) [3]

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

---

Rouse_   (2014-04-15 21:28:00) [4]

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

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

---

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

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

---

Rouse_   (2014-04-15 19:01:00) [6]

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

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

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

---

opium   (2014-04-15 18:12:00) [7]

Функцию переворота использовал системную из 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)

---

MBo_Moskow   (2014-04-15 18:06:00) [8]

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

---

opium   (2014-04-15 17:55:00) [9]

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

---

MBo_Moskow   (2014-04-15 17:54:00) [10]

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

---

Наверх