ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Delphi [игнор отключен] [закрыт для гостей] / TDictionary или TList<>.BinarySearch с позиции поиска
25 сообщений из 479, страница 15 из 20
  15  все
TDictionary или TList<>.BinarySearch с позиции поиска
    #39384886
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
System.Generics.Defaults.pas

Код: pascal
1.
2.
3.
4.
function GetHashCode_I4(Inst: Pointer; const Value: Integer): Integer;
begin
  Result := THashBobJenkins.GetHashValue(Value, SizeOf(Value), 0);
end;



Такая фигня?
...
Рейтинг: 0 / 0
15.01.2017, 00:52:23
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39384896
Bred eFeM
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bred eFeM
Участник
rgreatТакая фигня?Угу
...
Рейтинг: 0 / 0
15.01.2017, 03:26:40
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39384919
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
rgreatЭти дятлы расчитывали(!) бобом дженкинсом(!) хэши для 1-4 байтных целых.
Они не дятлы, просто для универсального, во всех отношениях, TDictionary, по дефолту, выбран обладающий хорошим лавинным эффектом (читай, подходящий для всех типов ключей) Дженкинс. При этом предоставлен механизм замены компарера, где можно реализовать какой угодно хеш. Вот где они налажали, так это в установлении Capacity. Кстати, когда я смотрел на применение словаря в VCL/FMX, то не видел мест, где используются кастомные компареры.
...
Рейтинг: 0 / 0
15.01.2017, 09:07:22
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39384991
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Зачем вообще нужна хеш функция для integer?
...
Рейтинг: 0 / 0
15.01.2017, 14:23:29
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385020
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
rgreatЗачем вообще нужна хеш функция для integer?
Я не знаю чем руководствовались в абракадабре, но думаю, что они ориентировались на средний вариант. Например, если мы берём в качестве ключа integer и заполняем таблицу миллионом последовательных ключей, то простое проецирование ключа на хеш даёт хороший результат. Но если мы вставляем миллион рандомных ключей, то производительность деградирует в разы, тогда, как хеш Дженкинса даёт стабильно одинаковый результат. Потестируй у себя, может что интересное получится. У меня, на AMD, Дженкинс немногим медленне худшего случая с рандомными ключами, вдруг у тебя быстрее окажется :)

Кстати, тут ещё могу привести пример, когда медленный Дженкинс уделывает быстрого Седжвика. Я тестировал свою таблицу на nextgen-компиляторе (XE5-6), и несмотря на более быстрый хеш Седжвика и более выгодную организацию данных она совсем немого но опережала дефолтный словарь с Дженкинсом. На последних версиях (XE8-10) моя таблица стабильно медленне дефолтного словаря, хотя тоже очень не на много. После того, как я заменил у себя Седжвика на Дженкинса, моя таблица снова стала быстрее на nextgen, несмотря на то, что Дженкинс медленне. Разница только в компиляторе и архитектуре процессора.
...
Рейтинг: 0 / 0
15.01.2017, 16:07:06
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385050
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
Раз уж пошла такая пьянка... Вот набор целочисленных ключей, на которых медленный Дженкинс рвёт в клочья прямое проецирование ключа на хеш:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
  For Index := 0 To High(Integer) Do
   If Index And (2097152 - 1) < (1000000 - 5000) Then
    Begin

     dict.Add(index, index);

     If dict.Count = 1000000 Then
      Break;

    End;


Понятное дело, что пример искусственный, но в жизни-то всякое бывает. На этом наборе ключей скорость поиска с Дженкинсом в 55 раз быстрее проецирования, а скорость вставки в 61 раз быстрее. А всё что мы сделали, это сосредоточили входы 1 млн. ключей в первых 995 тыс. яцеек таблицы. Таким образом на проецировании получается 5 тыс. коллизий на входе в таблицу, а у Дженкинса их более 200 тыс., но за счёт хорошего распределения у него очень короткие цепочки, что в результате позволяет ему выиграть.
...
Рейтинг: 0 / 0
15.01.2017, 18:16:05
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385060
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Kazantsev AlexeyРаз уж пошла такая пьянка... Вот набор целочисленных ключей, на которых медленный Дженкинс рвёт в клочья прямое проецирование ключа на хеш:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
  For Index := 0 To High(Integer) Do
   If Index And (2097152 - 1) < (1000000 - 5000) Then
    Begin

     dict.Add(index, index);

     If dict.Count = 1000000 Then
      Break;

    End;


