Re: [問題] 大量數字的計數並排序

[iamlouis (２塊錢立頓紅茶包)]

※ 引述《iamlouis (２塊錢立頓紅茶包)》之銘言：
: ※ 引述《mself (mself)》之銘言：
: : 程式碼(Code)： (請善用置底文標色功能)
: : 我原本想用 map<int, int> 先計數，將結果存進檔案。
: : 之後再用 sort command 排序那個檔案。
: : 可是因為 input 太多了，跑出 std::bad_alloc 的錯誤
: : 應該是記憶體不足。
: : 請問要怎麼做比較好呢？
:   我先假設你有 file system 可以用. 我想到的方法是將數值讀出來之後,
:   取高位元的 16 bit 當作檔名, 把值放在該檔案當中. 例如: 值 0x11223344
:   就會被放在 1122 這個檔案裡面, 所以最後這個檔案可能會長成這個樣子:

  吐嘈自己  :-)  這個方法有個問題: 如果值的分佈不均勻的時候, 記憶體可能還是
  不夠大到可以做 sorting. 極端的例子就是 1~2B 的值, 全部都是 0x0000000,
  結果全部都 hash 到 0000 這個檔案當中.

  改良的方法: 先將 1~2B 的檔案, 切成 n 個小檔案 (不需要真的切, 用 seek 跳著
  讀進記憶體就可以了), 每個小檔案在記憶體中先 sorting, 然後輸出到 n 個小檔案.
  接下來, 在這些小檔案之間做 merge sort, 在 merge 的時候, 不用把排好的數字
  寫到大檔案, 只要統計出現次數就可以了, 最後再依出現次數 sort 一次就好了.
   (呼應 bleed1979 大大的建議, 這樣可以將 disk access 的次數降到最低)

  做 merge sort 的時候, 有個小技巧, 由於每次都是比較 n 個檔案的排頭的數字,,
  所以可以將這 n 個數字先用 linked list 依大小串起來, 每次都拿走第一個(最小的)
  接下來, 將遞補的數字, 插入到該 linked list 當中適當的位置, 由於小檔案中
  的值已經排序過, 所以一般的情況下, 遞補的數字很快就可以找到他的位置. 舉例:

  小檔案 A:  6 6 8 9 9
  小檔案 B:  1 3 6 7 8
  小檔案 C:  5 5 6 6 9
  小檔案 D:  2 2 3 4 5

  第一回合的 linked list: B(1) -> D(2) -> C(5) -> A(6)

  永遠拿走第一個數字 (最小的), 也就是 B(1). 然後由 B 的 3 遞補, 變成:

                           *
                          B(3) -> D(2) -> C(5) -> A(6)

  把 B(3) 往後面一個一個比較, 直到大於等於下一個 linked list 中的數字:

                                   *
                          D(2) -> B(3) -> C(5) -> A(6)

  接著取走第一個數字: D(2), 遞補 D(2). 然後重覆一樣的動作. 直到結束.

  過程中, 使用兩個變數 current_value 與 current_count 記錄與輸出次數統計.
   (因為每次拿取的第一個數字, 一定是 n 個數字中最小的那個)

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 72.14.229.193
推 ledia:最後用個 priority_queue 吧 XD
推 DJWS:external sorting / external merge sort ?
推 suhorng:既然你已經分到檔案了，那用Counting Sort就不會有記憶體
→ suhorng:空間的問題啦 ?
→ iamlouis:counting sort 好像不行耶, 因為 range 可能是 2^32 種.
推 suhorng:@@!?不是先以數字的高16位元分檔案了?
→ suhorng:然後對每個檔案都counting sort一次呀?
→ tropical72:i大是說如果檔案裡面都是 1~10 的話就全都擠到同一個檔
→ tropical72:案裡面去了,所以才發這文再補充.
→ iamlouis:s大說的沒錯, 先用高16位元分到檔案後, 低16位元使用
→ iamlouis:counting sort就可以輕易求出統計數字了. 感謝s大.