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

Откуда:
Сообщений: 3170
Есть у меня тут задача, накидал вариант решения
Если коротко, условие задачи выглядит примерно так:
  • Должно быть хранилище указателей
  • Есть всего 3 операции: добавить, удалить и итератор
  • Возможны дубликаты (не часто), функция удаления должна возвращать, остался ли дубликат
  • Потребление оперативной памяти желательно свести к минимуму
  • Размер задействованной памяти должен быть кратен 16 байтам на 64 битах

В общем всё сводится вроде как к linear probing хеш-таблице
Раньше я использовал только списки, там всё понятно. Здесь могут быть нюансы
В общем почитал статью А. Шарахова, исходники дельфийского словаря
И получилась примерно такая концепция:
- размер равен степени 2 минус 1 (минимальный размер 7)
- бакет это некоторое виртуальное место, куда можно положить элемент, количество бакетов равно размеру таблицы
- индекс это позиция, в которой хранится элемент
- бакет может быть меньше индекса, это значит, что было несколько элементов с одним бакетом
- если бакет сильно больше индекса, значит было переполнение в конце
- при удалении возвращается True если есть дубликат


Я зафигачил тестовый проект, где есть проверки: элементарные в случае Release и доскональные в случае Debug
Смущает производительность. Даже 100k элементов без дубликатов считаются 1,5 секунды в Release. С дубликатами - уже 6 секунд.
В общем есть ощущение, что я что-то делаю не так и производительность должна быть на порядок выше. Смотрите аттач

Немного кода под катом:
+
type
  PHashTable = ^THashTable;
  THashTable = record
    Capacity: Cardinal;
    Count: Cardinal;
    Items: array[0..0] of Pointer;
  end;

const
  HASH_SHIFT = 6;
  HASH_EMPTY = Pointer(High(NativeUInt));
  HASH_MINSIZE = 7;

function HashTableGrowThreshold(const ACapacity: NativeUInt): NativeUInt; inline;
var
  LPow2: NativeUInt;
begin
  LPow2 := (ACapacity + 1);
  Result := (LPow2 shr 2) + (LPow2 shr 1);
end;

function HashTableFixBucket(const ABucket: NativeUInt; const ACapacity: NativeUInt): NativeUInt; inline;
begin
  Result := ABucket;
  if (Result = ACapacity) then
    Result := 0;
end;

function HashTableBucketIncrement(const ABucket: NativeUInt; const ACapacity: NativeUInt): NativeUInt; inline;
begin
  Result := HashTableFixBucket(ABucket + 1, ACapacity);
end;

function HashTableBucket(const P: Pointer; const ACapacity: NativeUInt): NativeUInt; inline;
begin
  Result := HashTableFixBucket((NativeUInt(P) shr HASH_SHIFT) and ACapacity, ACapacity);
end;

function HashTableIndex(const AItems: PPointer; const ACapacity: NativeUInt; const P: Pointer;
  const AAddMode: Boolean): NativeUInt;
var
  LValue: Pointer;
  LSourceBucket, LPrevBucket, LBucket: NativeUInt;
begin
  Result := HashTableBucket(P, ACapacity);

  // наиболее благоприятный случай
  LValue := AItems[Result];
  if (LValue = HASH_EMPTY) or (LValue = P) then
    Exit;

  // пропускаем лишние большие бакеты если было переполнение
  // или находим свободное место
  LSourceBucket := Result;
  LBucket := HashTableBucket(LValue, ACapacity);
  if (LBucket > LSourceBucket) then
  repeat
    LPrevBucket := LBucket;

    Result := HashTableBucketIncrement(Result, ACapacity);
    LValue := AItems[Result];
    if (LValue = HASH_EMPTY) then
      Exit;
    LBucket := HashTableBucket(LValue, ACapacity);
  until (LBucket < LPrevBucket);

  // пропускаем лишние малые бакеты если было переполнение
  // или находим свободное место
  if (AAddMode) then
  begin
    repeat
      if (LBucket >= LSourceBucket) then
        Exit;

      Result := HashTableBucketIncrement(Result, ACapacity);
      LValue := AItems[Result];
      if (LValue = HASH_EMPTY) then
        Exit;
      LPrevBucket := LBucket;
      LBucket := HashTableBucket(LValue, ACapacity);
      if (LPrevBucket > LBucket) then
        Break;
    until (False);
  end else
  begin
    repeat
      if (LBucket > LSourceBucket) or (LValue = P) then
        Exit;

      Result := HashTableBucketIncrement(Result, ACapacity);
      LValue := AItems[Result];
      if (LValue = HASH_EMPTY) then
        Exit;
      LPrevBucket := LBucket;
      LBucket := HashTableBucket(LValue, ACapacity);
      if (LPrevBucket > LBucket) then
        Break;
    until (False);
  end;