Понятное дело, что пример искусственный, но в жизни-то всякое бывает. На этом наборе ключей скорость поиска с Дженкинсом в 55 раз быстрее проецирования, а скорость вставки в 61 раз быстрее. А всё что мы сделали, это сосредоточили входы 1 млн. ключей в первых 995 тыс. яцеек таблицы. Таким образом на проецировании получается 5 тыс. коллизий на входе в таблицу, а у Дженкинса их более 200 тыс., но за счёт хорошего распределения у него очень короткие цепочки, что в результате позволяет ему выиграть.Я в восхищении от твоей способности подобрать такой тест кейс.
Но достаточно поменять в нем 1 цифру и Дженкинс опять проиграет. :)
...
Рейтинг: 0 / 0
15.01.2017, 18:41:21
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385061
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Kazantsev AlexeyrgreatЗачем вообще нужна хеш функция для integer?
Я не знаю чем руководствовались в абракадабре, но думаю, что они ориентировались на средний вариант. Например, если мы берём в качестве ключа integer и заполняем таблицу миллионом последовательных ключей, то простое проецирование ключа на хеш даёт хороший результат. Но если мы вставляем миллион рандомных ключей, то производительность деградирует в разы, тогда, как хеш Дженкинса даёт стабильно одинаковый результат. Потестируй у себя, может что интересное получится. У меня, на AMD, Дженкинс немногим медленне худшего случая с рандомными ключами, вдруг у тебя быстрее окажется :)
Вот такой код у меня стабильно медленней на дженкинсе.

Код: pascal
1.
2.
3.
    for i:=0 to 9999999 do begin
      A.AddOrSetValue(Random(10000),0);
    end;
...
Рейтинг: 0 / 0
15.01.2017, 18:54:54
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385063
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
rgreatНо достаточно поменять в нем 1 цифру и Дженкинс опять проиграет. :)
Это и понятно, но замена той же цифры может затормозить проецирование вообще в бесконечность. Вот тебе готовый сценарий для DOS-атаки, на таблицу ;)

rgreatВот такой код у меня стабильно медленней на дженкинсе.
На сколько, в процентном отношении?
...
Рейтинг: 0 / 0
15.01.2017, 19:00:15
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385066
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
rgreat,

Кстати, если мне не изменяет память, у тебя таблица разруливала коллизии методом цепочек. Если всё так, то её этот вариант радикально затормозить не должен.
...
Рейтинг: 0 / 0
15.01.2017, 19:05:53
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385069
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Kazantsev Alexeyrgreat,

Кстати, если мне не изменяет память, у тебя таблица разруливала коллизии методом цепочек. Если всё так, то её этот вариант радикально затормозить не должен.Угу. Она у меня скажем так "стабильно не очень быстрая".
Соседние коллизии друг на друга не влияют, но зато идет высокая нагрузка на менеджер памяти.
...
Рейтинг: 0 / 0
15.01.2017, 19:12:32
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385070
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Kazantsev AlexeyНа сколько, в процентном отношении?

Дженкинс: Add 10.000 integers in 10.000.000 iterations. 625 msec
Без него: Add 10.000 integers in 10.000.000 iterations. 312 msec.

в 2 раза.
...
Рейтинг: 0 / 0
15.01.2017, 19:14:10
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385072
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
rgreatСоседние коллизии друг на друга не влияют, но зато идет высокая нагрузка на менеджер памяти.
На nextgen не проверял, а то там с менеджером совсем плохо?

