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

Это потому, что ищу в пустом словаре )
Сорри, после копи-паста забыл убрать вызов Clear.
После исправления поиск и вставка работают одинаково медленно.
...
Рейтинг: 0 / 0
24.01.2017, 08:30:02
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39421977
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
rgreat,

Делаю сейчас комплексный бенчмарк. Судя по всему, ты смог добиться действительно классных результатов
Только у тебя много классов, я так и не понял что брать.
В бенчмарке используются классы хеш-таблиц с дефолтными хешами
TDictionary, THashTable или использовать какую-то другую комбинацию кода?
...
Рейтинг: 0 / 0
18.03.2017, 00:15:40
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422019
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
SOFT FOR YOUrgreat,

Делаю сейчас комплексный бенчмарк. Судя по всему, ты смог добиться действительно классных результатовНадо-же. Я когда их пилил о особой скорости думал.
Сделаешь бенч - интересно будет глянуть.
http://www.rgreat.ru/tmp/Delphi/Test.zip

Только у тебя много классов, я так и не понял что брать.
В бенчмарке используются классы хеш-таблиц с дефолтными хешами
TDictionary, THashTable или использовать какую-то другую комбинацию кода?Если тебе нужны объекты с хешами то:
THashTable<T>
TArrayEx<T>
...
Рейтинг: 0 / 0
18.03.2017, 02:20:10
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422028
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Добавил в свой тест твою Rapid.Generics.
По моим тестам x32 так вышло:
 
Код: 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.
Preparing GUIDs...Done.
Loading Dictionary...Done.

1. Benchmark TArrayEx<Integer>
Add 10.000.000 integers. 609 msec. 32 msec (optimised).
Add 10.000 integers in 10.000.000 iterations. 688 msec.
Locate 10.000 integers in 10.000.000 iterations. 687 msec.

2. Benchmark THashTable<Integer,Integer>
Add 10.000.000 integers. 1766 msec. 657 msec (optimised).
Add 10.000 integers in 10.000.000 iterations. 265 msec.
Locate 10.000 integers in 10.000.000 iterations. 266 msec.

3. Benchmark TDictionary<Integer,Integer>
Add 10.000.000 integers. 2047 msec.
Add 10.000 integers in 10.000.000 iterations. 641 msec.
Locate 10.000 integers in 10.000.000 iterations. 516 msec.

4. Benchmark TRapidDictionary<Integer,Integer>
Add 10.000.000 integers. 437 msec.
Add 10.000 integers in 10.000.000 iterations. 172 msec.
Locate 10.000 integers in 10.000.000 iterations. 125 msec.

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

6. Benchmark THashTable<string,Integer>
Add 1.000.000 GUIDs. 812 msec. 297 msec (optimised).
Add 150844 strings in 10.000.000 iterations. 2422 msec.
Locate 150844 strings in 10.000.000 iterations. 2375 msec.

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

8. Benchmark TRapidDictionary<string,Integer>
Add 1.000.000 GUIDs. 250 msec.
Add 150844 strings in 10.000.000 iterations. 1875 msec.
Locate 150844 strings in 10.000.000 iterations. 1594 msec.

Tests complete.


На первый взгляд у тебя очень шустро вышло.

В x64 Rapid.Generics не билдится.
Ну и твой TDictionary рушится при Create. Кстати, не надо так называть классы. TDictionary уже есть в базе. :)
...
Рейтинг: 0 / 0
18.03.2017, 03:01:58
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422032
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
rgreat,

Так THashTable<T> или TArrayEx<T>? В чём отличие то? :)
И, помнится (если не путаю), у тебя были более быстрые аналоги хешей. Это в каком модуле и как применять? )
Судя по тому, что я увидел... бегло... у тебя код очень похож на стандартный TDictionary. Имеет ли смысл менять класс, может просто взять твой хеш-компаратор?

