→ bleed1979:感謝，我知道怎麼寫了。 12/27 16:04
→ loveme00835:移位要小心整數的實際大小 12/27 16:45
我實作出來了，但是有問題想請教。
程式的問題出在亂數的部分。
我原本使用rand() % INT_MAX; (srand有寫)
但數值似乎只出現1,2萬的數值，
如果想要0 ~ 2147483647，
想請教怎麼修改會比較好。
(目前的亂數我硬是shift，才會有多個檔出現)
這份程式數量多的數字會先出現，如果數量相同就數字小的先出現。
目前跑1000個數字沒有出錯，有興趣的人可以增加DATA_SIZE。
http://nopaste.csie.org/db489
http://codepad.org/ka6UWpg3
謝謝。
Bleed
※ 引述《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: 114.32.177.97