Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Delphi Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 5101
Aleksandr Sharahov,

Да.
29 мар 21, 16:51    [22301543]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 2070
Kazantsev Alexey,

там еще про заголовки непонятка
29 мар 21, 16:52    [22301544]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 5101
Aleksandr Sharahov
вставляем 3 раза по 3 дубликата

Нет, вставляются 100K уникальных ключей 3 раза.

Aleksandr Sharahov
непонятно как выглядят заголовки процедур?

Не понял...
29 мар 21, 16:53    [22301546]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 2070
Kazantsev Alexey,

по идее хеш-таблица не содержит дубликатов,
поэтому возникают 2 вопроса:
- есть ли возможность хранить дубликаты в твоей таблице?
- если есть, то каков API?
29 мар 21, 16:57    [22301548]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 5101
Aleksandr Sharahov,

Да, хранить дубликаты можно.
//
function TPtrSet.GetPtrHash(APtr : Pointer) : THash;
begin

 Cardinal(Result) := {PtrUInt(APtr);{ Shr 4;//}BJ32BitFAHash(PtrUInt(APtr));

end;
//

//
procedure TPtrSet.Add(APtr : Pointer);
var

 ctx : TPtrSet.TSearchContext;

begin

 EnsureGrowth;

 if FindFirst(GetPtrHash(APtr), ctx) then
  repeat
  until not FindNext(ctx);

 RegisterItem(ctx){$IF SizeOf(Pointer) = 8}

                   .Data := PtrUInt(APtr) Shr 32;

                  {$IFEND};

end;
//

//
function TPtrSet.Remove(APtr : Pointer) : Boolean;
var

 ctx  : TPtrSet.TSearchContext;
 ictx : TPtrSet.TSearchContext;

 {$IF SizeOf(Pointer) = 8}

  data : Cardinal;

 {$IFEND}

begin

 Result := False;

 ictx.Items := nil;

 if FindFirst(GetPtrHash(APtr), ctx) then
  begin

   {$IF SizeOf(Pointer) = 4}

    ictx := ctx;

    if FindNext(ctx) then
     Result := true;

   {$ELSEIF SizeOf(Pointer) = 8}

    data := PtrUInt(APtr) Shr 32;

    if ctx.Item.Data = data then
     begin

      ictx := ctx;

      while FindNext(ctx) do
       if ctx.Item.Data = data then
        begin

         Result := true;
         break;

        end;

     end;

   {$ELSE}

    {$MESSAGE ERROR 'Unknown situation'}

   {$IFEND}

  end;

 if Assigned(ictx.Items) then
  UnregisterItem(ictx);

end;
//

//
function TPtrSet.Contains(APtr : Pointer) : Boolean;
var

 ctx : TPtrSet.TSearchContext;

begin

 result := False;

 if FindFirst(GetPtrHash(APtr), ctx) then

  {$IF SizeOf(Pointer) = 4}

   Result := True;

  {$ELSEIF SizeOf(Pointer) = 8}

   repeat

    if ctx.Item.Data = PtrUInt(APtr) Shr 32 then
     begin

      Result := True;

      Break;

     end;

   until not FindNext(ctx);

  {$ELSE}

   {$MESSAGE ERROR 'Unknown situation'}

  {$IFEND}

end;
//


Удаление делается по условию топикстартера, т.е. функция удаления возвращает булево в зависимости от наличия в таблице дубликатов ключа.
29 мар 21, 17:06    [22301554]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 2070
Kazantsev Alexey,

понятно.

На мой взгляд, как-то костыльно хранить дубликаты с доступом только к первому,
то топикстартеру видней, конечно.
29 мар 21, 17:13    [22301559]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 5101
Aleksandr Sharahov,

Нет смысла делать доступ к каждому из дубликатов, когда нет ассоциированных данных.
29 мар 21, 17:19    [22301567]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 2070
Kazantsev Alexey,

в данном случае - да (дубликаты просто выполняют роль счетчика),
но в общем случае это не так.

Сообщение было отредактировано: 29 мар 21, 17:19
29 мар 21, 17:24    [22301572]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 5101
О! Нашёл ошибку в удалении
29 мар 21, 17:36    [22301582]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
Kazantsev Alexey,

ну а если добавить все "красивости": KeyNotify, ValueNotify (с виртуальностью и с поддержкой OnKeyNotify OnValueNotify естественно), стандартный IComparer<T> а не статик функции.
взять простые типы вроде Integer, взять данные без существенных коллизий (ну хоть последовательно от 1 до млн)

и какая будет разница?

Сообщение было отредактировано: 29 мар 21, 20:00
29 мар 21, 20:07    [22301672]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 5101
kealon(Ruslan),

Дефолтный словарь <integer, integer>, 1M элементов вставка: 221.
Таблица с робингудом повторяющая обес словаря с виртуализованными вызовами нотификаций и дефолтным компарером: 154. Если увеличить фактор заполнения таблицы до 0.97, то скорость снижается до: 207, но и расход памяти сокращается в 2 раза.
29 мар 21, 21:23    [22301694]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 3170
Коллеги
Мы так и не ответили на вопрос, почему плохая хеш-функция, дающая большое количество коллизий, в итоге даёт многократный прирост
29 мар 21, 22:17    [22301715]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 5101
SOFT FOR YOU,

Прирост даёт, как раз, функция не имеющая коллизий (даже в 64-битном тесте все указатели не выходят за пределы 32 бит).

Сообщение было отредактировано: 29 мар 21, 22:29
29 мар 21, 22:37    [22301722]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 3170
Kazantsev Alexey,

BJ32BitFAHash даёт хороший результат
Но NativeUInt(P) and ACapacityMask работает в полтора раза быстрее

Посмотри вот это сообщение 22301081

Для тех, кто пропустил
Эксперименты с архивом hash_table_2.zip, который указан в 22301038
29 мар 21, 22:47    [22301725]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 5101
SOFT FOR YOU
Но NativeUInt(P) and ACapacityMask работает в полтора раза быстрее

Я об этом и говорю. NativeUInt(P) - не имеет коллизий в твоём тесте.
29 мар 21, 22:55    [22301728]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 3170
Kazantsev Alexey,

На 32 битах гранулярность указателей 8, на 64 - вообще 16
Это значит, что для всех указателей как минимум 3 младших бита равны нулю
Это значит, что NativeUInt(P) даёт пустоты в 7 пунктов, а, следовательно, огромное число коллизий
29 мар 21, 23:04    [22301734]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 5101
SOFT FOR YOU,

Это не коллизии хеш-функции. Это даже не коллизии входов в таблицу, это ухудшение распределения.

Вот распределение на робингуде при проекции указателя на хеш (300K элементов, уникальных 100K):

К сообщению приложен файл. Размер - 19Kb
29 мар 21, 23:31    [22301742]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 5101
А вот так выглядит распределение на робингуде при проекции и сдвиге:

К сообщению приложен файл. Размер - 3Kb
29 мар 21, 23:32    [22301743]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 2070
SOFT FOR YOU
...огромное число коллизий


а после каждого слота с коллизиями - огромное количество свободных слотов, куда они прекрасно лягут
29 мар 21, 23:32    [22301744]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 5101
Кстати, прямая проекция будет страдать от большого количества дубликатов сильнее, чем использование хеш-функции.
29 мар 21, 23:36    [22301748]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 3170
Aleksandr Sharahov,

Ну с таким же успехом можно просто возвращать 0
Тогда они ещё лучше лягут

Сообщение было отредактировано: 29 мар 21, 23:32
29 мар 21, 23:39    [22301751]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Aleksandr Sharahov
Member

Откуда: Москва
Сообщений: 2070
SOFT FOR YOU,

вот же меня опять угораздило, ушел
29 мар 21, 23:44    [22301752]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 5101
Aleksandr Sharahov,

29 мар 21, 23:45    [22301753]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
Kazantsev Alexey
kealon(Ruslan),

Дефолтный словарь <integer, integer>, 1M элементов вставка: 221.
Таблица с робингудом повторяющая обес словаря с виртуализованными вызовами нотификаций и дефолтным компарером: 154. Если увеличить фактор заполнения таблицы до 0.97, то скорость снижается до: 207, но и расход памяти сокращается в 2 раза.
хм,нашёл описание - это ж мой вариант с отсортированными значениями, такой вариант действительно будет не хуже, однако он уже таблицу хэшей срезал.
30 мар 21, 10:15    [22301852]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
SOFT FOR YOU
Kazantsev Alexey,

На 32 битах гранулярность указателей 8, на 64 - вообще 16
Это значит, что для всех указателей как минимум 3 младших бита равны нулю
Это значит, что NativeUInt(P) даёт пустоты в 7 пунктов, а, следовательно, огромное число коллизий


SOFT FOR YOU
тут вот вполне сносное объяснение твоему вопросу
автор
Схемы открытой адресации также предъявляют более жесткие требования к хэш-функции: помимо более равномерного распределения ключей по сегментам, функция также должна минимизировать кластеризацию последовательных хэш-значений в порядке проверки.
как раз то, что я тебе писал в 22301251

ещё у майла интересная статейка была
30 мар 21, 10:18    [22301854]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 [2] 3   вперед  Ctrl      все
Все форумы / Delphi Ответить