Re: [問題] 大量數字的計數並排序
※ 引述《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
推
12/27 09:48, , 1F
12/27 09:48, 1F
→
12/27 10:05, , 2F
12/27 10:05, 2F
推
12/27 10:06, , 3F
12/27 10:06, 3F
→
12/27 10:10, , 4F
12/27 10:10, 4F
→
12/27 10:11, , 5F
12/27 10:11, 5F
推
12/27 10:57, , 6F
12/27 10:57, 6F
推
12/27 11:21, , 7F
12/27 11:21, 7F
推
12/27 17:48, , 8F
12/27 17:48, 8F
推
12/28 00:44, , 9F
12/28 00:44, 9F
推
12/28 01:17, , 10F
12/28 01:17, 10F
討論串 (同標題文章)