страничка tripsin'а

Главная | Статьи | Заметки | Файлы| Ссылки | я

Палиндром

На форуме vr-online недавно прошла такая тема. Надо было сделать функцию, которая определяет является ли слово палиндромом ("перевертышем"). Мне очень понравилось предложение от Elen:

function IsPalindromeByElen(S: String): Boolean;
begin
  Result := S = ReverseString(S);
end;

Однако все решили, что это будет не очень честно, т.к. здесь используется внешняя функция из модуля StrUtils.pas. Решено было сделать самодостаточную функцию, не использующую внешние модули. Самый лучший алгоритм первым предложил innok, потому-что я не успел. Зато я воплотил его идею в код:

function IsPalindrome(const S: String): Boolean;
var
  i: Integer;
begin
  Result := False;
  for i := 1 to Length(S) div 2 do
    if S[i] <> S[Length(S) - i + 1] then Exit;
  Result := True;
end;

Но и в этом случае используется внешняя функция Length, хотя она и является встроенной. Дискуссия стала набирать обороты. И уже начали на личности переходить. Elen выложила какую-то чудную функцию на встроенном асме. Меня это все тоже зацепило и я сделал свою функцию. Вот ее код на Delphi:

function IsPalindrome(const S: String): Boolean;
var
  i,l: Integer;
begin
  Result := False;
  l := PLongWord(LongWord(S) - 4)^;
  for i := 1 to l div 2 do
    if S[i] <> S[l - i + 1] then Exit;
  Result := True;
end;

Здесь длина строки определяется с помощью небольшого хака. Его смысл объясняется в моей статье String. То, чего ты мог и не знать в разделе про AnsiString. А потом я переписал эту функцию на встроенном ассемблере Delphi:

function IsPalindrome(const S: String): Boolean;
asm
  push ebx;          // сохраняю регистры
  push esi;
  push edi;
  mov edi, eax;      // edi - начало строки
  xor eax, eax;      // Result := False
  test edi,edi;      // проверка на пустую строку
  je @exit;
  mov esi,[edi - 4]; // esi - длина строки
  mov ecx,esi;
  shr ecx,1;         // Вычисляю количество итераций
  test ecx, ecx; 
  je @exit;          // выхожу если счетчик цикла = 0
@loop:
  mov edx, edi;
  sub edx, ecx;             // [edi+esi-ecx]
  mov bl, byte [edx+esi];   // загружаю байт справа
  cmp bl, byte [edi+ecx-1]; // сравниваю с байтом слева
  jnz @exit;         // Выхожу из цикла если они не равны
  dec ecx;           // Уменьшаю счетчик
  jnz @loop;         // При нулевом счетчике выход из цикла
  mov eax, True;     // Result := True
@exit:
  pop edi;           // восстанавливаю регистры
  pop esi;
  pop ebx;
end;

Как это еще можно оптимизировать я уже не представляю. Конечно функция определения палиндрома должна еще уметь:

Все это нужно для того, чтобы предложение "А роза упала на лапу Азора." тоже воспринималось как палиндром. Но все это уже не интересно и делать не хочется.

Hosted by uCoz