Форум: "Основная";
Текущий архив: 2004.08.29;
Скачать: [xml.tar.bz2];
ВнизПроблема при использовании хеширования Найти похожие ветки
← →
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)
Зачем мне в исходники смотреть? Для размещения в хэш-листе нужно знать хэш, его расчет занимает некоторое время.
← →
TUser © (2004-08-16 12:22) [6]
> Ты бы сначала посмотрел в исходник :) добавление в ХэшСтрингЛист вообще есть одно и то же, что и в простом листе ;)
Угу. А на IndexOf вызывается UpdateValueHash. Ты потом ищешь только 1 раз. Для этих целей - нерационально использвать хеширование. Вот, если бы надо было искать раз эдак, много - тогда да. А так получается, что перед поиском выполняется очень сложная процедура - хеширование. Сам поиск проходит быстро, но накладные расходы при этом велики.
На самом деле класс устроен не лучшим образом - при добавлении каждой строки весь созданный ранее хеш забывается. Лучше бы он модифицировался, как в СУБДах.
← →
TUser © (2004-08-16 12:24) [7]
> Замерять надо только поиск.
Если замерить поиск - будет такой же результат, т.к. поиск в этом классе (ф-ция IndexOf) предполагает создание хеша (в данном случае). Использование такого класса рационально только в одном случае - если мы заполнили стринглист, а потом много-много раз в нем ищем.
← →
Sandman25 © (2004-08-16 12:24) [8]С учетом [6] Для размещения в хэш-листе нужно знать хэш, его расчет занимает некоторое время меняется на Для первого поиска в хэш-листе нужно знать хэш, его расчет занимает некоторое время, что, в принципе, непринципиально :)
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2004.08.29;
Скачать: [xml.tar.bz2];
Память: 0.47 MB
Время: 0.032 c