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

看板C_and_CPP作者 (mself)時間15年前 (2010/12/26 20:35), 編輯推噓1(1推 0噓 14→)
留言15則, 5人參與, 最新討論串1/5 (看更多)
開發平台(Platform): (Ex: VC++, Gcc, Linux, ...) Linux 問題(Question)： 有一個檔案，裡面有非常多數字， 即使僅算不同的，也還是很多 想將數字依照出現的次數多寡排序 餵入的資料(Input)： 10 11 10 12 預期的正確結果(Expected Output)： 10, 2 11, 1 12, 1 程式碼(Code)： (請善用置底文標色功能) 我原本想用 map<int, int> 先計數，將結果存進檔案。 之後再用 sort command 排序那個檔案。 可是因為 input 太多了，跑出 std::bad_alloc 的錯誤 應該是記憶體不足。 請問要怎麼做比較好呢？ 補充說明(Supplement)： 謝謝～ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 203.73.48.214
→
12/26 20:36, , 1F
不一定要 stable sort、但 stable 當然是很好
12/26 20:36, 1F
→
12/26 20:45, , 2F
有沒有數字範圍 多少資料
12/26 20:45, 2F
→
12/26 20:50, , 3F
範圍一定要知道, 如果非常密集, 排不完的
12/26 20:50, 3F
→
12/26 21:02, , 4F
數字範圍是 32bit，個數有 1~2 billion 個
12/26 21:02, 4F
→
12/26 21:11, , 5F
覺得用 external sort 先 sort 過可能會比較好...
12/26 21:11, 5F
推
12/26 21:23, , 6F
一兩億的話, 至少也得要32bits來存, range也有32bits,
12/26 21:23, 6F
→
12/26 21:24, , 7F
開陣列你需要16G的memory才放得下!?(小弟有沒算錯啊Orz)
12/26 21:24, 7F
→
12/26 21:25, , 8F
可以直接找資料庫來處理這些資料嗎....(光速逃XD)
12/26 21:25, 8F
→
12/26 21:34, , 9F
仔細想過後，應該先 sort 再記數。
12/26 21:34, 9F
→
12/26 21:34, , 10F
sort algorithm 有一類是專門處理超過 memory 大小的
12/26 21:34, 10F
→
12/26 21:35, , 11F
那就是 external sort。 sort 過就好辦多了。
12/26 21:35, 11F
→
12/26 21:43, , 12F
最後再 sort 一次~
12/26 21:43, 12F
→
12/27 10:01, , 13F
billion是10億，現在把1024當1000，
12/27 10:01, 13F
→
12/27 10:03, , 14F
4 * 1000000000 / 1000(kb) / 1000(mb) = 4000(mb) = 4G
12/27 10:03, 14F
→
12/27 10:07, , 15F
一個檔案這麼大，連開檔都很累吧。
12/27 10:07, 15F
‣ 更多 mself 的文章
文章代碼(AID): #1D5pQJnA (C_and_CPP)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 5 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共5篇)
‣ 更多 mself 的文章
文章代碼(AID): #1D5pQJnA (C_and_CPP)