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

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

※ 引述《mself (mself)》之銘言：
: 程式碼(Code)： (請善用置底文標色功能)
: 我原本想用 map<int, int> 先計數，將結果存進檔案。
: 之後再用 sort command 排序那個檔案。
: 可是因為 input 太多了，跑出 std::bad_alloc 的錯誤
: 應該是記憶體不足。
: 請問要怎麼做比較好呢？

  我先假設你有 file system 可以用. 我想到的方法是將數值讀出來之後,
  取高位元的 16 bit 當作檔名, 把值放在該檔案當中. 例如: 值 0x11223344
  就會被放在 1122 這個檔案裡面, 所以最後這個檔案可能會長成這個樣子:

  1122:
    3344
    A487
    5566
    3344
    3345
    5566
    183c
    1ab0

  接下來, 把 1122 檔案內容做統計, 產生底下的檔案:

  1122.statistic:
    1122183c  1
    11221ab0  1
    11223344  2
    11223345  1
    11225566  2
    1122A487  1

  最後把所有的 .statistic 檔 cat 起來 (同一個檔案), 一起做一次 sort 就可以了.

  也就是說, 把 32-bit 值域先 hash 成小範圍的檔案們 (2^16個 16-bit 值域),
  讓統計或排序變簡單與可行, 最後再組合起來做一次排序.
  當然, 如果在產生 statistic 檔的時候先排序過,
  這樣最後一個動作就可以用 merge sort 來做, 效率會更好.

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 221.169.204.127
推 ledia:!!
→ james732:好酷，這個有一點MapReduce的味道 XDD
推 loveme00835:0.0
→ bleed1979:覺得檔案內先排序是必要的。
→ bleed1979:不過動到IO的排序方式，一個下午不曉得能否跑完？
推 VictorTom:推一下:)
推 nowar100: 推一下:)