end;

procedure HashTableInsert(const AItems: PPointer; const ACapacity, AIndex: NativeUInt; const P: Pointer);
var
  LIndex: NativeUInt;
  LValue, LOldValue: Pointer;
begin
  LIndex := AIndex;
  LValue := P;

  repeat
    LOldValue := AItems[LIndex];
    AItems[LIndex] := LValue;
    if (LOldValue = HASH_EMPTY) then
      Exit;

    LValue := LOldValue;
    LIndex := HashTableBucketIncrement(LIndex, ACapacity);
  until (False);
end;

procedure HashTableAdd(var AHashTable: PHashTable; const P: Pointer);
var
  LCapacity: NativeUInt;
begin
  LCapacity := AHashTable.Capacity;
  if (AHashTable.Count = HashTableGrowThreshold(LCapacity)) then
  begin
    LCapacity := (LCapacity + 1) shl 1 - 1;
    HashTableRehash(AHashTable, LCapacity);
  end;

  Inc(AHashTable.Count);
  HashTableInsert(@AHashTable.Items[0], LCapacity,
    HashTableIndex(@AHashTable.Items[0], LCapacity, P, True), P);
end;

function HashTableRemove(var AHashTable: PHashTable; const P: Pointer): Boolean;
var
  LItems: PPointer;
  LCapacity: NativeUInt;
  LIndex, LNextIndex: NativeUInt;
  LValue: Pointer;
begin
  LItems := @AHashTable.Items[0];
  LCapacity := AHashTable.Capacity;
  LIndex := HashTableIndex(LItems, LCapacity, P, False);
  if (LItems[LIndex] <> P) then
    Exit(False);

  Result := False;
  repeat
    LNextIndex := HashTableBucketIncrement(LIndex, LCapacity);
    LValue := LItems[LNextIndex];

    if (LValue = HASH_EMPTY) then
      Break;

    if (LValue = P) then
      Result := True;

    if (LNextIndex = HashTableBucket(LValue, LCapacity)) then
      Break;

    LItems[LIndex] := LValue;
    LIndex := LNextIndex;
  until (False);
  LItems[LIndex] := HASH_EMPTY;

  Dec(AHashTable.Count);
  if (LCapacity <> HASH_MINSIZE) then
  begin
    LCapacity := LCapacity shr 1;
    if (AHashTable.Count = HashTableGrowThreshold(LCapacity)) then
      HashTableRehash(AHashTable, LCapacity);
  end;
end;


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

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

Там к статье исходники прилагаются, взял бы и не парился.

P.S. Как будет время планирую еще ускорить для очень больших таблиц, но это не твой случай.
28 мар 21, 02:23    [22300974]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
SOFT FOR YOU
Member

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

Во-первых, у тебя там юзается другая организация данных
Во-вторых, не рассчитана на дубликаты
В-третьих, у тебя там используются индексы как признак пустой ячейки. У меня могут быть «спец» указатели, совпадающие с индексом
28 мар 21, 02:47    [22300976]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Aleksandr Sharahov
Member

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

Во-первых, у тебя там юзается другая организация данных
Во-вторых, не рассчитана на дубликаты
В-третьих, у тебя там используются индексы как признак пустой ячейки. У меня могут быть «спец» указатели, совпадающие с индексом


1. Ну да, другая, более быстрая, тебе же это надо?
2. Рассчитана, но не по-твоему. А ты правда не знаешь, как сделать их различимыми или как хранить цепочку дубликатоа?
3. И как одно помешает другому?

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

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

Посмотри код
Скажи, что там не так
Потому что вроде бы всё так

Первый приоритет - это потребление памяти
Производительность - по остаточному принципу
Но 1/4 свободных ячеек - норм
28 мар 21, 11:23    [22301020]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 3170
В несколько раз ускорил, когда сделал
const
  HASH_SHIFT = 4;


Но всё равно мне кажется не то )
28 мар 21, 12:07    [22301025]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 3170
Сделал размер степени двойки

100k в Release считается за 400мс
Вроде неплохо
Но стоит добавить хотя бы по одному дубликату - проседает почти до 2 сек

К сообщению приложен файл (hash_table_2.zip - 9Kb) cкачать
28 мар 21, 12:52    [22301038]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 5101
// http://burtleburtle.net/bob/hash/integer.html
Function BJ32BitFAHash(AValue : Cardinal) : Cardinal;
Begin

 Result := (AValue  +  $7ED55D16)  +  (AValue Shl 12);
 Result := (Result Xor $C761C23C) Xor (Result Shr 19);
 Result := (Result  +  $165667B1)  +  (Result Shl 5);
 Result := (Result  +  $D3A2646C) Xor (Result Shl 9);
 Result := (Result  +  $FD7046C5)  +  (Result Shl 3);
 Result := (Result Xor $B55A4F09) Xor (Result Shr 16);

