Проблема при использовании хеширования

← →
Externalsym (2004-08-16 11:31) [0]

Я решил использовать ХЕШИРОВАННЫЙ стринглист из юнита inifiles.pas (THashedStringList). Он там используется для ускорения поиска строк как написано. Но я провел простой тест и
результаты мне совсем не понравились. На поиск элемента в листе размером 1000000 штук на моем атлоне 1.5ггц были выявлены следующие результаты теста (мс, в среднем):
TStringList - 2504
THashedStringList - 3676

т.е. не понимаю, либо я что -то делаю не так, либо хеширование - это полнейшая лажа.

Вот такой я код использовал для теста. Можете сами попробовать:

uses inifiles; function TickDelta(TickOld, TickNew: ULong): ULong; begin Result := 0; if TickOld <> TickNew then begin if TickNew < TickOld then begin TickNew := TickNew + ULong(MaxInt) + 1; TickOld := TickOld + ULong(MaxInt) + 1; end; Result := TickNew - TickOld; if TickNew < TickOld then if Result > 0 then Result := 0 - Result; end; end; // использование ХЕШИРОВАНИЯ procedure TForm1.Button1Click(Sender: TObject); var sl: THashedStringList; i, idx: integer; t: cardinal; begin t := GetTickCount; label1.Caption := ""; sl := THashedStringList.Create; for i:=0 to 1000000 do begin sl.Add("item"+inttostr(i)+"="+inttostr(i)); application.ProcessMessages; end; idx := sl.IndexOfName("item450000"); if idx >= 0 then sl.ValueFromIndex[idx]; label1.Caption := inttostr(tickdelta(t, GetTickCount)); sl.free; end; // Обычный стринглист procedure TForm1.Button2Click(Sender: TObject); var sl: TStringList; i, idx: integer; t: cardinal; begin t := GetTickCount; label2.Caption := ""; sl := TStringList.Create; for i:=0 to 1000000 do begin sl.Add("item"+inttostr(i)+"="+inttostr(i)); application.ProcessMessages; end; idx := sl.IndexOfName("item450000"); if idx >= 0 then sl.ValueFromIndex[idx]; label2.Caption := inttostr(tickdelta(t, GetTickCount)); sl.free; end;

← →
Sandman25 © (2004-08-16 11:35) [1]

Замерять нужно только поиск. Естественно, что добавление в HashStringList протекает медленнее.

← →
VMcL © (2004-08-16 11:36) [2]

>>Externalsym (16.08.04 11:31)

Может сортированный TStringList и метод TStringList.Find спасут отца русской демократии?

← →
Externalsym (2004-08-16 11:45) [3]

2 Sandman25 ©

Ты бы сначала посмотрел в исходник :) добавление в ХэшСтрингЛист вообще есть одно и то же, что и в простом листе ;)

2 VMcL ©

Неа.

← →
REA © (2004-08-16 12:02) [4]

>добавление в ХэшСтрингЛист вообще есть одно и то же, что и в простом листе ;)

Не совсем - разница в функции Changed
При первом вызове обновляется Hash поэтому пример не показателен - выигрыш будет на поиске большого количества элементов.
Замерять надо только поиск.

← →
Sandman25 © (2004-08-16 12:22) [5]

[3] Externalsym (16.08.04 11:45)

Зачем мне в исходники смотреть? Для размещения в хэш-листе нужно знать хэш, его расчет занимает некоторое время.

> Ты бы сначала посмотрел в исходник :) добавление в ХэшСтрингЛист вообще есть одно и то же, что и в простом листе ;)

Угу. А на IndexOf вызывается UpdateValueHash. Ты потом ищешь только 1 раз. Для этих целей - нерационально использвать хеширование. Вот, если бы надо было искать раз эдак, много - тогда да. А так получается, что перед поиском выполняется очень сложная процедура - хеширование. Сам поиск проходит быстро, но накладные расходы при этом велики.
На самом деле класс устроен не лучшим образом - при добавлении каждой строки весь созданный ранее хеш забывается. Лучше бы он модифицировался, как в СУБДах.

> Замерять надо только поиск.

Если замерить поиск - будет такой же результат, т.к. поиск в этом классе (ф-ция IndexOf) предполагает создание хеша (в данном случае). Использование такого класса рационально только в одном случае - если мы заполнили стринглист, а потом много-много раз в нем ищем.

С учетом [6] Для размещения в хэш-листе нужно знать хэш, его расчет занимает некоторое время меняется на Для первого поиска в хэш-листе нужно знать хэш, его расчет занимает некоторое время, что, в принципе, непринципиально :)

Проблема при использовании хеширования Найти похожие ветки