[問題] 適合大資料的排序方法

看板C_and_CPP作者 ( ╮(╯▽╰)╭)時間9年前 (2015/01/09 02:56), 編輯推噓3(3推 0噓 25→)
留言28則, 10人參與, 最新討論串1/1
開發平台(Platform): (Ex: VC++, GCC, Linux, ...) Dev-c++ 問題(Question)： 要用甚麼演算法比較適合大量數據的排序呢? 餵入的資料(Input)： 從檔案讀取大約幾十萬筆數字(都是不超過1000的正整數) 補充說明(Supplement)： 用了merge-sort/quicksort/heapsort三種演算法 好像都會爆掉... 可能會是甚麼問題呢? 想問哪一種排序演算法最可以承受大量的數據輸入呢? (先不考慮執行效能的話...) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.177.11.234 ※ 文章網址: http://www.ptt.cc/bbs/C_and_CPP/M.1420743402.A.147.html
→
01/09 03:03, , 1F
不超過 1000 的正整數，radix sort 最適合
01/09 03:03, 1F
→
01/09 03:06, , 2F
但是要解決問題你要先說你的爆掉是什麼意思
01/09 03:06, 2F
→
01/09 03:08, , 3F
如果是記憶體塞不下又沒範圍，就用 external merge
01/09 03:08, 3F
→
01/09 03:18, , 4F
compile時出現"xxx已經停止運作" 感覺是記憶體不夠...
01/09 03:18, 4F
→
01/09 03:19, , 5F
那external merge sort的code要怎麼寫呢?
01/09 03:19, 5F
→
01/09 05:46, , 6F
不超過 1000 ... 把它想成大量數據，方向就錯誤了。
01/09 05:46, 6F
→
01/09 05:47, , 7F
查一下 Programming Pearls 的第一章(Jon Benteley)
01/09 05:47, 7F
推
01/09 06:38, , 8F
我感覺未必是記憶體不夠，您有先用幾百筆的資料測過
01/09 06:38, 8F
→
01/09 06:39, , 9F
您的程式嗎？如果資料少時正確，資料大時錯誤的話
01/09 06:39, 9F
→
01/09 06:39, , 10F
才可能是記憶體的緣故。那也測一下多大才會死掉。
01/09 06:39, 10F
→
01/09 07:02, , 11F
算一百萬筆，用 int64 存也不會爆。除非存在 stack。
01/09 07:02, 11F
→
01/09 07:02, , 12F
compile 的時候就出現難不成是 compiler 有 bug XD (誤
01/09 07:02, 12F
→
01/09 07:03, , 13F
重點是你根本不知道錯在哪，然後開始修一個不存在的bug
01/09 07:03, 13F
→
01/09 07:08, , 14F
前面說錯，用 counting sort 纔對。不用讀入所有資料，
01/09 07:08, 14F
→
01/09 07:09, , 15F
就能做，而且快。只需要 int[1001] 的空間。
01/09 07:09, 15F
→
01/09 07:10, , 16F
然後 external merge sort code google 隨便都有...
01/09 07:10, 16F
→
01/09 07:11, , 17F
總之，我覺得要不是你別的地方錯，不然就是存在 stack
01/09 07:11, 17F
→
01/09 07:12, , 18F
先檢查完，再來做 counting sort 或 external sort
01/09 07:12, 18F
→
01/09 10:28, , 19F
神奇海螺說：有BUG
01/09 10:28, 19F
→
01/09 12:36, , 20F
真的是compiler在compile時compiler停止運作嗎？
01/09 12:36, 20F
→
01/09 12:38, , 21F
還是你只是按到「編譯並執行」？compiler問題跟程式
01/09 12:38, 21F
→
01/09 12:38, , 22F
問題是不一樣的
01/09 12:38, 22F
→
01/09 14:52, , 23F
未看先猜int arr[n]
01/09 14:52, 23F
推
01/11 11:19, , 24F
演算法的話理論上都可以吧 只是效率的問題
01/11 11:19, 24F
→
01/11 11:20, , 25F
會爆掉的話 還是要看是什麼東西爆掉才能做判斷
01/11 11:20, 25F
推
01/11 13:16, , 26F
幾十萬筆稱不上大資料吧... qsort都還ok
01/11 13:16, 26F
→
01/14 13:01, , 27F
stack overflow?
01/14 13:01, 27F
→
01/14 13:02, , 28F
試試看全域變數?
01/14 13:02, 28F
‣ 更多 kevin77884 的文章
文章代碼(AID): #1KhjBg57 (C_and_CPP)