请教什么算法可以最优的获取某次考试班级进步、退步最快的10个学生列表

赵开锦 发布于 2011/11/09 15:12
阅读 789
收藏 0

现有学生成绩表,结构如下:

id、学生id、班级id、考试id、语文成绩、数学成绩、英语成绩

请教给出班级id和考试id,如何最快的计算出相对与上次考试,进步最快的10人和退步最快的10人,要求支持多客户端并发的。

说明:上次考试id=本次考试id-1

加载中
0
方旭
方旭

一楼的解法有个小问题就是,最大差分值不等于进步名次,比如倒数第一的同学第一次总分50,第二次150,差距100,但还是倒数第一名,并没有名次差,分值差倒是挺大的。

想要知道最优算法,必须理解清楚,问题基本解答出来总共的复杂度。抛开SQL,因为它也是需要算法支持。知道基本解法的复杂度,就可以从每个步骤的复杂度进行优化。

假设班级有N个同学,假设2次考试,一般解法:

    第一步:需要对每个同学总成绩进行计算,需要循环N次,有两次考试,需要2N次。

    第二步:需要对两次考试排名,第一步得到了两个无序数组,这步需要对这两个数组进行排序,假设用快速排序,需要复杂度:N*logN,两个数组总共需要:2*N*logN。

    第三步:需要对两个排序好的数据进行一个相同同学的比对获得一个数组,比如一个同学第一次是第10名,第二次如果是第1名,数组记录9,前进了9位,如果第二次是20名,记录-10,表示后退了10位。由于两个数组是根据分数排序,并没有根据用户名排序,所以需要循环第一个数组,到第二个数组中查找相同的同学名,比较排名差,记录到新数组。复杂度是:N * N。

    第四步:第三步计算出了排名差的数组,但是是无序的,需要从这个数组中找到前10名和后10名,也就是对这个数组进行一次排序,需要 N*logN。

    以上是我对这个问题基本解答的思路,优化也需要思路,具体可以参考:

    编程珠玑 - 代码调优法则 - 基础篇

1
方旭
方旭
第三步的复杂度N*N最大,可以考虑在第二步后,再对排序好的其中一个数组进行按照同学名排序,记录名次,第三步时候就可以根据未排序的一个数组循环到排序好的数组搜索相同名字的名次,排序好的数组查找,复杂度为一个常数(参考二分查找),那么第三步复杂度:常数 * N。但是增加了一个排序一个数组的复杂度:N*logN。第三步就变成了:N*logN + 常数 * N。
0
sxgkwei
sxgkwei

我是否可以理解为都是考试进步,只是有的人进步是负数?

1,取出这次考试成绩信息,相加获得总成绩

2,取出上次考试成绩信息,相加获得总成绩

3,这次总成绩-上次总成绩

4,对上步获得结果升序排列

5,前10个退步最快(或者说进步最少),后10个进步最多

 

0
赵开锦
赵开锦
可能我没有说清楚,进步、退步指的是相对其他同学的名次的进步与退步,不是总分数的进步与退步
0
Grrrr
Grrrr
其实相对其他同学进步退步, 就是班级成绩排名. 把上次考试的排名和本次的进行比照. 应该就是你想要的.
0
赵开锦
赵开锦
我知道的,其实基本算法我是知道的,我就是问有没有优化的余地
0
Y-QTCe
Y-QTCe
怎样证明一个算法是最优,这个很困难啊
0
Grrrr
Grrrr

我觉得用sql查询出来的效率已经很不错了。你这个逻辑完全可以用sql写出来。

0
赵开锦
赵开锦

嗯,感谢方旭同学的回复,已经采用空间换时间的方法解决。

增加一个学生名次计算表

id、学生id、班级id、考试id、本次考试名次、上次考试名次、进步名次

增加一个名次计算功能,当每次考试的成绩录入完成后,做一个名次计算

这样即可以实现查询最快了。

返回顶部
顶部