powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Delphi [игнор отключен] [закрыт для гостей] / TDictionary или TList<>.BinarySearch с позиции поиска
25 сообщений из 479, страница 2 из 20
TDictionary или TList<>.BinarySearch с позиции поиска
    #39368880
серчер
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
причем чем-то таким, чтобы это еще в базе можно было бы выгрузить в готовом виде. А не так чтобы в коде еще шерстить. Это вариант, если не получится из базы достать готовый.

Может есть какие то стандартные функции хеширования в инт для дельфи и мсскл?
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39368907
Фотография Квейд
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
CRC32 же!
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39368926
white_nigger
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В современных делфях хэшей вагон и маленькая тележка. Даже модуль специальный есть. А ТС упорно игнорирует совет почитать матчасть чтоб представлять что это и с чем его едят...
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369072
asviridenkov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати, я тут небольшой тест сделал TDictionary<string, object> c Trie.
Содержимое - список тегов HTML, прогоняется много раз поиск всего списка в словаре.
Получается, что на поиске trie дает где-то 40% выигрыша.
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369077
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Частный случай всегда быстрей чем универсалка.
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369085
asviridenkov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rgreatЧастный случай всегда быстрей чем универсалка.

Ага, конечно. Сравни TStringList c TDictionary
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369087
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
asviridenkov,

TStringList не оптимизирован на поиск ключей.
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369090
white_nigger
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
asviridenkovКстати, я тут небольшой тест сделал TDictionary<string, object> c Trie.
Содержимое - список тегов HTML, прогоняется много раз поиск всего списка в словаре.
Получается, что на поиске trie дает где-то 40% выигрыша.Пример выложить можешь? Хочу свой словарик сравнить
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369091
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
asviridenkovКстати, я тут небольшой тест сделал TDictionary<string, object> c Trie.
Содержимое - список тегов HTML, прогоняется много раз поиск всего списка в словаре.
Получается, что на поиске trie дает где-то 40% выигрыша.
Просто TDictionary невероятный тормоз. У меня хеш-таблица построенная по аналогичному алгоритму (открытая адресация с линейным пробированием) тоже уделывает TDictionary. На рандомных ключах (GUID) на 97%, на ключах с последовательно изменяющейся частью (index1 .. 1000000) на 159%, на английском словаре на 46%.
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369092
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
asviridenkovАга, конечно. Сравни TStringList c TDictionary
На длинных ключах стринглист надерёт словарю жопу ;)
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369094
asviridenkov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
white_nigger,

он совсем простой

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
procedure TForm23.Button1Click(Sender: TObject);
var i, k, T: integer;
    L: TStringList;
    s: string;
    D: TDictionary<string, TObject>;
    //ST: THtStringTrie;
    O: TObject;
begin
  L:=TStringList.Create;
  L.Add('div');
  L.Add('span');
  L.Add('table');
  L.Add('td');
  L.Add('tr');
  L.Add('th');
  L.Add('li');
  L.Add('meta');
  L.Add('script');
  L.Add('style');
  L.Add('ol');
  L.Add('ul');
  L.Add('h1');
  L.Add('h2');
  L.Add('h3');
  L.Add('h4');
  L.Add('h5');
  L.Add('thead');
  L.Add('tbody');
  L.Add('html');
  L.Add('body');
  L.Add('blockquote');
  L.Add('address');
  L.Add('frame');
  L.Add('frameset');
  L.Add('pre');
  L.Add('button');
  L.Add('textarea');
  L.Add('strike');
  L.Add('del');
  L.Add('menu');
  L.Add('small');
  L.Add('sub');
  L.Add('sup');
  L.Add('img');
  L.Add('fieldset');
  L.Add('legend');
  D := TDictionary<string, TObject>.Create;
  for i := 0 to L.Count - 1 do
    D.Add(L[i], TObject.Create);
  //ST := THtStringTrie.Create();
  //for i := 0 to L.Count - 1 do
  //  ST.Add(L[i], TObject.Create);
  T := GetTickCount;
  for i := 1 to 1000000 do
  begin
    for k := 0 to L.Count -1 do
      D.TryGetValue(L[k], O)
      //ST.Find(L[k], O);
  end;
  Caption := inttostr(GetTickCount - T);
