Временная сложность erlang dict

Ответ 1

Поскольку модуль dict реализован в самом Erlang, используя встроенные типы данных (кортежи и списки), и является неразрушающим, то есть каждое "обновление" фактически создает слегка переписанную новую версию предыдущего dict, время сложность никогда не может быть лучше логарифмической (реализация должна использовать какое-то дерево), но детали могут варьироваться в зависимости от реализации.

Текущая реализация (которая существует уже много лет) на самом деле не очень хорошо масштабируется, когда количество записей становится большим. Автор (Роберт Вирддинг) недавно экспериментировал с другими реализациями дерева, такими как 2-3 дерева, и вполне возможно, что реализация dict-модуля по умолчанию будет изменена в будущей версии. См. http://erlang.org/pipermail/erlang-questions/2012-June/067311.html

Если вы заинтересованы в подобных вещах, вам может потребоваться больше узнать о чистых функциональных структурах данных. Это кажется хорошей отправной точкой: http://en.wikipedia.org/wiki/Purely_functional (в частности, ссылка на тезис Окасаки).

Ответ 2

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

Глядя на источник для модуля dict (lib/stdlib/src/dict.erl), показывает:

%% We use the dynamic hashing techniques by Per-�ke Larsson as
%% described in "The Design and Implementation of Dynamic Hashing for
%% Sets and Tables in Icon" by Griswold and Townsend.  Much of the
%% terminology comes from that paper as well.

В этой статье представлен ряд ссылок с данным PDF файлом, на которые вы можете ссылаться на технические подробности реализации (также есть больше комментариев в исходном коде, которые могут быть полезны)

Надеюсь, что он проливает свет на него!