12

私は岡崎の純粋関数型データ構造に取り組んでおり、物事のF＃実装を構築しようとしています。私はまた、本にリストされている演習を行っています（いくつかはかなり挑戦的です）。元の2パスの実装ではなく、シングルパスで実行されるようにWeightBiasedLeftistHeapのマージ関数を変更する必要がある演習3.4に固執しています。

私はまだこれを行う方法を理解することができず、いくつかの提案を望んでいました。SOに関する別の投稿があり、makeT関数をほぼインライン化することでSMLでそれを実行しています。私はこのルートを開始しました（コメントセクション3.4 First Tryで。しかし、これは実際にはシングルパスで実行されていないと思ったため、このアプローチを放棄しました（リーフに到達するまで、ツリーを巻き戻して再構築します）。それをまだ2パスマージであると解釈するのは間違っていますか？

これは、WeightBiasedLeftistHeapの完全な実装へのリンクです。

F＃でこれを実行しようとして失敗したのは次のとおりです。

type Heap<'a> =
| E
| T of int * 'a * Heap<'a> * Heap<'a> 

module WeightBiasedLeftistHeap =
    exception EmptyException

    let weight h =
        match h with
        | E -> 0
        | T(w, _,_,_) -> w

    let makeT x a b =
        let weightA = weight a
        let weightB = weight b
        if weightA >= weightB then
            T(weightA + weightB + 1, x, a, b)
        else
            T(weightA + weightB + 1, x, b, a)

    // excercise 3.4 first try
    //    let rec merge3_4 l r =
    //        match l,r with
    //        | l,E -> l
    //        | E,r -> r
    //        | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
    //            if lx <= rx then
    //                let right = merge3_4 lb rh
    //                let weightA = weight la
    //                let weightB = weight right
    //
    //                if weightA >= weightB then
    //                    T(weightA + weightB + 1, lx, la, right)
    //                else
    //                    T(weightA + weightB + 1, lx, right, la)
    //            else
    //                let right = merge3_4 lh rb
    //                let weightA = weight ra
    //                let weightB = weight right
    //
    //                if weightA >= weightB then 
    //                    T(weightA + weightB + 1, rx, ra, right)
    //                else
    //                    T(weightA + weightB + 1, rx, right, ra)

    // excercise 3.4 second try (fail!)
    // this doesn't work, I couldn't figure out how to do this in a single pass
    let merge3_4 l r =
        let rec merge' l r value leftChild  =
            match l,r with
            | l,E -> makeT value leftChild l
            | E,r -> makeT value leftChild r
            | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
                if lx <= rx then
                    merge' lb rh lx la   //(fun h -> makeT(lx, la, h))
                else
                    merge' lh rb rx ra   //(fun h -> makeT(rx, ra, h))

        match l, r with
        | l, E -> l
        | E, r -> r
        | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
            let lf = fun h -> makeT(lx, la, h)
            if lx <= rx then
                merge' lb rh lx la // (fun h -> makeT(lx, la, h))
            else
                merge' lh rb rx ra // (fun h -> makeT(rx, ra, h))

    let rec merge l r =
        match l,r with
        | l,E -> l
        | E,r -> r
        | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
            if lx <= rx then
                makeT lx la (merge lb rh)
            else
                makeT rx ra (merge lh rb)

    let insert3_4 x h =
        merge3_4 (T(1,x,E,E)) h
4

2 に答える 2

23

最初の質問は、「ワンパス」アルゴリズムを構成するものは何かということです。単一のトップダウンループとして自然に実装できるものが適格です。対照的に、再帰（単純にコンパイルされたもの）には通常、2つのパスがあります。1つはダウンの途中で、もう1つはアップの途中です。 末尾再帰は簡単にループにコンパイルでき、通常は関数型言語です。 末尾再帰のモジュロ短所は、あまり一般的ではありませんが、同様の最適化です。ただし、コンパイラが末尾再帰のモジュロ短所をサポートしていない場合でも、そのような実装を手動でループに簡単に変換できます。

末尾再帰のモジュロ短所は、通常の末尾再帰と似ていますが、末尾呼び出しがコンストラクターでラップされている点が異なります。コンストラクターは、再帰呼び出しの前に割り当てて部分的に入力できます。この場合、戻り式はのようなものにする必要がありますT (1+size(a)+size(b)+size(c),x,a,merge(b,c))。ここで必要な重要な洞察（他のSOスレッドの編集で述べたように）は、結果がどのくらい大きくなるか、したがって新しいツリーのどちら側にあるかを知るためにマージを実行する必要がないということです。続ける。これは、のサイズmerge(b,c)が常にであるためです。これはsize(b)+size(c)、マージの外部で計算できます。

rank通常の左利きヒープの元の関数はこのプロパティを共有しないため、この方法で最適化できないことに注意してください。

次に、基本的に、makeTへの2つの呼び出しをインライン化し、フォームの呼び出しをに変換しsize(merge(b,c))ますsize(b)+size(c)。

この変更を行うと、再帰的マージを評価する前に結果のルートを返すことができるため、結果の関数は元の関数よりも大幅に遅延します。

同様に、ロックとミューテーションを含む並行環境では、新しい実装は、ツリー全体をロックするのではなく、途中で各ノードのロックを取得および解放することで、大幅に多くの同時実行をサポートできます。（もちろん、これは非常に軽量のロックにのみ意味があります。）

于 2011-06-14T02:21:12.693 に答える
2

質問を正しく理解したかどうかは正確にはわかりませんが、これが私の試みです-現在、merge操作はへの再帰呼び出しを実行しmerge（これが最初のパスです）、ヒープの終わりに達すると（の最初の2つのケースmatch）、新しく構築されたヒープを呼び出し元に戻しmakeT、数回呼び出します（これが2回目のパスです）。

単純にインライン化することが私たちに求められていることではないと思いmMakeTます（そうであれば、追加inlineするだけmakeTで、コードを読みにくくすることなく実行されます:-)）。

ただし、実行できるのはmerge、「残りの作業」が関数として再帰呼び出しに渡される継続渡しスタイルを使用するように関数を変更することです（したがって、スタック上で実行される保留中の作業はありません。最初のパスが完了します）。これは次のように実行できます。

let rec merge' l r cont =
    match l,r with
    | l,E -> cont l // Return result by calling  the continuation
    | E,r -> cont r // (same here)
    | T(_, lx, la, lb) as lh, (T(_, rx, ra, rb) as rh) ->
        if lx <= rx then
            // Perform recursive call and give it 'makeT' as a continuation
            merge' lb rh (makeT lx la)
        else
            // (same here)
            merge' lh rb (makeT rx ra)

// Using 'id' as a continuation, we just return the 
// resulting heap after it is constructed
let merge l r = merge' l r id

これが正しい答えであるとは完全には確信していません。パスは1回だけ実行されますが、（継続して）集約された作業は、パスが2倍長くなることを意味します。しかし、これをもっと簡単にする方法がわからないので、それは正しい答えかもしれません...

于 2011-06-13T19:39:16.143 に答える