rgreatв 2 раза.
О! У меня всего 20-25%
...
Рейтинг: 0 / 0
15.01.2017, 19:18:11
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385084
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
Kazantsev AlexeyО! У меня всего 20-25%
Это от того, что у меня верхняя граница High(Integer);
...
Рейтинг: 0 / 0
15.01.2017, 19:48:34
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385086
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Kazantsev AlexeyKazantsev AlexeyО! У меня всего 20-25%
Это от того, что у меня верхняя граница High(Integer);Похоже на то.
Но этот случай для ключей не очень вероятный.
...
Рейтинг: 0 / 0
15.01.2017, 19:53:55
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385089
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Kazantsev AlexeyНа nextgen не проверял, а то там с менеджером совсем плохо?
Думаю там многое будет зависить от конкретной реализации в OS. Да и разброс в железе велик.
Замучаешься выводить закономерности.

Небось придется делать свой микро-менеджер памяти внутри цепочки.
...
Рейтинг: 0 / 0
15.01.2017, 19:56:05
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385090
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Вот мой тестовый пример.

http://www.rgreat.ru/tmp/Test.zip

Я там базовые модули Generics.* переименовал в Indexes.* для простоты.

Для теста достаточно в Indexes.Collections.Pas поменять Uses

Код: pascal
1.
2.
3.
4.
5.
uses
  System.Types,
  Indexes.Defaults,
//  Generics.Defaults,
  System.SysUtils;
...
Рейтинг: 0 / 0
15.01.2017, 19:58:17
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385091
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
У меня с базовыми TDictionary результат пока такой:

 
Код: plaintext
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.
Preparing GUIDs...Done.
Loading Dictionary...Done.

1. Logic Tests TArrayEx<Integer>
   0;1;1;1;1;2;2;2;2;2;2;3;3;3;3;3;3;4;4;4;4;4;5;5;5;5;5;5;6;6;6;7;7;7;8;8;8;8;8;9
   Length of array A = 40
   0;1;2;3;4;5;6;7;8;9
   Length of array B = 10
   These are equal: 0
   B in A: -1
   C:=A+B
   0;1;1;1;1;2;2;2;2;2;2;3;3;3;3;3;3;4;4;4;4;4;5;5;5;5;5;5;6;6;6;7;7;7;8;8;8;8;8;9;0;1;2;3;4;5;6;7;8;9
   Length of array C = 50
   Value "5" found 7 times in array C, at indexes = [22;23;24;25;26;27;45]
   Implicit cast to array passed.

2. Benchmark TArrayEx<Integer>
   Add 10.000.000 integers. 578 msec. 31 msec (optimised).
   Add 10.000 integers in 10.000.000 iterations. 672 msec.
   Locate 10.000 integers in 10.000.000 iterations. 671 msec.

3. Benchmark THashTable<Integer,Integer>
   Add 10.000.000 integers. 1688 msec. 687 msec (optimised).
   Add 10.000 integers in 10.000.000 iterations. 313 msec.
   Locate 10.000 integers in 10.000.000 iterations. 281 msec.

4. Benchmark TDictionary<Integer,Integer>
   Add 10.000.000 integers. 1984 msec.
   Add 10.000 integers in 10.000.000 iterations. 641 msec.
   Locate 10.000 integers in 10.000.000 iterations. 500 msec.

5. Benchmark TArrayEx<string>
   Add 1.000.000 GUIDs. 93 msec. 31 msec (optimised).
   Add 150844 strings in 10.000.000 iterations. 2890 msec.
   Locate 150844 strings in 10.000.000 iterations. 2813 msec.

6. Benchmark THashTable<string,Integer>
   Add 1.000.000 GUIDs. 578 msec. 235 msec (optimised).
   Add 150844 strings in 10.000.000 iterations. 2453 msec.
   Locate 150844 strings in 10.000.000 iterations. 2406 msec.

