История изменений
Исправление Nervous, (текущая версия) :
это не хэш, а просто массив деревьев
Да, это не хэш (hash-table), это префиксное дерево (trie), в котором роль префиксов играют куски ключа элемента или производного от него значения (хэша ключа).
Насколько я понимаю, когда с помощью trie реализуют собственно хэш-таблицу (словарь) с произвольными ключами, ключи нужно хэшировать, чтобы привести их к единому представлению и минимизировать коллизии, а когда реализуют вектор — можно вместо хэшей использовать тупа сами ключи (индексы), они по определению уникальные (коллизий нет) и уже нужного вида (целые числа).
будет срыв кэша практически на каждом элементе
Да, говорят, с кэшем есть некоторые сложности. Но зато имеем эффективные иммутабельные персистентные структуры данных без постоянных копирований всего массива. Как всегда — серебряной пули нет, есть набор компромиссов.
Есть любопытная серия постов как раз про персистентные векторы: https://hypirion.com/musings/understanding-persistent-vector-pt-1
Реально данных от произвольного ключа в программе не оказалось.
Ну то есть и в программе на Перле хэш был не так чтобы сильно и нужен, и можно было ускорить и её тем же методом (не в 50 раз, конечно).
Исправление Nervous, :
это не хэш, а просто массив деревьев
Да, это не хэш (hash-table), это префиксное дерево (trie), в котором роль префиксов играют куски ключа элемента или производного от него значения (хэша ключа).
Насколько я понимаю, когда с помощью trie реализуют собственно хэш-таблицу (словарь) с произвольными ключами, ключи нужно хэшировать, чтобы привести их к единому представлению и минимизировать коллизии, а когда реализуют вектор — можно вместо хэшей использовать тупа сами ключи (индексы), они по определению уникальные (коллизий нет) и уже нужного вида (целые числа).
будет срыв кэша практически на каждом элементе
Да, говорят, с кэшем есть некоторые сложности. Но зато имеем эффективные иммутабельные структуры данных без постоянных копирований всего массива. Как всегда — серебряной пули нет, есть набор компромиссов.
Есть любопытная серия постов как раз про персистентные векторы: https://hypirion.com/musings/understanding-persistent-vector-pt-1
Реально данных от произвольного ключа в программе не оказалось.
Ну то есть и в программе на Перле хэш был не так чтобы сильно и нужен, и можно было ускорить и её тем же методом (не в 50 раз, конечно).
Исходная версия Nervous, :
это не хэш, а просто массив деревьев
Да, это не хэш (hash-table), это префиксное дерево (trie), в котором роль префиксов играют куски ключа элемента или производного от него значения (хэша ключа).
Насколько я понимаю, когда с его помощью реализуют собственно хэш-таблицу (словарь) с произвольными ключами, ключи нужно хэшировать, чтобы привести их к единому представлению и минимизировать коллизии, а когда реализуют вектор — можно вместо хэшей использовать тупа сами ключи (индексы), они по определению уникальные (коллизий нет) и уже нужного вида (целые числа).
будет срыв кэша практически на каждом элементе
Да, говорят, с кэшем есть некоторые сложности. Но зато имеем эффективные иммутабельные структуры данных без постоянных копирований всего массива. Как всегда — серебряной пули нет, есть набор компромиссов.
Есть любопытная серия постов как раз про персистентные векторы: https://hypirion.com/musings/understanding-persistent-vector-pt-1
Реально данных от произвольного ключа в программе не оказалось.
Ну то есть и в программе на Перле хэш был не так чтобы сильно и нужен, и можно было ускорить и её тем же методом (не в 50 раз, конечно).