作者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