Вопрос по dictionary, erlang – Временная сложность Эрланга Дикта

12

Мне интересно, если Erlang OTPdict Модуль реализован в виде хэш-таблицы, и в этом случае он дает производительность такого?

Средний случай

Search: O(1 + n/k)
Insert: O(1)
Delete: O(1 + n/k)

Худший случай

Search: O(n)
Insert: O(1)
Delete: O(n)

Источник:Википедия Хеш-таблица

Ваш Ответ

2   ответа
3

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

Глядя на источник для модуля 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-файл, к которым вы можете обратиться за техническими подробностями реализации (кроме того, в исходном коде есть больше комментариев, которые могут быть полезны)

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

7

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

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

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

Похожие вопросы