End;
//


function HashTableBucket(const P: Pointer; const ACapacity: NativeUInt): NativeUInt; inline;
begin
//  Result := HashTableFixBucket((NativeUInt(P) shr HASH_SHIFT) and ACapacity, ACapacity);
  Result := HashTableFixBucket(BJ32BitFAHash(NativeUInt(P){ shr HASH_SHIFT}) and ACapacity, ACapacity);
end;
28 мар 21, 12:56    [22301042]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
SOFT FOR YOU
Member

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

Да, ты прав
Небо и земля
Может что-то попроще взять?
Типа седжвика, например

Вот неплохой вариант (от hash_table2.zip):
function HashTableBucket(const P: Pointer; const ACapacityMask: NativeUInt): NativeUInt; inline;
var
  LTemp: NativeUInt;
begin
  LTemp := NativeUInt(P) shr 16;
  Result := ((NativeUInt(P) + LTemp) xor LTemp) and ACapacityMask;
end;


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

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

Попроще - это для x86 без хеша вообще, а для x64 брать младшие 4 байта.
28 мар 21, 13:47    [22301057]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
SOFT FOR YOU
Member

Откуда:
Сообщений: 3170
Что-то я совсем не догоняю

Почему это работает супер быстро:
function HashTableBucket(const P: Pointer; const ACapacityMask: NativeUInt): NativeUInt; inline;
begin
   Result := NativeUInt(P) and ACapacityMask;
end;

А вот это вот супер медленно:
function HashTableBucket(const P: Pointer; const ACapacityMask: NativeUInt): NativeUInt; inline;
begin
   Result := (NativeUInt(P) shr 4) and ACapacityMask;
end;


По идее наоборот. Если большинство указателей выровнены на 16 байт, то смещение наоборот должно дать хорошее распределение
28 мар 21, 14:46    [22301081]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 6314
SOFT FOR YOU
Возможны дубликаты (не часто), функция удаления должна возвращать, остался ли дубликат

реализация из дельфи очень плохо ложится на "условие возможности дуликатов" и вообще на "исключающий поиск"
т.е. "спрашивать то чего нет" это очень тормознуто

это возникает из-за того что для разруливания коллизий используется алгоритм "проверять до пустой", а обычно все значения кучкуются (теоретически вероятность встретить значение типа деградирует как (Size/Capacity)^i, но поди найди идеальную хэш-функцию), т.е. проверка наличия обычно деградирует на поиск совпадающего кеша по большому куску таблицы.

лучше поискать реализации с устранением коллизий с помощью бинарных деревьев (есть реализации на плоском массиве, ищи), либо искать очень хорошую хэш-функцию и разряжать массив (Size/Capacity -> 0), что бы дырки были чаще
29 мар 21, 06:47    [22301251]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
crutchmaster
Member

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

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

Откуда: Нижневартовск
Сообщений: 6314
+
SOFT FOR YOU
Что-то я совсем не догоняю

Почему это работает супер быстро:
function HashTableBucket(const P: Pointer; const ACapacityMask: NativeUInt): NativeUInt; inline;
begin
   Result := NativeUInt(P) and ACapacityMask;
end;

А вот это вот супер медленно:
function HashTableBucket(const P: Pointer; const ACapacityMask: NativeUInt): NativeUInt; inline;
begin
   Result := (NativeUInt(P) shr 4) and ACapacityMask;
end;


По идее наоборот. Если большинство указателей выровнены на 16 байт, то смещение наоборот должно дать хорошее распределение
ничего удивительного здесь нет, значения начинают кучковаться, собираясь в большие блоки
29 мар 21, 07:04    [22301253]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
SOFT FOR YOU
Member

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

Действительно в Delphi поиск до пустого
Я же ищу только в рамках бакета

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

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

Действительно в Delphi поиск до пустого
Я же ищу только в рамках бакета

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

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

Робин Гуд очень хорошо помогает в ситуации, когда в таблице формируются большие кластеры. Заполненность таблицы можно довести до 0.99 (если правильно помню, в расте хеш-таблицы с робин гудом, и там 0.9 по дефолту). Когда я с ним экспериментировал на обычных данных, то не впечатлился (скорость вставки несколько снижается, по сравнению с линейной схемой), однако, впоследствии, встретил ситуацию, при которой таблица без робин гуда адово тормозила.
29 мар 21, 11:33    [22301332]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
kealon(Ruslan)
Member

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

Тормозит на 20-30% потому, что "скакать надо" по массиву в произвольном порядке
реализации с деревьми тоже такой-же эффект имеют на современных процах, но они не дают обвалиться производительности на плохих случаях - за всё надо платить. В той же jave хвалятся, что реализовали устранение коллизий через бинарное дерево, но факт выше как-то умалчивают, и про перерасход памяти раза в 3 тоже молчат.

