Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Да. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 16:51 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Kazantsev Alexey, там еще про заголовки непонятка ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 16:52 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov вставляем 3 раза по 3 дубликата Нет, вставляются 100K уникальных ключей 3 раза. Aleksandr Sharahov непонятно как выглядят заголовки процедур? Не понял... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 16:53 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Kazantsev Alexey, по идее хеш-таблица не содержит дубликатов, поэтому возникают 2 вопроса: - есть ли возможность хранить дубликаты в твоей таблице? - если есть, то каков API? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 16:57 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Да, хранить дубликаты можно. Код: 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. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. Удаление делается по условию топикстартера, т.е. функция удаления возвращает булево в зависимости от наличия в таблице дубликатов ключа. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 17:06 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Kazantsev Alexey, понятно. На мой взгляд, как-то костыльно хранить дубликаты с доступом только к первому, то топикстартеру видней, конечно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 17:13 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Нет смысла делать доступ к каждому из дубликатов, когда нет ассоциированных данных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 17:19 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Kazantsev Alexey, в данном случае - да (дубликаты просто выполняют роль счетчика), но в общем случае это не так. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 17:24 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
О! Нашёл ошибку в удалении ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 17:36 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Kazantsev Alexey, ну а если добавить все "красивости": KeyNotify, ValueNotify (с виртуальностью и с поддержкой OnKeyNotify OnValueNotify естественно), стандартный IComparer<T> а не статик функции. взять простые типы вроде Integer, взять данные без существенных коллизий (ну хоть последовательно от 1 до млн) и какая будет разница? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 20:07 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan), Дефолтный словарь <integer, integer>, 1M элементов вставка: 221. Таблица с робингудом повторяющая обес словаря с виртуализованными вызовами нотификаций и дефолтным компарером: 154. Если увеличить фактор заполнения таблицы до 0.97, то скорость снижается до: 207, но и расход памяти сокращается в 2 раза. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 21:23 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Коллеги Мы так и не ответили на вопрос, почему плохая хеш-функция, дающая большое количество коллизий, в итоге даёт многократный прирост ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 22:17 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Прирост даёт, как раз, функция не имеющая коллизий (даже в 64-битном тесте все указатели не выходят за пределы 32 бит). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 22:37 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Kazantsev Alexey, BJ32BitFAHash даёт хороший результат Но NativeUInt(P) and ACapacityMask работает в полтора раза быстрее Посмотри вот это сообщение 22301081 Для тех, кто пропустил Эксперименты с архивом hash_table_2.zip, который указан в 22301038 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 22:47 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU Но NativeUInt(P) and ACapacityMask работает в полтора раза быстрее Я об этом и говорю. NativeUInt(P) - не имеет коллизий в твоём тесте. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 22:55 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Kazantsev Alexey, На 32 битах гранулярность указателей 8, на 64 - вообще 16 Это значит, что для всех указателей как минимум 3 младших бита равны нулю Это значит, что NativeUInt(P) даёт пустоты в 7 пунктов, а, следовательно, огромное число коллизий ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 23:04 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Это не коллизии хеш-функции. Это даже не коллизии входов в таблицу, это ухудшение распределения. Вот распределение на робингуде при проекции указателя на хеш (300K элементов, уникальных 100K): ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 23:31 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
А вот так выглядит распределение на робингуде при проекции и сдвиге: ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 23:32 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU ...огромное число коллизий а после каждого слота с коллизиями - огромное количество свободных слотов, куда они прекрасно лягут ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 23:32 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Кстати, прямая проекция будет страдать от большого количества дубликатов сильнее, чем использование хеш-функции. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 23:36 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, Ну с таким же успехом можно просто возвращать 0 Тогда они ещё лучше лягут ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 23:39 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, вот же меня опять угораздило, ушел ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 23:44 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Aleksandr Sharahov, ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 29.03.2021, 23:45 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
Kazantsev Alexey kealon(Ruslan), Дефолтный словарь <integer, integer>, 1M элементов вставка: 221. Таблица с робингудом повторяющая обес словаря с виртуализованными вызовами нотификаций и дефолтным компарером: 154. Если увеличить фактор заполнения таблицы до 0.97, то скорость снижается до: 207, но и расход памяти сокращается в 2 раза. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.03.2021, 10:15 |
|
||
|
Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU Kazantsev Alexey, На 32 битах гранулярность указателей 8, на 64 - вообще 16 Это значит, что для всех указателей как минимум 3 младших бита равны нулю Это значит, что NativeUInt(P) даёт пустоты в 7 пунктов, а, следовательно, огромное число коллизий SOFT FOR YOU тут вот вполне сносное объяснение твоему вопросу авторСхемы открытой адресации также предъявляют более жесткие требования к хэш-функции: помимо более равномерного распределения ключей по сегментам, функция также должна минимизировать кластеризацию последовательных хэш-значений в порядке проверки. как раз то, что я тебе писал в 22301251 ещё у майла интересная статейка была ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 30.03.2021, 10:18 |
|
||
|
|

start [/forum/topic.php?fid=58&msg=40057897&tid=2037343]: |
0ms |
get settings: |
11ms |
get forum list: |
12ms |
check forum access: |
8ms |
check topic access: |
8ms |
track hit: |
48ms |
get topic data: |
10ms |
get forum data: |
2ms |
get page messages: |
58ms |
get tp. blocked users: |
2ms |
| others: | 11ms |
| total: | 170ms |

| 0 / 0 |
