8

これは、外部マージソートについて説明しているリンクから取得しました。

スライド6から例：5つのバッファページを使用して、108ページのファイルを並べ替える

  • Pass0：[108/5] =各5ページの22のソートされた実行（最後の実行は3ページのみ）

  • Pass1 [22/4] =各20ページの6つのソートされた実行（最後の実行は8ページのみ）

  • Pass2：[6/3] = 2つのソートされた実行、80ページと28ページ

  • パス3：[2/2] =1108ページのソートされたファイル

質問：私の理解は外部マージソートにあります。パス0では、チャンクを作成してから各チャンクをソートします。残りのパスでは、それらをマージし続けます。したがって、これを上記の例に適用すると、バッファページが5つしかないため、パス0では、それぞれ5ページの22のソートされた実行が必要です。

  1. では、なぜ代わりに残りのパスに対してソートされた実行を行ったり、マージしたりするのですか？

  2. バッファページが5つしかないのに、パス1、それぞれ20ページの6つのソートされた実行がどうしてわかるのでしょうか。

  3. ここでマージは正確にどこで行われていますか？そして、各パスでNはどのように減少しますか？つまり、108から22、6から2になりますか？

4

2 に答える 2

17

すべてのデータをメモリに保存できない場合は、外部マージソートが必要です。最善の方法は、データを並べ替えられた実行に分割し、後続のパスで実行をマージすることです。実行の長さは、使用可能なバッファーサイズに関連付けられています。

Pass0：あなたはその場で操作を行っています。したがって、5ページのデータをバッファにロードし、インプレースソートアルゴリズムを使用してインプレースソートします。これらの5ページは、実行として一緒に保存されます。

次のパス：多くのページの実行をマージしているため、その場で操作を実行できなくなります。4ページがバッファにロードされ、5番目が書き込みバッファです。マージはマージソートアルゴリズムと同じですが、2ではなくB-1の係数で分割統治します。書き込みバッファがいっぱいになると、ディスクに書き込まれ、次のページが開始されます。

複雑さ：外部マージソートの複雑さを分析する場合、I/Oの数が考慮されています。各パスで、ページを読み取って書き込む必要があります。Nをページ数とします。各実行には2Nの費用がかかります。ページを読み、ページを書きます。
バッファスペースを保持できるページ数をB、ページ数をNとします。
ceil（log_B-1（ceil（N / B）））パスがあります。各パスには2NI/Oがあります。つまり、O（nlogn）です。

各パスで、実行のページ長はB-1の係数で増加し、ソートされた実行の数はB-1の係数で減少しています。
Pass0：ceil（108/5）= 22、実行あたり5ページ
Pass1：ceil（22/4）= 6、実行あたり20ページ
Pass2：ceil（6/4）= 2、実行あたり80ページ
Pass3：ceil（2 / 4）= 1-完了、108ページの1回の実行

于 2012-04-28T01:38:12.740 に答える
0

A.マージについては言及されていないので、後の「ソート」パスがマージを行っていると思います（期待しています）。

B.繰り返しになりますが、これがマージされていると仮定すると、マージされたレコードを保存するために1つのバッファーが必要であり、マージされる各ファイルに残りのバッファーの1つを使用します。

C.マージが2回行われているところに答えたと思います:)

于 2012-04-28T01:19:25.133 に答える