看板 TL
作者 標題 [筆記] 大量數字的計數並排序
時間 2013年01月27日 Sun. PM 06:38:15
看板 C_and_CPP
作者 標題 Re: [問題] 大量數字的計數並排序
時間 Mon Dec 27 08:06:09 2010
※ 引述《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
推 :!!1F 12/27 09:48
→ :好酷，這個有一點MapReduce的味道 XDD2F 12/27 10:05
推 :0.03F 12/27 10:06
→ :覺得檔案內先排序是必要的。4F 12/27 10:10
→ :不過動到IO的排序方式，一個下午不曉得能否跑完？
→ :不過動到IO的排序方式，一個下午不曉得能否跑完？
推 :推一下:)6F 12/27 10:57
推 : 推一下:)7F 12/27 11:21
--
Shaken, Not Stirred.
--
※ 作者: TL 時間: 2013-01-27 18:38:15
※ 看板: TL 文章推薦值: 0 目前人氣: 0 累積人氣: 35
回列表(←)
分享