Можно бы было как вариант поддерживать сортировку по (Hash & C) - это бы позволило не гулять по всему куску при удалении и поиске, но он уже таблицу хешей срезал, что разумно.
В его случае, что бы побороться за производительность придётся пустить съэкономленную память на "слабое заполнение".
"Открытая адресация" других вариантов не оставляет. Ну и хорошо подбирать хэш-функцию под ситуацию.
29 мар 21, 12:22    [22301364]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 5101
kealon(Ruslan)
Тормозит на 20-30%

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

Откуда: Нижневартовск
Сообщений: 6314
Kazantsev Alexey
kealon(Ruslan)
Тормозит на 20-30%

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

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

В смысле, робингуд тормозит?
29 мар 21, 15:30    [22301485]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
kealon(Ruslan)
Member

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

да, так же как и 2-choice hashing
чем тупее код, тем он в идеальном варианте быстрее (при прочих равных естественно: хэш-функция, ёмкость)
29 мар 21, 15:40    [22301498]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

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

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

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

И ещё на счёт:
kealon(Ruslan)
"спрашивать то чего нет" это очень тормознуто


Берём таблицу с робингудом на 300K элементов (указателей). Примем условие, что только 30% ключей являются уникальными. Усложним задачу, установив заполнение таблицы: 0.99

add: 169 -- Вставляем 100K ключей 3 траза.
contains: 672 -- Ищем 100K существующих ключей 3 раза.
not contains: 688 -- Ищем 100K несуществующих ключей 3 раза.
remove: 924 -- Удаляем 100K существующих ключей 3 раза.

Как видим, поиск существующих и не существующих ключей выполняется за одинаковое время. Теперь посмотрим как выглядит эта таблица:

# Hash table map
# ==============
# Items.Length : 303030
# Capacity : 300000 (2147483647)
# Count : 300000
# Load Factor : 0.9900 (0.9900)


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

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

при поиске всегда выдается первый найденный?

вставляем 3 раза по 3 дубликата - непонятно как выглядят заголовки процедур?

Сообщение было отредактировано: 29 мар 21, 16:43
29 мар 21, 16:47    [22301537]     Ответить | Цитировать Сообщить модератору
 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]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

Откуда:
Сообщений: 5101
kealon(Ruslan)
однако он уже таблицу хэшей срезал

Сраведливости ради нужно заметить, что если довести количество элементов таблицы до порога её расширения, то их скорость становится одинаковой.

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

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

Статейки почитаю чуть попозже
Спасибо

Kazantsev Alexey,

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

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

Всё никак руки не доходят оформить и выложить...
30 мар 21, 16:20    [22302110]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
kealon(Ruslan)
Member

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

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

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

А чё тебе мой вариант не нравится?
Там есть и замер времени, и автотест в дебаге
30 мар 21, 20:36    [22302218]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
kealon(Ruslan)
Member

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

А чё тебе мой вариант не нравится?
Там есть и замер времени, и автотест в дебаге

да неплох твой проект в целом, то что хотелось(я так понимаю - это оптимизаия памяти) он закрывает
а то что структура немного плоха при удалении - тут надо выбирать: тратить ли память на хэши используя RG, либо не тратить

небольшое придирочное замечание
+
  function HashTableFixBucket(const ABucket: NativeUInt; const ACapacity: NativeUInt): NativeUInt; inline;
begin
  Result := ABucket;
  if (Result = ACapacity) then
    Result := 0;
end;

function HashTableBucketIncrement(const ABucket: NativeUInt; const ACapacity: NativeUInt): NativeUInt; inline;
begin
  Result := HashTableFixBucket(ABucket + 1, ACapacity);
end;

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

Откуда:
Сообщений: 5101
kealon(Ruslan)
тратить ли память на хэши используя RG, либо не тратить

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

Откуда: Нижневартовск
Сообщений: 6314
Kazantsev Alexey
kealon(Ruslan)
тратить ли память на хэши используя RG, либо не тратить

Посмотри на код, что я привёл, там хеши отдельно не хранятся.
про это 22301554 ?
по этому куску я вообще не вижу как там что хранится
31 мар 21, 14:13    [22302498]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
Kazantsev Alexey
Member

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

И shr 32 ни о чём не говорит?
31 мар 21, 14:54    [22302526]     Ответить | Цитировать Сообщить модератору
 Re: Linear probing хеш-таблица с дубликатами (просьба подключиться А. Шарахова)  [new]
kealon(Ruslan)
Member

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

это догадываться надо, а на шар у меня в последнее время электричества нет
31 мар 21, 18:37    [22302667]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: 1 2 3      [все]
Все форумы / Delphi Ответить