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)

出典:ウィキペディアハッシュテーブル

4

2 に答える 2

7

dictモジュールは組み込みのデータ型(タプルとリスト)を使用してErlang自体に実装され、非破壊的であるため、つまり、すべての「更新」によって実際に以前のdictのわずかに書き直された新しいバージョンが作成されるため、時間計算量は決してありません。対数よりも優れています(実装では何らかのツリーを使用する必要があります)が、詳細は実装によって異なる場合があります。

現在の実装(長年使用されています)は、エントリの数が多くなると、実際にはうまく拡張できません。著者(Robert Virding)は最近、2-3ツリーなどの他のツリー実装を実験しており、将来のリリースでdictモジュールのデフォルト実装が変更される可能性があります。http://erlang.org/pipermail/erlang-questions/2012-June/067311.htmlを参照してください

この種のことに興味がある場合は、純粋な機能データ構造について詳しく調べてください。これは良い出発点のようです:http://en.wikipedia.org/wiki/Purely_functional(特に岡崎の論文へのリンク)。

于 2012-06-18T20:32:10.330 に答える
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とのリンクがいくつか表示され、実装の技術的な詳細を参照できます(また、ソースコードには役立つ可能性のあるコメントがあります)

それがそれに光を当てることを願っています!

于 2012-06-15T17:39:25.180 に答える