end;
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369095
asviridenkov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kazantsev AlexeyasviridenkovАга, конечно. Сравни TStringList c TDictionary
На длинных ключах стринглист надерёт словарю жопу ;)

На малом числе строк, в принципе тоже должен.
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369096
asviridenkov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Kazantsev AlexeyasviridenkovКстати, я тут небольшой тест сделал TDictionary<string, object> c Trie.
Содержимое - список тегов HTML, прогоняется много раз поиск всего списка в словаре.
Получается, что на поиске trie дает где-то 40% выигрыша.
Просто TDictionary невероятный тормоз. У меня хеш-таблица построенная по аналогичному алгоритму (открытая адресация с линейным пробированием) тоже уделывает TDictionary. На рандомных ключах (GUID) на 97%, на ключах с последовательно изменяющейся частью (index1 .. 1000000) на 159%, на английском словаре на 46%.

А хэш какой - CRC32? Ты софлкомплетовскую реализацию Hashrie за основу брал?
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369098
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
asviridenkovА хэш какой - CRC32? Ты софлкомплетовскую реализацию Hashrie за основу брал?
Хеш Седжвика. За основу брал голый алгоритм таблицы с открытой адресацией, т.к. он самый простой и удовлетворяет некоторым дополнительным условиям.
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369100
white_nigger
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
На ноуте несколько проходов:
TDictionary ~3678
TdxNamedObjectDictionary ~2266
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369102
white_nigger
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А вообще для таких небольших константных словариков легко идеальный хэш подобрать и сделать специализированный словарь - ещё быстрее будет
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369105
asviridenkov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
white_niggerНа ноуте несколько проходов:
TDictionary ~3678
TdxNamedObjectDictionary ~2266

Ну вот у меня на простейшем Trie ровно такой же результат.
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369108
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
asviridenkovКстати, я тут небольшой тест сделал TDictionary<string, object> c Trie.
Содержимое - список тегов HTML, прогоняется много раз поиск всего списка в словаре.
Получается, что на поиске trie дает где-то 40% выигрыша.

А ты сравни с CachedSerializer
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369109
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
серчерпричем чем-то таким, чтобы это еще в базе можно было бы выгрузить в готовом виде. А не так чтобы в коде еще шерстить. Это вариант, если не получится из базы достать готовый.

Может есть какие то стандартные функции хеширования в инт для дельфи и мсскл?

Ты меня начинаешь подбешивать
TDictionary, когда ключ строка - уже автоматически все делает
За тебя
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369110
asviridenkov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SOFT FOR YOUasviridenkovКстати, я тут небольшой тест сделал TDictionary<string, object> c Trie.
Содержимое - список тегов HTML, прогоняется много раз поиск всего списка в словаре.
Получается, что на поиске trie дает где-то 40% выигрыша.

А ты сравни с CachedSerializer

Я же тест выложил, запусти и сравни.
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369116
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Быстрый хэшик для строки.
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
{$OverFlowChecks OFF}
function GetHash(const Key: String): integer;
var
  a : Integer;
  i : Integer;
begin
  Result:=0;
  a:=63689;
  for i:=1 To Length(Key)-1 do begin
    Result:=Result*a+PWordArray(Key)[i];
    a:=a*378551;
  end;
end;
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369117
asviridenkov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rgreat,

Ты всерьез думаешь что это быстрее CRC32?

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
function CalcStrCRC32(const s: string): cardinal;
var p: pchar;
begin
  Result := $FFFFFFFF;
  p := pointer(s);
  if p <> nil then
    while p^ <> #0 do
    begin
      Result := (((Result shr 8) and $00FFFFFF) xor (Ccitt32Table[(Result xor byte(p^)) and $FF]));
      inc(p);
    end;
