Быстрое сравнение строк?

← →
andreil © (2008-08-06 20:10) [0]

У меня в программе есть необходимость БЫСТРО сравнивать множество строк множество раз (20 000шт около 3000раз). Это необходимо, поскольку поиск осуществляется только по имени файла, его хэндл будет на выходе.
Пробывал всякие там strcmp, StrComp_NoCase, AnsiCompareStr - сильно медленно (или я их неправильно использую?):
//strcmp if Header.pDirectoryHeader.ItemCount>0 then for i:=0 to Header.pDirectoryHeader.ItemCount-1 do if strcmp(pChar(Path), pChar(Header.FileNames[i]))=0 then begin result:=i; Exit; end; //StrComp_NoCase, AnsiCompareStr if Header.pDirectoryHeader.ItemCount>0 then for i:=0 to Header.pDirectoryHeader.ItemCount-1 do if StrComp_NoCase(pChar(Path), pChar(Header.FileNames[i]))=0 then if AnsiCompareStr(Path, Header.FileNames[i])=0 then begin result:=i; Exit; end;

← →
Сергей М. © (2008-08-06 20:17) [1]

> сильно медленно

Интересно, с каким "слабо быстро" ты хотел бы сравнить свое "сильно медленно" ?

← →
andreil © (2008-08-06 21:01) [2]

С HlLib"ом. Там этот же поиск происходит за пару секунд, но дело в том, что там все написано на С++ + все сильно взаимосвязанно.

← →
Сергей М. © (2008-08-06 21:13) [3]

> С HlLib"ом

Что за зверь ?

Причем здесь СсыПлюсПлюс ?

Кто с кем "сильно взаимосвязан" ?

Ты вообще-то представляешь себе алгоритмы сравнения строк , в т.ч. регистронезависимые ?

← →
Юрий Зотов © (2008-08-06 21:18) [4]

1. Начнем с простого - на кой леший нужна эта строка:
if Header.pDirectoryHeader.ItemCount > 0 then...

2. Зачем во втором куске 2 сравнения?

3. Модуль QString можно попробовать, в Сети он есть. Еще лучше - найти функции работы со строками от Александра Шарахова (Sha), среди них вполне может быть и сравнение строк.

4. Если хранить (а потом сравнивать) не сами строки, а их хэши, то поиск станет намного быстрее.

← →
Ruzzz © (2008-08-06 21:57) [5]

Посмотри исходные коды функций, попробуй переписать на асме, я когда-то от нечего делать такое делал :) если лень, то поставь брекпоинт на функции и скопируй асм-код, далее усовершенствуй :) Вообще все критичные моменты даже в наше время все еще можно писать на асме :)

Отсортируй список строк, а далее используй алгоритмы быстрого поиска!

← →
Viktorious © (2008-08-06 23:47) [6]

Еще можно использовать TStringList/TWideStringList. За все версии Делфи точно не скажу, но в BDS2006, если свойство TStringList.Sorted установлено в true, при поиске в списке (функция IndexOf) используется бинарный поиск, что существенно ускоряет процесс.

Я пользовался так:

AList := TWideStringList.Create;
AList.Sorted := true;
AList.Duplicates := dupIgnore;

потом добавляете ваши строки AList.Add(s) (хинт: если речь идет о именах файлов, сохраняйте строки, преобразованные к верхнему регистру - не надо будет делать лишний раз при сравнении).

Потом AList.IndexOf(s) выдаст -1, если строки s нет списке, иначе выдаст индекс этой строки в списке.

← →
Johnmen © (2008-08-07 09:43) [7]

См. раздел Fastcode Challenges отсюда
http://fastcode.sourceforge.net/
ф-ию CompareStr/CompareText. Там среди авторов и упомянутый Sha © есть :)

← →
Rouse_ © (2008-08-07 13:04) [8]

Сравнивай хэши наименований по сортированному списку

> Сергей М.
HlLib - это такая библиотека на С++, предназначенная для работы с файлами такой программы, как Steam, например с GCF(NCF)-архивами.

> Юрий Зотов
1. Если файл неправильно откроется (файла нет или ошибка), то эта переменная бужет равна 0.
2. либо первое либо второе - эффект одинаковый. Просто забыл закомментировать в посте).
3. Попробую;
4. Поподробнее можно?

Сейчас попробую сам ускорить, может получится...

> andreil © (07.08.08 19:17) [9]

> Если файл неправильно откроется (файла нет или ошибка), то эта
> переменная бужет равна 0.

И это будет автоматически учтено в следующей строке (заголовке цикла). Поэтому дополнительная проверка не нужна, заголовок цикла сделает ее сам.

> andreil © (07.08.08 19:17) [9]

> 4. Поподробнее можно?

Гугль по словам hash b Delphi. Например:
http://www.sql.ru/forum/actualthread.aspx?tid=48091

>Посмотри исходные коды функций, попробуй переписать на асме, я когда-то от нечего делать такое делал :) если лень, то поставь брекпоинт на функции и скопируй асм-код, далее усовершенствуй :) Вообще все критичные моменты даже в наше время все еще можно писать на асме :)

Асм в данном случае ничего не даст. Алгоритмическими методами можно ускортися на порядок или несколько.

Быстрое сравнение строк? Найти похожие ветки