外部排序合併(external sort-merge)

在複習外部排序合併的概念時,一直想不透下面例子中的Pass 2, 為何會是前半段佔 80 pages, 而後半段佔 28 pages? 可以給我一個合理的解釋嗎?

假設記憶體的 buffer = 5 pages, 所要排序的檔案大小佔 108 page:

Pass 0: 108/5 = 22; 檔案會被切割載入記憶體做 22 回合的排序, 每一回合會使用 5 pages.

Pass 1: 22/4 = 6 (除不盡, 商數進位成整數); 切割後的檔案會再做 6 回合的排序, 每一回合會使用 20 pages.

Pass 2: 將 2 個已各別完成排序的資料列, 再做排序並合併成 1 個資料列; 第 1 個資料列佔 80 pages, 第 2 個資料列佔 28 pages.

Update:

非常感謝您的回答, 但是我覺得自己還不是很懂您在 Pass 1 及 Pass 2 的說明, 可以請您再幫我解析一下嗎?

我原來的想法是:

第1回合 - 分割成 22 個區塊, 各個區塊已完成排序.

第2回合 - 將 22 個區塊兩兩合併並做排序; 整合成 11 個已完成排序的區塊.

第3回合 - 參照上述步驟, 可整合成 6 個已完成排序的區塊.

第4回合 - 同上, 此時可整合成 3 個已完成排序的區塊.

第5回合 - 同上, 此時可整合成 2 個已完成排序的區塊.

第 6 回合 - 即可將全部資料整合成一個已完成排序的區塊.

請問我是哪個概念弄錯了?

1 Answer

Rating
  • 1 decade ago
    Favorite Answer

    pass 0:

    分成22段,每段都各自排序。(初始段)

    其中有 21 段占 5 pages,有 1 段占 3 pages。

    pass 1:

    由題目所揭資訊,知其採 4 路合併,得花 6 個回合,

    第 1~5 回合各用 5*4=20 pages,

    第 6 回合用 5+3=8 pages。

    本階段合併成 6 段,其中有 5 段各占 20 pages,有 1 段占 8 pages。

    pass 2:

    把 pass 1 併成的 6 段,再用 4 路合併,得花 2 個回合,

    第 1 回合用 20*4=80 pages,

    第 2 回合用 20+8=28 pages。

    本階段合併成 2 段,其中有 1 段占 80 pages,有 1 段占 28 pages。

    pass 3:

    把 pass 2 併成的 2 段,再合併成 1 段,排序完成。

    2009-06-20 14:12:06 補充:

    你在補充所述的內容是正確的,是最基本的2路合併。

    但你的題目所述,22/4 = 6 擺明了是用4路合併,

    既然題目已指定用4路合併,當然用4路合併的觀點來處理。

    所謂4路合併,是指同時處理4段併成1段。

    2009-06-20 14:24:30 補充:

    你在補充所用的第1回合至第6回合,

    建議改用第0回合至第5回合,

    第0回合是初始階段,即分割來源資料,並各自順序。

    第1回合以後者為歸併階段,較易看出是歷經幾個回合的歸併。

    歸併的回合數=log n M

    上式中的 n=合併的路數 ,M=初始的段數

    以本例,用4路,要歸併 log4 22 =3 回合。

    若用2路,要歸併 log2 22 =5 回合。

    • Login to reply the answers
Still have questions? Get your answers by asking now.