end;
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369118
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
asviridenkov,

Проверил, быстрей. А еще говорят дает меньше коллизов.
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369120
asviridenkov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
rgreatasviridenkov,

Проверил, быстрей. А еще говорят дает меньше коллизов.

Насколько быстрее?
...
Рейтинг: 0 / 0
TDictionary или TList<>.BinarySearch с позиции поиска
    #39369121
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
asviridenkov,

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
procedure TMain.Button3Click(Sender: TObject);
const
  CRC32_POLYNOMIAL = $EDB88320;
var
  i, k, T      : integer;
  L            : TStringList;
  Ccitt32Table : array[0..255] of longint;

  function crc32(crc : longint; const c : byte) : longint;
  begin
    crc32 := (((crc shr 8) and $00FFFFFF) xor (Ccitt32Table[(crc xor c) and $FF]));
  end;

  procedure BuildCRCTable;
  var
  i, j, value : DWORD;
  begin
  for i := 0 to 255 do
  begin
  value := i;
  for j := 8 downto 1 do
  begin
  if ((value and 1) <> 0) then
  value := (value shr 1) xor CRC32_POLYNOMIAL
  else
  value := value shr 1;
  end;
  Ccitt32Table[i] := value;
  end
  end;


function GetHash1(const Key: String): integer;
var p: pchar;
begin
  Result := $FFFFFFFF;
  p := pointer(Key);
  if p <> nil then
    while p^ <> #0 do
    begin
      Result := (((Result shr 8) and $00FFFFFF) xor (Ccitt32Table[(Result xor byte(p^)) and $FF]));
      inc(p);
    end;
end;

{$OverFlowChecks OFF}
function GetHash2(const Key: String): integer;
var
  a : Integer;
  i : Integer;
begin
  Result:=0;
  a:=63689;
  for i:=1 To Length(Key)-1 do begin
    Result:=Result*a+PWordArray(Key)[i];
    a:=a*378551;
  end;
end;
{$OverFlowChecks On}


begin
  BuildCRCTable;

  L:=TStringList.Create;
  L.Add('div');
  L.Add('span');
  L.Add('table');
  L.Add('td');
  L.Add('tr');
  L.Add('th');
  L.Add('li');
  L.Add('meta');
  L.Add('script');
  L.Add('style');
  L.Add('ol');
  L.Add('ul');
  L.Add('h1');
  L.Add('h2');
  L.Add('h3');
  L.Add('h4');
  L.Add('h5');
  L.Add('thead');
  L.Add('tbody');
  L.Add('html');
  L.Add('body');
  L.Add('blockquote');
  L.Add('address');
  L.Add('frame');
  L.Add('frameset');
  L.Add('pre');
  L.Add('button');
  L.Add('textarea');
  L.Add('strike');
  L.Add('del');
  L.Add('menu');
  L.Add('small');
  L.Add('sub');
  L.Add('sup');
  L.Add('img');
  L.Add('fieldset');
  L.Add('legend');

  T := GetTickCount;
  for i := 1 to 1000000 do
  begin
    for k := 0 to L.Count -1 do
      GetHash1(L[k]);
  end;
  Edit1.Text := inttostr(GetTickCount - T);

  T := GetTickCount;
  for i := 1 to 1000000 do
  begin
    for k := 0 to L.Count -1 do
      GetHash2(L[k]);
  end;
  Edit2.Text := inttostr(GetTickCount - T);
end;



953 vs 797
...
Рейтинг: 0 / 0
25 сообщений из 479, страница 2 из 20
Форумы / Delphi [игнор отключен] [закрыт для гостей] / TDictionary или TList<>.BinarySearch с позиции поиска
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]