Кстати, не надо так называть классы. TDictionary уже есть в базе. :)
Так в том и суть :)
Там полные эквиваленты TDictionary, TList, TQueue, TStack, TArray, ...
...
Рейтинг: 0 / 0
18.03.2017, 04:31:31
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422182
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
SOFT FOR YOUrgreat,

Так THashTable<T> или TArrayEx<T>? В чём отличие то? :)
Первое - это словарь.
Второе - массив, с опциональным поиском в нем через хеш.

И, помнится (если не путаю), у тебя были более быстрые аналоги хешей. Это в каком модуле и как применять? )

Судя по тому, что я увидел... бегло... у тебя код очень похож на стандартный TDictionary. Имеет ли смысл менять класс, может просто взять твой хеш-компаратор?
Вот тут возьми.
https://quality.embarcadero.com/browse/RSP-16730

Так в том и суть :)
Там полные эквиваленты TDictionary, TList, TQueue, TStack, TArray, ...Рисковый подход.
...
Рейтинг: 0 / 0
18.03.2017, 16:15:45
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422236
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
rgreat,

А в чём преимущество THashTable относительно стандартного TDictionary?
Скинь сюда, пожалуйста, я там не зарегистрирован

В общем скажи наиболее эффективный способ воспользоваться твоими наработками?
THashTable + альтернативные хеши?
...
Рейтинг: 0 / 0
18.03.2017, 17:47:37
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422277
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
rgreatВот тут возьми.
https://quality.embarcadero.com/browse/RSP-16730


Там рекомендуется
Код: pascal
1.
2.
3.
4.
function GetHashCode_I4(Inst: Pointer; const Value: Integer): Integer;
 begin
 Result := Value;
 end;



Так нельзя делать. Это будет тормозить, например, если все Value имеют вид 256*i.
Имеет смысл использовать функции "взбалтывания", см. пример http://guildalfa.ru/alsha/node/32
...
Рейтинг: 0 / 0
18.03.2017, 20:24:02
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422282
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
А альтернативные хеши на дженкинсе никто не делал?
Имею ввиду реализации IEqualityComparer<T>
...
Рейтинг: 0 / 0
18.03.2017, 20:47:31
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422306
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Блин, хотел модуль Шарахова добавить, а UnicodeString нет, RawByteString-таблица основана на поле в обжекте
Нет, хватит париться )
...
Рейтинг: 0 / 0
18.03.2017, 21:40:20
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422324
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Aleksandr SharahovТак нельзя делать. Это будет тормозить, например, если все Value имеют вид 256*i.
Имеет смысл использовать функции "взбалтывания", см. пример http://guildalfa.ru/alsha/node/32 Под любой хеш используемый в виде цепочек можно подобрать такие Value что его поставит раком.

Какой смысл все усложнять?
...
Рейтинг: 0 / 0
18.03.2017, 22:25:36
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422325
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
На случайных ключах для SizeOf(Value)<=4 быстрей чем Hash:=Value нет ничего.
...
Рейтинг: 0 / 0
18.03.2017, 22:28:22
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422326
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
rgreatAleksandr SharahovТак нельзя делать. Это будет тормозить, например, если все Value имеют вид 256*i.
Имеет смысл использовать функции "взбалтывания", см. пример http://guildalfa.ru/alsha/node/32 Под любой хеш используемый в виде цепочек можно подобрать такие Value что его поставит раком.

Какой смысл все усложнять?

Мы боремся не с атакой на хеш. Это бред.
Мы боремся с регулярностью ключа. А это реальность.
...
Рейтинг: 0 / 0
18.03.2017, 22:28:29
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422327
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Хотел сказать SizeOf(Value)=4.

Там где SizeOf(Value)<4 можно соптимизировать попростому.
...
Рейтинг: 0 / 0
18.03.2017, 22:30:29
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422357
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Завершил бенчмарки для проекта Rapid.Generics:
https://github.com/d-mozulyov/Rapid.Generics

Вот бенчмарк по хеш-таблицам:
...
Рейтинг: 0 / 0
19.03.2017, 00:56:14
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422359
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Что за единицы измерения в этой таблице.

