16

私が取り組んでいるプログラムでは、大きな「スレッド ツリー」 (ノードごとに最大で k 個の子) を開発しています。各スレッドは、その親から継承されたハッシュ テーブルにいくつかの変更を加えます。ある程度「永続的」なハッシュ テーブルを実装する方法はありますか ( http://en.wikipedia.org/wiki/Persistent_data_structureの意味で) ?

つまり、少なくとも O(log n) のルックアップ、挿入、および完全に永続的な削除を伴うキーと値のペアリングを実装する方法はありますが、通常のハッシュと同じくらい「スペース効率」(最悪の場合) です。テーブル？

4

4 に答える 4

5

「通常のハッシュテーブルと同じくらいスペース効率が良い」というのはかなりあいまいな仕様です。わかりやすい永続ハッシュ テーブルを設計した人はまだいないと思います。

必要な複雑さを持つ永続的なキー値マップを取得する最も簡単な方法は、永続的な二分探索ツリーを使用することです。ルックアップは、一時的な (非永続的な) BST でおなじみのアルゴリズムです。ただし、変更を挿入すると、(疑似 Java) のようになります。

// overwrites the value for k if it's already in the tree
Node insert(Node node, Key k, Value v)
{
    if (k < node.key)
        return new Node(node.key, node.val, insert(node.left, k, v), node.right);
    else if (k > node.key)
        return new Node(node.key, node.val, node.left, insert(node.right, k, v));
    else
        return new Node(k, v, node.left, node.right);
}

挿入ルーチンは新しいツリーを返すことに注意してください。これは非効率に見えるかもしれませんが、トラバースするノードのみを変更します。これは平均で O(lg n ) なので、平均で O(lg n ) 回の割り当てを行います。これは、得られるスペース効率とほぼ同じです。

最悪の場合の O(lg n ) の動作を取得するには、赤黒木を使用します。関数型プログラミングのデータ構造に関する文献も参照してください。

于 2011-02-01T11:19:12.273 に答える
2

完全に永続的であるが、通常のハッシュテーブルと同じくらい「スペース効率」(最悪の場合) である、少なくとも O(log n) ルックアップ、挿入、および削除を備えたキーと値のペアリングを実装する方法はありますか?

確かにあります。多くの方法。

たとえば、Haskell では、次のように単純なData.Mapサイズバランスの取れたバイナリ ツリー (または制限付きバランスのツリー) が記述されています。

  • Stephen Adams 著、「Efficient sets: a balancer act」、Journal of Functional Programming 3(4):553-562、1993 年 10 月、http ://www.swiss.ai.mit.edu/~adams/BB/ 。
  • J. Nievergelt および EM Reingold 著、「有界バランスの二分探索木」、SIAM ジャーナル オブ コンピューティング 2(1)、1973 年 3 月。

基準を満たす次の API を提供します。

insert :: Ord k => k -> a -> Map k a -> Map k a   -- O(log n)
lookup :: Ord k => k -> Map k a -> Maybe a        -- O(log n)
delete :: Ord k => k -> Map k a -> Map k a        -- O(log n)

完全に持続的でありながら。スペースの使用はO(n)です。

より良い定数係数についてはData.HashMap、全体的な複雑さが同じデータ構造などを試してください。

代替構造は次のとおりです。

  • キーストレージが高密度であるため、ハッシュテーブルよりもスペースの使用が改善された永続的な試行。
于 2011-05-30T15:24:43.800 に答える
1

Clojure は、ハッシュ マップなどの一連の永続的なデータ構造を実装しています。オープンソースですので、一度見てみてはいかがでしょうか？

http://clojure.org/data_structures

http://code.google.com/p/clojure/source/browse/trunk/src/jvm/clojure/lang/PersistentHashMap.java

于 2011-02-01T17:39:29.530 に答える
1

つまり、少なくとも O(log n) のルックアップ、挿入、および完全に永続的な削除を伴うキーと値のペアリングを実装する方法はありますが、通常のハッシュと同じくらい「スペース効率」(最悪の場合) です。テーブル？

はい。Driscoll et al. の「Making Data Structures Persistent」のセクション 5では、挿入、削除、およびルックアップの O(lg n) 時間と O(1) スペースの複雑さで、完全に永続的な赤黒ツリーを作成する手法を示しています。

それらのデータ構造は、コンフルエントに永続的ではありません。持続性の詳細については、このトピックに関する Kaplan の調査を参照してください。

于 2011-03-24T03:14:59.710 に答える