作者godisme (老鼠)
看板C_and_CPP
標題[問題]
時間Tue May 12 21:52:19 2009
這個我也必須承認是作業文 XD
但我不是來要答案的~"~
題目如下: 模擬 external sorting
寫一個程式 程式讀取 input.txt 文件檔
裡面會有一堆數字 請把內部數字 排序好
在寫入 output.txt 檔.....
就這樣? 才怪~ 要是這樣我就不需要PO文了 ~"~|
補充: 文件檔 input.txt 和 ouput.txt是一個純文字檔 內含 " 不定 "
的行數 lines (代表 page數目的 N 不固定)
但每行有 4個整數 (最後一行不一定)
EX: 3 13 4 11
6 5 15 12
16 10 1 9
2 7 15 14
13 8
結果:
1 2 3 4
5 6 7 8
9 10 11 12
13 13 14 15
15 16
重點!!
假設可以使用 9 個 buffer pages(B=9),每個buffer page可以
儲存4個整數，且每個 disk I/O 讀取或寫出一整個line(4個整數)
Pass 0 使用 heapsort,並且要計算 pass 0 產生的所有 run 平均長度
( 大約為 2*(B-2)*(page size) = 2*7*6 =56 個整數~ 其中B個
buffer pages中 留1個做 output buffer,留一個做 input buffer)
還要顯示總共經過幾個 pass,以及 使用多少次 disk I/O (讀取
和寫出的 line數) ~
目前 小弟會把檔案讀進來 做 heapsort 在把檔案寫出去...
但是小弟的 資料庫老師 要我們模擬的 我真的搞不懂~"~
請板上前輩 不吝 以 淺俗的 解說 教導小弟
> < 我想寫出來阿!!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.47.76.182
※ godisme:轉錄至看板 Database 05/12 22:12
1F：→ sosokill:逐行讀取→取出數字→轉成int→比較&排序→轉成char(Str) 05/12 22:24
2F：→ sosokill:→存檔→結束 05/12 22:25
3F：→ sosokill:External Sortiing→ 05/12 22:27
5F：推 jerohands:fstream inf("input.txt", ios::in); int num = 0; 05/12 22:30
6F：→ jerohands:然後就一直作inf>> num; 讀數字直到eof 05/12 22:30
7F：→ jerohands:然後可以再偷工減料用STL的容器幫你作sorting。Done! 05/12 22:31
8F：→ jerohands:抱歉，第2行更正。既然要External Sorting那就讀到你指 05/12 22:35
9F：→ jerohands:定大小的Buffer，flush到硬碟，再重複作Y 05/12 22:36
10F：→ godisme:恩 可是我還是不懂 56的意思 還有 計算LINE數 > <" 05/12 22:43
11F：推 evernever:56是你自己算的, 還是老師已給56, 你要找原因.. 05/12 23:16
12F：推 snowlike:可視範圍是7行*4整，output第七行時，已經input 2倍行數 05/12 23:25
13F：→ snowlike:io次數應該要一樣的，意思應該是指達到排序完成input幾次 05/12 23:26