Страницы

Поиск по вопросам

вторник, 30 октября 2018 г.

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

Имеется программа для сравнения 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; Подскажите хороший алгоритм для более быстрого сравнения строк.


Ответ

Отсортировать базы и сравнивать за один проход. Залить в какую-нить БД, добавить индексов, фильтровать там. сложно что-то более конкретное советовать... 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;

Комментариев нет:

Отправить комментарий