3

現在、不変の BST を clojure に実装しようとしています。これは私のmake-tree関数です:

(defn make-tree [v] {:v v :l nil :r nil})

と挿入:

(defn insert [tree v]
  (if (nil? tree)
    (make-tree v)
    (case (compare v (tree :v))
      -1 (assoc tree :l (insert (:l tree) v))
      0 tree
      1 (assoc tree :r (insert (:r tree) v)))))

問題は、この挿入関数は次のようなものでオーバーフローすることです

(reduce insert (make-tree 1) (range 10000))

1000 を超える深さはほとんど必要ないように、ツリーのバランスを取ることができることを理解しています。オーバーフローしないように関数を定義する方法があるかどうか、まだ興味があります。

ミュータブル版はノードを変更するだけなので、親ノードを保存する必要がなく便利そうです。

あなたは実生活で何を選びますか？可変または不変？

4

2 に答える 2

4

A.ウェッブの答えに追加するには：

純粋に機能的な実装は CPS で記述する必要がありますが、ツリーを機能的なラッパー + 可変ノードとして実装することもできます。変更は次のように行われます。

  1. ラッパーは新しい空のルートを作成し、現在のルートに変更を実行して結果を新しいルートに入れるように指示します。

  2. 新しいルートが自身の値を変更する必要があると判断した場合、その子を新しいルートにコピーし、新しい値を新しいルートに入れ、戻ります。

  3. それ以外の場合は、その値と変更を必要としないブランチを新しいルートにコピーし、変更が必要な (または可能性がある) ブランチの代わりに、新しいルートに新しい (空白の) ノードをインストールします。

  4. 現在のルートは、変更が必要なブランチにそれ自体を変更するように指示し、新しい空白ノードも渡します。

  5. ブランチは、手順 2 ～ 5 を繰り返す際のルートとして機能します。

  6. ラッパーは、新しいルートで新しいラッパーを作成します。トップレベルの操作の結果として、新しいラッパーが返されます。

上記のポイント 2 から 5 は再帰手順を説明していますが、実際には末尾再帰であるため、ループとして書き直すことができます。

すべてが完了した後、もちろん、古いラッパーは完全に正常であり、同じツリーを保持しています (すべての変更は新しいノードのみに関係しているため)。

実際、Clojure データ構造の多くは、包含可変性 (主に配列を含む) を常に使用しています。(ただし、ツリー マップではありません。ミュータビリティを使用する実際のパターンも異なりますが、包含ミュータビリティを使用して内部で物事を高速化し、外部で機能的なインターフェイスを維持するという基本的な前提は似ています。)

また、接線方向の 2 つのコメントを追加します。

まず、実装compareでは -1、0、1 のいずれかが返されると想定していますが、実際には、「より小さい」の場合は負の数を、「より大きい」の場合は正の数を自由に返すことができます (は私の REPL で(compare "foo" "bar")評価され、おそらく4正確な値は指定されていませんが、任意の JVM REPL です)。

次に、Clojure で実装された自己均衡ツリーの実例に興味がある場合は、 ClojureとClojure の実装であるsorted.cljを参照してください。これは ClojureScript 実装に基づいており、これは Clojure の Java 実装の移植版です。現時点では、純粋に実験的なものだと思います1が、動作しているように見え (CLJS テスト スイートに合格し、REPL で期待したことを実行します)、単純な PDS 実装の例として役立つ場合があります。 Clojureのように見えます。PersistentTreeMapPersistentTreeSet

1基本的に ClojureScript の実装を作成した後、同じデータ構造の Clojure 実装を作成するのにどれだけの追加作業が必要かを確認したかったのです。Javaインターフェースを実装する必要があるため、いくつかの追加作業があることは明らかですが、コードを処理する配列を微調整する必要がありますが、あまり多くないことを望んでいました. その基本的な期待が経験によって裏付けられたことを喜んで報告します。パフォーマンスに関しては、Java 実装の標準に完全には達していません (ほとんどのベンチマークで 1.5 倍の速度低下を覚えているようですが、再確認する必要があります)。現時点では、 core.rrb-vectorのパフォーマンス チューニングが優先されますが、最終的にはこれを改善したいと考えています。

于 2013-05-18T12:54:01.403 に答える
3

あなたの実装は自己均衡ではなく、あなたの例は要素が順番に挿入される最悪のシナリオです。スタック オーバーフローは、深い再帰によるものです。これを回避するには、呼び出しスタックを暗黙的に使用するのではなく、末尾再帰を使用するか、明示的なアンワインド スタックを作成できるように、継続渡しスタイルでアルゴリズムを書き直す必要があります。

実生活では、Clojure にはすでに不変の自己均衡ツリーsorted-setと がありsorted-map、ほとんどの状況でこれを使用します。Java にはミュータブルTreeMapがあり、必要に応じて Clojure の Java 相互運用機能を介してかなり簡単に利用できます。

(into (sorted-set) (range 10000))

于 2013-05-17T16:50:03.110 に答える