3

Splay Treesウィキペディアのページには、次のように書かれています(「利点」セクション)。

更新後に以前のバージョンと新しいバージョンの両方にアクセスできる、スプレイ ツリーの永続的なデータ構造バージョンを作成する可能性。これは関数型プログラミングで役立ち、更新ごとに償却された O(log n) スペースが必要です。

何故ですか？関数型プログラミングは、特に永続的な Splay ツリーをどのように利用していますか?

4

3 に答える 3

6

あなたの質問は、しつこく不幸な用語の混乱から来ているようです。より良い言い方は、純粋に関数型、つまり、破壊的な突然変異のない関数型プログラミングです。さまざまな理由から、不変で永続的なデータ構造が関数型プログラミング全体でより一般的であるという事実から、混乱が生じる可能性があります。

要するに、おそらくそのフレーズを「永続的なスプレイ ツリーの作成は、不変のデータ構造のみを使用してプログラミングする場合に役立つ可能性がある」と読むことができます。これは、トートロジーに隣接しています。

于 2011-12-01T21:35:59.550 に答える
5

ステートフルプログラムはエラーを回避するためにコマンドを正しい順序で注意深く実行する必要があるため、最新の関数型プログラミングの推進目標の1つは、状態の管理を改善することです。

永続データ構造は、可変状態を使用しないため、正確に優れており、純粋で不変の計算で使用できます。

//mutable tree
var t = new_tree();
add(t, 1);
add(t, 2);
//the tree has now changed so if anyone was depending on the old value
//we will now have a problem

//persistent tree
var t = new_tree();
var t2 = add(t, 1);
var t3 = add(t2, 2);
//t1 and t2 have not changed

あなたが指摘した引用は、永続データ構造が純粋関数型プログラミングで一般的に使用されている（そして好まれている）ことを強調しているだけです。この場合、スプレー木については特に何もありません。

于 2011-12-01T21:31:30.790 に答える
1

反対に、関数型プログラミングでスプレイ ツリーを使用するのはあまり快適ではありません。検索操作のたびに新しいツリーを返し、ほぼすべての操作で最後のツリーを追跡する必要があるためです。また、私が知っているすべての検索ツリーは、操作ごとに O(log n) の追加スペースで機能的に直接使用できます。その文の唯一の興味深い事実は、ツリーを常に再構築しているにもかかわらず、操作ごとのメモリ要件が O(log n) 償却されたままであるということですが、検索に対してもそのスペースの代償を払っていることに注意してください。

于 2015-08-25T19:30:57.393 に答える