| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Проблема при использовании хеширования [D7, WinXP]
Externalsym © (2004-08-16 11:31:00)Я решил использовать ХЕШИРОВАННЫЙ стринглист из юнита 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;
TUser (2004-08-16 12:24:00) [1]
> Замерять надо только поиск.
Если замерить поиск - будет такой же результат, т.к. поиск в этом классе (ф-ция IndexOf) предполагает создание хеша (в данном случае). Использование такого класса рационально только в одном случае - если мы заполнили стринглист, а потом много-много раз в нем ищем.
Sandman25 (2004-08-16 12:24:00) [2]С учетом [6] Для размещения в хэш-листе нужно знать хэш, его расчет занимает некоторое времяменяется на Для первого поиска в хэш-листе нужно знать хэш, его расчет занимает некоторое время, что, в принципе, не принципиально :)
Sandman25 (2004-08-16 12:22:00) [3][3] Externalsym (16.08.04 11:45)
Зачем мне в исходники смотреть? Для размещения в хэш-листе нужно знать хэш, его расчет занимает некоторое время.
TUser (2004-08-16 12:22:00) [4]
> Ты бы сначала посмотрел в исходник :) добавление в ХэшСтрингЛист вообще есть одно и то же, что и в простом листе ;)
Угу. А на IndexOf вызывается UpdateValueHash. Ты потом ищешь только 1 раз. Для этих целей - нерационально использвать хеширование. Вот, если бы надо было искать раз эдак, много - тогда да. А так получается, что перед поиском выполняется очень сложная процедура - хеширование. Сам поиск проходит быстро, но накладные расходы при этом велики.
На самом деле класс устроен не лучшим образом - при добавлении каждой строки весь созданный ранее хеш забывается. Лучше бы он модифицировался, как в СУБДах.
REA (2004-08-16 12:02:00) [5]>добавление в ХэшСтрингЛист вообще есть одно и то же, что и в простом листе ;)
Не совсем - разница в функции Changed
При первом вызове обновляется Hash поэтому пример не показателен - выигрыш будет на поиске большого количества элементов.
Замерять надо только поиск.
Externalsym (2004-08-16 11:45:00) [6]2 Sandman25 ©
Ты бы сначала посмотрел в исходник :) добавление в ХэшСтрингЛист вообще есть одно и то же, что и в простом листе ;)
2 VMcL ©
Неа.
VMcL (2004-08-16 11:36:00) [7]>> Externalsym (16.08.04 11:31)
Может сортированный TStringList и метод TStringList.Find спасут отца русской демократии?
Sandman25 (2004-08-16 11:35:00) [8]Замерять нужно только поиск. Естественно, что добавление в HashStringList протекает медленнее.
| |
