Производительность Hash Array Mapped Trie

Я пытаюсь реализовать Hash Array Mapped Trie на Java. Раньше я думал, что эта структура данных должна быть более эффективной с точки зрения памяти, чем Hash Map, но когда я сделал первые измерения памяти с помощью Visual Vm, я обнаружил, что моя реализация требует больше памяти, чем Hash Map (также операция «положить» медленнее). Я не могу понять: HAMT действительно требует больше памяти, или я допустил ошибку в реализации. Результаты производительности такие же, как у в этом вопросе.

Есть ли преимущества в производительности «Hash Array Mapped Trie» по сравнению с «Hash Table» («Hash Map»)?


hashmap algorithm trie hashtable
person Ivan Kurchenko    schedule 13.02.2014    source источник
comment
Вы использовали классическое дерево или радиксное дерево? Какова длина ваших ниток для теста? сколько струн вы использовали? Сколько бит вы перемешали?   -  person amit    schedule 13.02.2014
comment
Нет, я их не использовал. Я использовал hamt. Для тестов я сделал два случая: со случайными целыми числами и последовательными целыми числами в качестве ключей. Количество ключей в разных тестах составляло от 1 до 5 миллионов. Длина префикса хеширования составляла 4 бита (в классическом варианте - 5).   -  person Ivan Kurchenko    schedule 13.02.2014
comment
Кто вам сказал, что хамты в любом случае быстрее хеш-таблиц? Их большое преимущество в том, что они настойчивы, но не слишком быстры. В быстрых реализациях также используются низкоуровневые уловки вроде аппаратного popcount и т. Д. Я думаю, что таким образом можно приблизиться к скорости хэш-таблицы.   -  person Niklas B.    schedule 13.02.2014
comment
Никлас Б., спасибо за комментарий! Я ошибся в вопросе. Я действительно имею в виду использование памяти, а не производительность. Как я понял из статей «Идеальные хеш-деревья» и «Быстрый и эффективный поиск по пространству», Hamt должен быть более эффективным с точки зрения памяти. Или я ошибаюсь?   -  person Ivan Kurchenko    schedule 13.02.2014

Ответы (1)


arrow_upward
2
arrow_downward

Можно ожидать, что для одного HAMT потребуется больше памяти, чем для одной хеш-таблицы. Преимущество памяти появляется только тогда, когда вы используете постоянные свойства HAMT. Когда вы делаете копию HAMT и изменяете в ней одно значение, вы можете совместно использовать большинство узлов между двумя копиями, для хеш-таблицы вам обычно потребуется дублировать всю структуру таблицы.

person JanKanis    schedule 18.08.2016