Не комильфо.
...
Рейтинг: 0 / 0
19.03.2017, 01:05:26
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422360
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Что такое 8752 и почему оно такое большое?
...
Рейтинг: 0 / 0
19.03.2017, 01:06:32
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422361
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
rgreat,

Миллисекунды
Но важны не они, а коэффициент прироста производительности
...
Рейтинг: 0 / 0
19.03.2017, 01:07:00
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422362
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Чем отличается Dictionary of RapidDictionary?
...
Рейтинг: 0 / 0
19.03.2017, 01:08:13
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422363
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
rgreat,

8,5 секунд
Видимо для Integer хеш даёт много коллизий, и для реализации стандартного TDictionary это даёт серьёзную просадку производительности при добавлении
...
Рейтинг: 0 / 0
19.03.2017, 01:10:36
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422364
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
rgreat,

TRapidDictionary не позволяет задать хеш-компаратор
Используются дефолтные и инлайнятся
...
Рейтинг: 0 / 0
19.03.2017, 01:12:05
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422365
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
Aleksandr SharahovМы боремся не с атакой на хеш. Это бред.
Мы боремся с регулярностью ключа. А это реальность.Надежней через Capacity это решить.
При условии что положение в листе ищется через n:=Value mod Capacity.

И коллизий не будет и в скорости не потеряешь.
...
Рейтинг: 0 / 0
19.03.2017, 01:14:36
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422367
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
SOFT FOR YOUrgreat,

8,5 секунд
Видимо для Integer хеш даёт много коллизий, и для реализации стандартного TDictionary это даёт серьёзную просадку производительности при добавлении
Поменяй свое
Код: pascal
1.
2.
3.
4.
5.
class function InterfaceDefaults.GetHashCode_N4(Inst: Pointer; Value: Integer): Integer;
begin
  Result := Value + ((Value shr 8) * 63689) + ((Value shr 16) * -1660269137) +
    ((Value shr 24) * -1092754919);
end;



на
Код: pascal
1.
2.
3.
4.
class function InterfaceDefaults.GetHashCode_N4(Inst: Pointer; Value: Integer): Integer;
begin
  Result := Value;
end;



Проверь разницу.
...
Рейтинг: 0 / 0
19.03.2017, 01:16:21
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422368
rgreat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rgreat
Участник
SOFT FOR YOUrgreat,

А в чём преимущество THashTable относительно стандартного TDictionary?
- Наличие доступа к данным через индекс в массиве словаря, а не только через ключ.
- Скорость работы мало страдает от коллизий хеша.
- Автоматическое очищение хранимых объектных типов при удалении (отключаемое).
- Возможность задания Default значения в случше ненахождения значения в словаре.
- BeginUpdates/EndUpdates для пакетного изменения.
- Режим хранения значений с дублирующимися ключами.
- Lock/Unlock/isLocked.
- Tag и прочие мелочи. :)

THashTable + альтернативные хеши?Идеала не существует. Кому что больше прет.
...
Рейтинг: 0 / 0
19.03.2017, 01:29:52
| Ответить | Цитировать | Написать  
TDictionary или TList<>.BinarySearch с позиции поиска
    #39422369
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
rgreatПроверь разницу.
Лень
Там исходники бенчмарка открыты, посмотри, если хочешь
Вангую, что скорость будет как у TRapidGenerics
Но я считаю, предложенный тобой способ не надёжен для универсального использования. Хотя в частных случаях годится - вполне
...
Рейтинг: 0 / 0
19.03.2017, 01:47:41
| Ответить | Цитировать | Написать  
25 сообщений из 479, страница 16 из 20
  16  все
Форумы / Delphi [игнор отключен] [закрыт для гостей] / TDictionary или TList<>.BinarySearch с позиции поиска
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=58&msg=39422032&tid=2041988]:
 0ms
get settings:
 7ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 180ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 39ms
get tp. blocked users:
 1ms
others: 195ms
total:  452ms
созд. / загр.: 452ms
x
x
Закрыть


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