Максимально быстрый алгоритм сравнения 2х строк

#windows #delphi #алгоритм

Имеется программа для сравнения 2х баз вида:
123
234
456

При совпадении значений строка удаляется в новой базе.
Базы большие(по 300т строк) и скорость получается очень маленькой.
Вот кусок моего кода:
 while i <= ListNBD.Count-1 do
 begin
  StrN:=ListNBD[i];                  //строка и3 новой базы
  j:=0;
  while j <= ListBD.Count-1 do       //идем по строкам старой базы
    begin
    StrB:=ListBD[j];                 //строка и3 старой базы
  if (Length(StrN)=Length(StrB))then //если строки равны по кол-ву символов
   if (StrN=StrB) then               //сравнение   {САМА ПРОВЕРКА}
      begin
        ListNBD.Delete(i);           //удаляем из новой базы
        Inc(DelStatusB);             //увеличиваем статус удаленных строк
        i:=i-1;                      //перемещаемся назад на 1 запись
        break;                       //выходим из 1 цикла
      end;
    Inc(j);
    end;
  inc(i);
  Inc(StatusB);
 end;

Подскажите хороший алгоритм для более быстрого сравнения строк.    

Ответы

Ответ 1

Отсортировать базы и сравнивать за один проход.
Залить в какую-нить БД, добавить индексов, фильтровать там.

сложно что-то более конкретное советовать...
UPD Использование THashedStringList.
Входные данные: два файла в одном 300к строк (base1.txt), в другом 600к строк (base2.txt).
Во втором файле каждая вторая строка из первого файла. Длина строк 100 символов (влияет
на скорость вычисления хэша). Хэш строится за ~секунду по 300к строкам.
procedure TForm1.Button1Click(Sender: TObject);
var
  SL_Old: THashedStringList;
  SL_New: TStringList;
  SL_Result: TStringList;
  i: Integer;
begin
  Memo1.Lines.Add('Start:'+DateTimeToStr(Now));
  SL_Old:=THashedStringList.Create;
  SL_New:=TStringList.Create;
  SL_Result:=TStringList.Create;
  try
    SL_Old.LoadFromFile('c:\base1.txt');
    SL_New.LoadFromFile('c:\base2.txt');
    for i:=0 to SL_New.Count-1 do
    begin
      if SL_Old.IndexOf(SL_New[i])<0 then
        SL_Result.Add(SL_New[i]);
    end;
    SL_Result.SaveToFile('c:\baseresult.txt');
  finally
    SL_Old.Free;
    SL_New.Free;
    SL_Result.Free;
    Memo1.Lines.Add('Finish:'+DateTimeToStr(Now));
  end;
end;

Время работы 1,5 минуты.
Если поменять местами файлы, т.е. хэшировать бОльший файл, то время работы - 1 минута.
Если использовать TStringList, то поиск строк будет аналогичен коду в вопросе, там
все плохо естественно, через 10 минут прервал выполнение.
Для интересующихся в THashedStringList хэш-функция используется такая:
function TStringHash.HashOf(const Key: string): Cardinal;
var
  I: Integer;
begin
  Result := 0;
  for I := 1 to Length(Key) do
    Result := ((Result shl 2) or (Result shr (SizeOf(Result) * 8 - 2))) xor
      Ord(Key[I]);
end;


Ответ 2

(Сходу в голову приходят два варианта, если реализовывать ваш алгоритм самостоятельно)

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


Алгоритмическая сложность - O(N log N), где N = max(N1, N2), поскольку сортировка
займет время, равное O(N log N), а алгоритм слияния - O(N).


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




Строго проанализировать алгоритмическую сложность (как и всегда в случае хэширования)
в этом случае довольно-таки непросто - для полноценного обоснования рекомендую обратиться
к [Cormen] Introduction to algorithms.


Но, если прикинуть сложность алгоритма, то она будет стремиться к O(N), поскольку
затраты на вставку элементов в хэш-таблицу должны составлять O(N(1 + A)), где A - медленно
растущая функция, а перечисление всех элементов в хэш-таблице однозначно можно реализовать
за O(N).


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


Ответ 3

Еще как вариант: построить бор из первого списка и поиск слова из второго будет равен
его длине
Могут правда возникнуть проблемы с памятью, если в первой базе слишком много слов


Ответ 4

В помощь вам операторы SQL:
EXCEPT
INTERSECT
UNION
UNION ALL
Построчная обработка таблиц - это жесть!