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

看板C_and_CPP作者iamlouis (２塊錢立頓紅茶包)時間15年前 (2010/12/29 10:34)推噓4(4推 0噓 7→)

留言11則, 5人參與討論串5/5 (看更多)

※ 引述《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

12/29 16:08, , 1^F

12/29 16:08, 1^F

推

DJWS

12/29 16:43, , 2^F

12/29 16:43, 2^F

推

suhorng

12/29 19:53, , 3^F

12/29 19:53, 3^F