Design-and-analysis-of-algorithms-optimal-merge-pattern
DAA-最適なマージパターン
異なる長さのソート済みファイルのセットを単一のソート済みファイルにマージします。 結果のファイルが最短時間で生成される最適なソリューションを見つける必要があります。
ソートされたファイルの数が指定されている場合、それらを単一のソートされたファイルにマージする多くの方法があります。 このマージはペアで実行できます。 したがって、このタイプのマージは* 2-wayマージパターン*と呼ばれます。
異なるペアリングには異なる時間を必要とするため、この戦略では、多くのファイルをマージする最適な方法を決定します。 各ステップで、2つの最短シーケンスがマージされます。
- p-recordファイル*と* q-recordファイル*をマージするには、 p + q レコードの移動が必要になる可能性があります。当然のことながら、各ステップで2つの最小ファイルをマージします。
双方向マージパターンは、バイナリマージツリーで表すことができます。 一連の n ソート済みファイル \ {f〜1〜、f〜2〜、f〜3〜、…、f〜n〜} を考えてみましょう。 最初は、この各要素は単一ノードのバイナリツリーと見なされます。 この最適なソリューションを見つけるために、次のアルゴリズムが使用されます。
Algorithm: TREE (n)
for i := 1 to n – 1 do
declare new node
node.leftchild := least (list)
node.rightchild := least (list)
node.weight) := ((node.leftchild).weight) + ((node.rightchild).weight)
insert (list, node);
return least (list);このアルゴリズムの最後に、ルートノードの重みが最適なコストを表します。
例
与えられたファイル、f〜1〜、f〜2〜、f〜3〜、f〜4〜、f〜5〜をそれぞれ20、30、10、5、30個の要素で考えてみましょう。
提供されたシーケンスに従ってマージ操作が実行される場合、
- M〜1〜= f〜1〜とf〜2〜をマージ* ⇒ 20 + 30 = 50
- M〜2〜= M〜1〜とf〜3〜をマージ ⇒ 50 + 10 = 60
- M〜3〜= M〜2〜とf〜4〜をマージします。 ⇒ 60 + 5 = 65
- M〜4〜= M〜3〜とf〜5〜のマージ ⇒ 65 + 30 = 95
したがって、操作の総数は
50 + 60 + 65 + 95 = 270
さて、より良い解決策はありますか？
昇順でサイズに応じて番号を並べ替えると、次のシーケンスが得られます-
- f〜4〜、f〜3〜、f〜1〜、f〜2〜、f〜5〜*
したがって、このシーケンスでマージ操作を実行できます
- M〜1〜= f〜4〜とf〜3〜をマージ ⇒ 5 + 10 = 15
- M〜2〜= M〜1〜とf〜1〜をマージ ⇒ 15 + 20 = 35
- M〜3〜= M〜2〜とf〜2〜*をマージする⇒ 35 + 30 = 65
- M〜4〜= M〜3〜とf〜5〜のマージ ⇒ 65 + 30 = 95
したがって、操作の総数は
15 + 35 + 65 + 95 = 210
明らかに、これは前のものよりも優れています。
このコンテキストでは、このアルゴリズムを使用して問題を解決します。
初期セット
ステップ1
ステップ2
ステップ-3
ステップ-4
したがって、ソリューションには15 + 35 + 60 + 95 = 205の比較が必要です。
