二分木を作成するための再帰的アルゴリズムの反復バージョン
https://stackoverflow.com/questions/235868
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
このアルゴリズムを考慮すると、反復バージョンが存在するかどうか知りたいと思います。また、反復バージョンの方が高速になるかどうかも知りたいです。
これはある種の擬似 Python です...
アルゴリズムはツリーのルートへの参照を返します
make_tree(array a)
if len(a) == 0
return None;
node = pick a random point from the array
calculate distances of the point against the others
calculate median of such distances
node.left = make_tree(subset of the array, such that the distance of points is lower to the median of distances)
node.right = make_tree(subset, such the distance is greater or equal to the median)
return node
解決
通常、再帰呼び出しが1つだけの再帰関数は、あまり労力をかけずに末尾再帰関数に変換できます。その後、反復関数に変換するのは簡単です。ここでの標準的な例は階乗です：
# naïve recursion
def fac(n):
if n <= 1:
return 1
else:
return n * fac(n - 1)
# tail-recursive with accumulator
def fac(n):
def fac_helper(m, k):
if m <= 1:
return k
else:
return fac_helper(m - 1, m * k)
return fac_helper(n, 1)
# iterative with accumulator
def fac(n):
k = 1
while n > 1:
n, k = n - 1, n * k
return k
ただし、ここでのケースには2つの再帰呼び出しが含まれているため、アルゴリズムを大幅に修正しない限り、スタックを保持する必要があります。独自のスタックの管理は、Pythonの関数呼び出しスタックを使用するよりも少し速いかもしれませんが、追加された速度と深さは、おそらく複雑さの価値はありません。ここでの標準的な例は、フィボナッチ数列です：
# naïve recursion
def fib(n):
if n <= 1:
return 1
else:
return fib(n - 1) + fib(n - 2)
# tail-recursive with accumulator and stack
def fib(n):
def fib_helper(m, k, stack):
if m <= 1:
if stack:
m = stack.pop()
return fib_helper(m, k + 1, stack)
else:
return k + 1
else:
stack.append(m - 2)
return fib_helper(m - 1, k, stack)
return fib_helper(n, 0, [])
# iterative with accumulator and stack
def fib(n):
k, stack = 0, []
while 1:
if n <= 1:
k = k + 1
if stack:
n = stack.pop()
else:
break
else:
stack.append(n - 2)
n = n - 1
return k
今、あなたのケースはこれよりもはるかに困難です：単純なアキュムレータは、部分的に構築されたツリーを、サブツリーを生成する必要がある場所へのポインタで表現するのが困難です。 ジッパーが必要になります。実際には機能しない言語のような実装は簡単ではありませんPython。
他のヒント
反復バージョンの作成は、通常の言語呼び出しスタックの代わりに独自のスタックを使用するだけです。通常の呼び出しスタックはこの目的のために最適化されているため、反復バージョンの方が高速になるとは思いません。
取得するデータはランダムであるため、ツリーは任意のバイナリツリーになります。この場合、スレッド化されたバイナリツリーを使用できます。これは、再帰なしでスタックなしで走査および構築できます。ノードには、リンクが別のノードへのリンクであるか、「次のノード」に到達する方法を示すフラグがあります。
「反復」をどのように定義するかによっては、前の回答で言及されていない別の解決策があります。「反復」が単に「スタック オーバーフロー例外の影響を受けない」(ただし、「let rec」の使用は許可される) ことを意味する場合、末尾呼び出しをサポートする言語では、(「明示的な」ではなく) 継続を使用してバージョンを作成できます。スタック"）。以下の F# コードはこれを示しています。これは、配列から BST を構築するという点で、元の問題に似ています。配列がランダムにシャッフルされる場合、ツリーは比較的バランスが取れており、再帰バージョンによってスタックが深すぎることはありません。しかし、シャッフルをオフにすると、ツリーのバランスが崩れ、再帰バージョンはスタック オーバーフローしますが、継続ありの反復バージョンは問題なく続行されます。
#light
open System
let printResults = false
let MAX = 20000
let shuffleIt = true
// handy helper function
let rng = new Random(0)
let shuffle (arr : array<'a>) = // '
let n = arr.Length
for x in 1..n do
let i = n-x
let j = rng.Next(i+1)
let tmp = arr.[i]
arr.[i] <- arr.[j]
arr.[j] <- tmp
// Same random array
let sampleArray = Array.init MAX (fun x -> x)
if shuffleIt then
shuffle sampleArray
if printResults then
printfn "Sample array is %A" sampleArray
// Tree type
type Tree =
| Node of int * Tree * Tree
| Leaf
// MakeTree1 is recursive
let rec MakeTree1 (arr : array<int>) lo hi = // [lo,hi)
if lo = hi then
Leaf
else
let pivot = arr.[lo]
// partition
let mutable storeIndex = lo + 1
for i in lo + 1 .. hi - 1 do
if arr.[i] < pivot then
let tmp = arr.[i]
arr.[i] <- arr.[storeIndex]
arr.[storeIndex] <- tmp
storeIndex <- storeIndex + 1
Node(pivot, MakeTree1 arr (lo+1) storeIndex, MakeTree1 arr storeIndex hi)
// MakeTree2 has all tail calls (uses continuations rather than a stack, see
// http://lorgonblog.spaces.live.com/blog/cns!701679AD17B6D310!171.entry
// for more explanation)
let MakeTree2 (arr : array<int>) lo hi = // [lo,hi)
let rec MakeTree2Helper (arr : array<int>) lo hi k =
if lo = hi then
k Leaf
else
let pivot = arr.[lo]
// partition
let storeIndex = ref(lo + 1)
for i in lo + 1 .. hi - 1 do
if arr.[i] < pivot then
let tmp = arr.[i]
arr.[i] <- arr.[!storeIndex]
arr.[!storeIndex] <- tmp
storeIndex := !storeIndex + 1
MakeTree2Helper arr (lo+1) !storeIndex (fun lacc ->
MakeTree2Helper arr !storeIndex hi (fun racc ->
k (Node(pivot,lacc,racc))))
MakeTree2Helper arr lo hi (fun x -> x)
// MakeTree2 never stack overflows
printfn "calling MakeTree2..."
let tree2 = MakeTree2 sampleArray 0 MAX
if printResults then
printfn "MakeTree2 yields"
printfn "%A" tree2
// MakeTree1 might stack overflow
printfn "calling MakeTree1..."
let tree1 = MakeTree1 sampleArray 0 MAX
if printResults then
printfn "MakeTree1 yields"
printfn "%A" tree1
printfn "Trees are equal: %A" (tree1 = tree2)
はい、再帰アルゴリズムを反復することは可能です。暗黙的に、再帰アルゴリズムを作成するとき、各呼び出しは前の呼び出しをスタックに配置します。あなたがしたいことは、暗黙の呼び出しスタックを明示的なものにすることです。反復バージョンは必ずしも高速ではありませんが、スタックオーバーフローを心配する必要はありません。 （回答にサイトの名前を使用するためのバッジがありますか？
一般的な意味では、再帰アルゴリズムを直接反復アルゴリズムに変換するには明示的なスタックが必要になるのは事実ですが、反復形式で直接レンダリングする特定のアルゴリズムのサブセットがあります（スタックは不要です） 。これらのレンダリングは、パフォーマンスの保証が同じではない場合があります（機能リストの繰り返しと再帰的な解体）が、しばしば存在します。
スタックベースの反復ソリューション（Java）：
public static Tree builtBSTFromSortedArray(int[] inputArray){
Stack toBeDone=new Stack("sub trees to be created under these nodes");
//initialize start and end
int start=0;
int end=inputArray.length-1;
//keep memoy of the position (in the array) of the previously created node
int previous_end=end;
int previous_start=start;
//Create the result tree
Node root=new Node(inputArray[(start+end)/2]);
Tree result=new Tree(root);
while(root!=null){
System.out.println("Current root="+root.data);
//calculate last middle (last node position using the last start and last end)
int last_mid=(previous_start+previous_end)/2;
//*********** add left node to the previously created node ***********
//calculate new start and new end positions
//end is the previous index position minus 1
end=last_mid-1;
//start will not change for left nodes generation
start=previous_start;
//check if the index exists in the array and add the left node
if (end>=start){
root.left=new Node(inputArray[((start+end)/2)]);
System.out.println("\tCurrent root.left="+root.left.data);
}
else
root.left=null;
//save previous_end value (to be used in right node creation)
int previous_end_bck=previous_end;
//update previous end
previous_end=end;
//*********** add right node to the previously created node ***********
//get the initial value (inside the current iteration) of previous end
end=previous_end_bck;
//start is the previous index position plus one
start=last_mid+1;
//check if the index exists in the array and add the right node
if (start<=end){
root.right=new Node(inputArray[((start+end)/2)]);
System.out.println("\tCurrent root.right="+root.right.data);
//save the created node and its index position (start & end) in the array to toBeDone stack
toBeDone.push(root.right);
toBeDone.push(new Node(start));
toBeDone.push(new Node(end));
}
//*********** update the value of root ***********
if (root.left!=null){
root=root.left;
}
else{
if (toBeDone.top!=null) previous_end=toBeDone.pop().data;
if (toBeDone.top!=null) previous_start=toBeDone.pop().data;
root=toBeDone.pop();
}
}
return result;
}
