Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Delphi Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
 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]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2 3   вперед  Ctrl      все
Все форумы / Delphi Ответить