需求：
1）
现在要求你提供一个服务，输入考生编号，返回该考生的三科成绩。请说明你的磁盘文件组织和内存数据结构。并尽量对性能做优化
2）
假设由于地区区域不同，考生的编号不连续，范围改变为1~10亿之间，请对你上述方案作出相应的修改。
3)
在主干条件不变的情况下，由于系统升级，需要提供排名查询，即输入考生编号，在返回三科成绩之外，还需要额外提供此考生的总成绩在全部考生中的排名，相同成绩的考生名次并列。需要注意的是，在系统提供查询服务期间，仍有可能补录一楼的考生成绩，由于查询量远大于补漏的数量，请设计合理的数据结构以最大化提升查询性能。
我是这样想的
1）
N（百万级别） 最大为 1000万，直接在内存中肯定放不下成绩数据，所以应该建立一个索引表，其实就是一个有N项顺序表，表的下标就是考生的编号，该下标对应的内容即该编号考生的成绩数据在磁盘文件中的位置，而且应该至少用4字节整数才能索引到文件每一项。内存中存放索引表用了40M了。
磁盘中的成绩总共有N*3*4Byte 大小 也就是120兆左右 加上分隔每科成绩和每个考生成绩的分隔符 最多也就150兆
这儿题目中要求说明磁盘文件组织，是什么意思？
我回答文件中每条记录格式是a成绩 分隔符 b成绩 分隔符 c成绩 分隔符........这样回答正确吗？
还有第一问如何对性能做优化呀？
2）
这个我知道 应该是用hash函数 把id压缩到N之内，是吧。
3）
内存感觉已经放不下东西了，因为已经用掉了40兆了。
我觉得肯定应该对文件进行外排，然后每次查询时，就返回记录地址除以每个文件记录大小+1，O(1)的复杂度，但是这样的话每个文件记录地址就变了，重新建立索引？
而且要重新建立索引的话，应该在文件记录中加上学生编号这个域，对吧？
这样磁盘文件也还是够用，问题是，每次加入一个新的学生，就要重新排序一次，而且还要重新建立索引，
我不知道 我的解法有没有达到最大化查询性能的要求。
还有 我上面的分析有没有疏漏或者错误？？
大家讨论讨论
5 个解决方案
#1
该回复于2011-10-18 11:03:10被版主删除
#2
1）
现在要求你提供一个服务，输入考生编号，返回该考生的三科成绩。请说明你的磁盘文件组织和内存数据结构。并尽量对性能做优化
我想应该是将数据进行分开，使用多个文件去存放数据。比如1-100000放在第一个文件，100000-200000.这样的话根据ID就可以去加载对应的文件，然后去查找相应的数据。
一千万 × 4 / 1024 / 1024 所有的数据都放在内存里面，需要大概150M内存，所以肯定是不够用的。这样就是每次的查询都是从文件里面去读取。尽量减少内存中保存数据。
2）
假设由于地区区域不同，考生的编号不连续，范围改变为1~10亿之间，请对你上述方案作出相应的修改。
我想可以加一个索引文件，表示这个ID所在范围对应的文件。
第三个要求有点复杂。。。
现在要求你提供一个服务，输入考生编号，返回该考生的三科成绩。请说明你的磁盘文件组织和内存数据结构。并尽量对性能做优化
我想应该是将数据进行分开，使用多个文件去存放数据。比如1-100000放在第一个文件，100000-200000.这样的话根据ID就可以去加载对应的文件，然后去查找相应的数据。
一千万 × 4 / 1024 / 1024 所有的数据都放在内存里面，需要大概150M内存，所以肯定是不够用的。这样就是每次的查询都是从文件里面去读取。尽量减少内存中保存数据。
2）
假设由于地区区域不同，考生的编号不连续，范围改变为1~10亿之间，请对你上述方案作出相应的修改。
我想可以加一个索引文件，表示这个ID所在范围对应的文件。
第三个要求有点复杂。。。
#3
如果是放在文件里面的话，就全是字符串，占用大小会大一些： 1千万是8个字符，加上三个成绩9个字符，加上三个分隔符可以用空格3个字符，一个字符两个字节。也就是1千万 × 20 × 2 / 1024 /1024，大概是380M左右。不超过硬盘大小。
#4
第三题：
我想我们应该换种思路。其实就是计算那个考生的分数占用的排名，也就是只需要一个文件记录300行数据，每个分数包含的人数。
然后先查询出考生的成绩，之后计算排名就很容易了。
重新录入一个考生。只要将他的成绩对应的人数加一，更新一条成绩就OK了。
我想我们应该换种思路。其实就是计算那个考生的分数占用的排名，也就是只需要一个文件记录300行数据，每个分数包含的人数。
然后先查询出考生的成绩，之后计算排名就很容易了。
重新录入一个考生。只要将他的成绩对应的人数加一，更新一条成绩就OK了。
#5
第三个不用排序的
只需要记录总分为0 - 300的学生个数各为多少就行了
int stucnt[301]; //0号位表示总分为0的学生个数 1号位表示总分为1的学生个数 依次类推
每次获取学生排名，只需算一下总分小于该生的学生有多少个即可
每次补录时也只需要更新这个数组即可
只需要记录总分为0 - 300的学生个数各为多少就行了
int stucnt[301]; //0号位表示总分为0的学生个数 1号位表示总分为1的学生个数 依次类推
每次获取学生排名，只需算一下总分小于该生的学生有多少个即可
每次补录时也只需要更新这个数组即可
#1
该回复于2011-10-18 11:03:10被版主删除
#2
1）
现在要求你提供一个服务，输入考生编号，返回该考生的三科成绩。请说明你的磁盘文件组织和内存数据结构。并尽量对性能做优化
我想应该是将数据进行分开，使用多个文件去存放数据。比如1-100000放在第一个文件，100000-200000.这样的话根据ID就可以去加载对应的文件，然后去查找相应的数据。
一千万 × 4 / 1024 / 1024 所有的数据都放在内存里面，需要大概150M内存，所以肯定是不够用的。这样就是每次的查询都是从文件里面去读取。尽量减少内存中保存数据。
2）
假设由于地区区域不同，考生的编号不连续，范围改变为1~10亿之间，请对你上述方案作出相应的修改。
我想可以加一个索引文件，表示这个ID所在范围对应的文件。
第三个要求有点复杂。。。
现在要求你提供一个服务，输入考生编号，返回该考生的三科成绩。请说明你的磁盘文件组织和内存数据结构。并尽量对性能做优化
我想应该是将数据进行分开，使用多个文件去存放数据。比如1-100000放在第一个文件，100000-200000.这样的话根据ID就可以去加载对应的文件，然后去查找相应的数据。
一千万 × 4 / 1024 / 1024 所有的数据都放在内存里面，需要大概150M内存，所以肯定是不够用的。这样就是每次的查询都是从文件里面去读取。尽量减少内存中保存数据。
2）
假设由于地区区域不同，考生的编号不连续，范围改变为1~10亿之间，请对你上述方案作出相应的修改。
我想可以加一个索引文件，表示这个ID所在范围对应的文件。
第三个要求有点复杂。。。
#3
如果是放在文件里面的话，就全是字符串，占用大小会大一些： 1千万是8个字符，加上三个成绩9个字符，加上三个分隔符可以用空格3个字符，一个字符两个字节。也就是1千万 × 20 × 2 / 1024 /1024，大概是380M左右。不超过硬盘大小。
#4
第三题：
我想我们应该换种思路。其实就是计算那个考生的分数占用的排名，也就是只需要一个文件记录300行数据，每个分数包含的人数。
然后先查询出考生的成绩，之后计算排名就很容易了。
重新录入一个考生。只要将他的成绩对应的人数加一，更新一条成绩就OK了。
我想我们应该换种思路。其实就是计算那个考生的分数占用的排名，也就是只需要一个文件记录300行数据，每个分数包含的人数。
然后先查询出考生的成绩，之后计算排名就很容易了。
重新录入一个考生。只要将他的成绩对应的人数加一，更新一条成绩就OK了。
#5
第三个不用排序的
只需要记录总分为0 - 300的学生个数各为多少就行了
int stucnt[301]; //0号位表示总分为0的学生个数 1号位表示总分为1的学生个数 依次类推
每次获取学生排名，只需算一下总分小于该生的学生有多少个即可
每次补录时也只需要更新这个数组即可
只需要记录总分为0 - 300的学生个数各为多少就行了
int stucnt[301]; //0号位表示总分为0的学生个数 1号位表示总分为1的学生个数 依次类推
每次获取学生排名，只需算一下总分小于该生的学生有多少个即可
每次补录时也只需要更新这个数组即可