7. Benchmark TDictionary<string,Integer>
   Add 1.000.000 GUIDs. 547 msec.
   Add 150844 strings in 10.000.000 iterations. 2000 msec.
   Locate 150844 strings in 10.000.000 iterations. 1688 msec.

Tests complete.

Но там еще есть чего оптимизировать.
...
Рейтинг: 0 / 0
15.01.2017, 20:00:32
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385095
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
TDictionary без Дженкинса:

 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
Preparing GUIDs...Done.
Loading Dictionary...Done.

1. Benchmark TDictionary<Integer,Integer>
   Add 10.000.000 integers. 641 msec.
   Add 10.000 integers in 10.000.000 iterations. 297 msec.
   Locate 10.000 integers in 10.000.000 iterations. 218 msec.

2. Benchmark TDictionary<string,Integer>
   Add 1.000.000 GUIDs. 454 msec.
   Add 150844 strings in 10.000.000 iterations. 1906 msec.
   Locate 150844 strings in 10.000.000 iterations. 1578 msec.

Tests complete.
...
Рейтинг: 0 / 0
15.01.2017, 20:06:13
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385097
Kazantsev Alexey
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Kazantsev Alexey
Участник
rgreatДумаю там многое будет зависить от конкретной реализации в OS. Да и разброс в железе велик.
Просто там FastMM'а нет :)

rgreatНебось придется делать свой микро-менеджер памяти внутри цепочки.
Мне в паре мест пришлось менять алгоритм работы с памятью :)
...
Рейтинг: 0 / 0
15.01.2017, 20:07:44
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385099
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Kazantsev AlexeyПросто там FastMM'а нет :)Потому и будет. :)

Может через пару лет и FastMM допилят для NextGen? ;)
...
Рейтинг: 0 / 0
15.01.2017, 20:11:27
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39385526
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Проголосуйте, кому не лень.

https://quality.embarcadero.com/browse/RSP-16730
...
Рейтинг: 0 / 0
16.01.2017, 15:45:43
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39389954
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
обновил статью и исходник в свете последних обсуждений
...
Рейтинг: 0 / 0
24.01.2017, 00:04:08
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39389964
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
rgreat,

на таком же тесте с моим словарем на E6850 времена такие
1357
203
78

 
Код: 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.
procedure TForm1.Button2Click(Sender: TObject);
var
  OD: TShaObjectDictionary;
  i, j: integer;
  t: cardinal;
begin;
  len:=10000000;
  OD:=TShaObjectDictionary.Create;

  t:=GetTickCount;
  for i:=0 to len-1 do OD.Add(i, pointer(i));
  t:=GetTickCount-t;
  Memo1.Lines.Add(IntToStr(t)); //1357ms
  OD.Clear;

  t:=GetTickCount;
  for i:=0 to len-1 do OD.Add(Random(10000), 0);
  t:=GetTickCount-t;
  Memo1.Lines.Add(IntToStr(t)); //203ms
  OD.Clear;

  t:=GetTickCount;
  for i:=0 to len-1 do OD.Find(Random(10000));
  t:=GetTickCount-t;
  Memo1.Lines.Add(IntToStr(t)); //78ms
  OD.Clear;

  OD.Free;
  end;

...
Рейтинг: 0 / 0
24.01.2017, 00:55:07
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39389991
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Без сравнения с другими мало о чем говорит, кроме того что поиск у тебя гораздо быстрей добавления.
...
Рейтинг: 0 / 0
24.01.2017, 05:38:37
| Ответить | Цитировать | Написать  
25 сообщений из 479, страница 15 из 20
  15  все
Форумы / Delphi [игнор отключен] [закрыт для гостей] / TDictionary или TList<>.BinarySearch с позиции поиска
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=58&msg=39384896&tid=2041988]:
 0ms
get settings:
 9ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 177ms
get topic data:
 11ms
get forum data:
 2ms
get page messages:
 52ms
get tp. blocked users:
 1ms
others: 227ms
total:  500ms
созд. / загр.: 500ms
x
x
Закрыть


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