Поиск карты в Elixir O (1)? - программирование

Структуры dict/map на основе хэш-таблицы обеспечивают время поиска O(1). Тем не менее, я продолжаю видеть, что в Elixir поиск подходящей функции голова быстрее, чем поиск чего-то на карте.

Например, Elixir String.Unicode компилирует список символов Юникода во многие главы функций, поэтому задавая вопрос: "Что такое верхняя версия é" ответил, найдя головку функции для upcase, которая ожидает "é".

Я не знаю, почему это было бы быстрее или более эффективно с памятью, чем с одной головкой upcase, которая просматривает "é" на карте.

Аналогично, когда показано, как построить библиотеку I18n в "Metaprogramming Elixir", Крис МакКорд дает каждому ключу трансляции свою собственную функциональную голову и говорит:

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

Карты в Elixir не обеспечивают поиск O (1)? Является ли поиск подходящей функции O (1)? Почему вы хотите собрать статический список для многих головоломок, а не просто сохранить его на карте?

Ответ 1

Эликсирные карты не являются плоскими структурами данных на основе хэш-таблицы. Маленькими картами являются упорядоченные списки, в которых карта имеет <= 31 записи. Когда карта получает 32 записи, она меняется на хэш-три, которая имеет поиск O(log n). В конце концов, неизменяемые структуры данных на основе хэш-таблицы будут очень дорогими для обновления, что является основным методом "создания" одной из этих структур данных. Изменение одного значения потребует, чтобы вы обновили новую карту всего за 1 пункт. Они основаны на постоянных хэшмапах Rich Hickey, которые являются своего рода массивом хэшей, отображаемым trie.

Сложность совпадения функций головы O(n) в худшем случае, но может быть оптимизирована компилятором способами, которые я не совсем понимаю. В некоторых случаях он может превратить некоторые шаблоны головы функции в дерево. Но так как совпадения функций не имеют общего порядка и должны совпадать в том порядке, в котором они определены, объем оптимизации довольно ограничен. Вам может быть просто повезло с использованием частей совпадения функций, которые очень малы, а также в дереве последовательности соответствия функции.

Каждый шаг головного матча также довольно легкий и высоко оптимизированный, где карты все еще новы, и есть некоторые оптимизации производительности. Сложность хэш-функции, например, не проста, если ключ сложный/вложенный (простые целые числа, однако, имеют очень быструю хэш-функцию). Но в примере вашего юникода, я ставлю стандарт юникода, по характеру, как он заказывает идентификатор, ставит перед собой как можно больше своих обычных персонажей. Это, вероятно, упростит работу виртуальной машины, и вы получите очень хорошее время поиска. Я уверен, что если вы посмотрите на неясный алфавит, ваша сложность изменится.

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