Добрый день ВСЕМ! Как ускорить поиск в списке TList?

← →
tytus (2006-02-03 13:50) [0]

Есть тип:
PCalling=^TCalling;
TCalling=Record
ID:integer;
DN:string[12];
Count:integer;
end;
procedure Compose;
var
Calling:PCalling;
CallingList:TList;
begin
CallingList:=TList.Create;
//Вначале ищутся записи, поетому их количество до поиска известно, и можно установить емкость списка.
CallingList.Capasity:=FindingRecordCount;
В программе ищутся записи (около 1 млн).
Из записи выбирается строка, которую нужно проверить на наличии в списке, и выполняется следующее:
s:=Value;// к примеру - 487563312 (номера телефонов)
//Поиск
n:=0;
with CallingList do
while (n<>Count)and(PCalling(Items[n])^.DN<>s) do
inc(n);
if n=CallingList.Count then n:=-1;
//Поиск содрал с модуля реализации TLIst-a
if n=-1 then begin
New(Calling);
Calling^.ID:=CallingList.Count+1;
Calling^.DN:=s;
Calling^.Count:=1;
CallingList.Add(Calling);
end else begin
Calling:=PCalling(CallingList.Items[n]);
Calling^.Count:=Calling^.Count+1;//Если номер есть в списке, то увеличиваем его счетчик
end;
Так вот, если номеров около 10000, то скорость поиска терпима, а если 800 000, то ждать можно 10 минут (Р4, 512 Mb).
Вопрос - как сие можно ускорить?
Использовал хеши - но с ними даже медленее.
Написал программку для сравнения TStringList, TList и THashedStringList. Так вот Список и Хеш по скорости почти одинаковые, а СтрингЛист отдыхает... Алгоритм тот-же - с объектами типа Запись. (TStringList.AddObject(s,TObject(Calling));

← →
TUser © (2006-02-03 13:54) [1]

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

← →
tytus (2006-02-03 14:04) [2]

>[1]TUser
Сортировать я так полагаю лучше уже тогда, когда не надо добавлять новые елементы в список. У меня готовый список (тысячи елементов) сортируется быстро - меньше секунды (метод Sort списка и своя процедура сортировки - Callinglist.Sort(@MySortProc).
А вот по поводу хеш таблиц и бинарных деревьев - можно немного по-подробнее...

← →
Alex Konshin © (2006-02-03 14:12) [3]

Взгляни на мои юниты AVLtrees или Arrays. Они оба подходят для твоей задачи.
Там же можешь посмотреть на ArrayGrid, чтобы убедится, насколько шустро это работает.
Да, юниты на сайте, который указан в анкете.

> Сортировать я так полагаю лучше уже тогда, когда не надо
> добавлять новые елементы в список.

Да.

> А вот по поводу хеш таблиц и бинарных деревьев - можно немного
> по-подробнее...

http://alogolist.manual.ru/

Добрый день ВСЕМ! Как ускорить поиск в списке TList? Найти похожие ветки