100万考生两两比较的结果多达3600亿条，该如何设计算法

欢迎您:游客帮助

我参与的帖子

100万考生两两比较的结果多达3600亿条，该如何设计算法 [已结贴,结贴人:jakieken]

jakieken
jakieken
等级:

发表于：2008-04-26 13:47:21 楼主

现在要对某次考试的3000多名考生的选择题答案进行两两分析，如果按照排列组合要有将近五百万条结果，计算时间很长。如果有100万考生那么比较的结果是3600亿条，用普通计算机的计算时间将会以“日”来计算。大家有什么优化的算法吗？

问题点数：200 回复次数：93 修改删除举报引用回复

akirya
坏[其实偶不是什么所谓的坏人]
等级:

发表于：2008-04-26 13:50:541楼得分:0

怎么两两个分析法

修改删除举报引用回复

Chiyer
星羽
等级:

发表于：2008-04-26 14:00:202楼得分:0

比较些什么？具体要得到什么样的结果？

修改删除举报引用回复

wuyu637
乱世藏大米（继续收藏中）
等级:

发表于：2008-04-26 14:01:543楼得分:0

楼主的意思是比较选择题的答案的是否相同吧？

修改删除举报引用回复

jakieken
jakieken
等级:

发表于：2008-04-26 14:02:034楼得分:0

就是如果只有a，b，c三个考生，我们就要对ab，ac，bc考生的答案进行分析，看有几个相同选项，其中又有几个是答错相同，几个答对相同，进行类似的分析。如果考生数量很大达100万，组合就会有上万亿条，就需要一个比较好的算法了。

修改删除举报引用回复

Chiyer
星羽
等级:

发表于：2008-04-26 14:04:515楼得分:0

这样不就是每个学生几乎要和其他所有的比一次 - -

是不是检测是否抄袭的 - -b

修改删除举报引用回复

jakieken
jakieken
等级:

发表于：2008-04-26 14:08:506楼得分:0

不知道我描述清楚了没有，首先就是一个组合的问题，n个考生里面任取两个，然后是对这两个考生的答案进行分析，算有几个是相同选项，几个错误相同，几个是正确相同，还有各自答案的正确和错误个数。

修改删除举报引用回复

jakieken
jakieken
等级:

发表于：2008-04-26 14:12:077楼得分:0

5楼的兄弟说的很对，就是检测抄袭的，所以要两两比较

修改删除举报引用回复

ugg
逸学堂
等级:

发表于：2008-04-26 14:14:538楼得分:0

把所有题的正确答案放入一个数组比如
int key[]={2,4,8,16...};// 2,4,8,16表示ABCD选项
把考生的选择答案放入
int que[]={8,4,8,16...}; // 2,4,8,16表示ABCD选项

数组key与que进行异或比较，如果que[i]==0;
即认为que[i]错误,否则考生选择正确。

修改删除举报引用回复

ugg
逸学堂
等级:

发表于：2008-04-26 14:16:119楼得分:0

理解错误了，以为找正确答案那

修改删除举报引用回复

arong1234
阿荣
等级:

发表于：2008-04-26 14:27:1710楼得分:100

这个就是"hash"的妙用了。你不能做两两比较，因为这样会导致计算量变成N^2的
简单的办法就是对于每个考生的答案生成一个hash码，这样我们只要比较对应的hash 码一样的情况一样就可以了。
问题的关键变成怎么去做hash,这需要根据具体情况进行设计，一个草案是（楼主要根据这个方向自己充实，我不会给你提供代码或者提供更复杂的设计的）：
a) 把选择题每几题进行一个组合,假定每个题目有四种答案，需要占据2bit数据，这样一个16位的数据，我们可以表达8个题目的答案。这样我们每8题一组，填充成一个16bit的整数(也就是一个WORD)
b) 对于一份考卷中，我们可以得到一组这样的WORD，我们把他们彼此异或，得到一个WORD
c) 建立一个有65536个元素的array，每个array里包含一个链表，第n个链表中保存的元素是上述方法计算得到的hash code为n的试卷

假如一个试卷计算的hash code为k，则我们去查询第k个链表，如果这个链表为空，则说明没有答案相同的试卷，如果不为空，则一一比较这个试卷和链表中的试卷（这是因为不同答案的hash code可能一样），这样你要比较的数量会大多缩小）

修改删除举报引用回复

akirya
坏[其实偶不是什么所谓的坏人]
等级:

发表于：2008-04-26 14:30:5611楼得分:0

用arong1234的办法不错

修改删除举报引用回复

arong1234
阿荣
等级:

发表于：2008-04-26 14:31:4512楼得分:0

0

修改删除举报引用回复

OpenHero
开勇,kelvin
等级:

发表于：2008-04-26 14:34:5413楼得分:0

http://topic.csdn.net/u/20071226/15/e277802f-8b31-4222-8ab2-90605190f822.html
intel的多核编程竞赛有一期是房间分配问题～
和lz的题目是一样的
上面的链接是我写的一个代码
或许能帮上lz的忙
这里求得不是最优解，只是在很短的时间之内求相对最优解
ps：linux下安装intel TBB可以运行
lz可以看看intel多核比赛的房间分配问题的相关讨论

修改删除举报引用回复

ugg
逸学堂
等级:

发表于：2008-04-26 14:37:1114楼得分:0

不知道我描述清楚了没有，首先就是一个组合的问题，n个考生里面任取两个，然后是对这两个考生的答案进行分析，算有几个是相同选项，几个错误相同，几个是正确相同，还有各自答案的正确和错误个数。
~~~~~~~~~~~~
这种统计内容太多了，无论如何也难逃两两比较计算过程。具体比较过程可以参考我上面提到的那种算法。

其实我想这种判断抄袭的方法不科学。我们都是从小到大考过来的。考试之前先给大家分考号，然后分考试教室，然后大家按考号“龙字形”考试，更可怕的是选择题还有AB卷。所以即使两两比较抄袭也应该是先分小组然后再分
AB卷，然后在小组内比较。如果所有的人都两两比较，即使他们所有的对错都相同，但是他们不在一个教室内考试
也不能算是抄袭啊。

所以，我觉得出这道算法的人，他自己也没有好的算法，只是想看看做题者的考虑角度和方法。

修改删除举报引用回复

jakieken
jakieken
等级:

发表于：2008-04-26 14:58:5315楼得分:0

其实我的意思是如果有100万个考生，我想知道这些考生中哪两个存在作弊的可能，所以要对他们的答案（选择题A,B,C，D）进行分析，通过计算任意两个考生之间有多少错同选项（选错且都选了同一个错误选项），计算各自的错同率（错同选项个数除以各自答错题目数目），如果某两个考生之间的错同率远远高于此次考试的平均错同率的话这两个考生就存在作弊可能，不知我描述是否清楚。

修改删除举报引用回复

arong1234
阿荣
等级:

发表于：2008-04-26 15:02:3416楼得分:0

那就是我说得那个办法了

引用 15 楼 jakieken 的回复:
其实我的意思是如果有100万个考生，我想知道这些考生中哪两个存在作弊的可能，所以要对他们的答案（选择题A,B,C，D）进行分析，通过计算任意两个考生之间有多少错同选项（选错且都选了同一个错误选项），计算各自的错同率（错同选项个数除以各自答错题目数目），如果某两个考生之间的错同率远远高于此次考试的平均错同率的话这两个考生就存在作弊可能，不知我描述是否清楚。

修改删除举报引用回复

N_IThero
NIThero
等级:

发表于：2008-04-26 15:52:4417楼得分:0

"hash"的妙用
顶 arong1234

修改删除举报引用回复

andy_cai
菜鸟
等级:

发表于：2008-04-26 16:38:3718楼得分:0

arong1234的方法不错
学习

修改删除举报引用回复

zlcs8921
摄氏37度
等级:

发表于：2008-04-26 17:27:3219楼得分:0

hash 先一次遍历，对每个学生的信息进行hash ，
然后再比较。

修改删除举报引用回复

akirya
坏[其实偶不是什么所谓的坏人]
等级:

发表于：2008-04-26 17:43:4820楼得分:0

要是100w考生

有两个完全一样的答案,一个在北京,一个在上海.
这也算作弊?

修改删除举报引用回复

magicway
等级:

发表于：2008-04-26 17:56:4621楼得分:0

引用 20 楼 akirya 的回复:
要是100w考生

有两个完全一样的答案,一个在北京,一个在上海.
这也算作弊?

顶!!!!
就是嘛...怎么?100万人在一个考场考试?

修改删除举报引用回复

lanmuyi
lanmuyi
等级:

发表于：2008-04-26 17:58:3222楼得分:0

查找抄袭应该先从其他角度考虑否定绝大部分不可能作弊的考生

比如不在同一考场的考生，可以通过他们的准考证号进行判断

否则处理起来很麻烦，而且按照概率分析肯定有一样的答案

最后得出的数据不一定能说明问题

修改删除举报引用回复

thirdapple
.:RNPA:.陨落雕 - 非无圣主，岂乏明时
等级:

发表于：2008-04-26 18:05:3023楼得分:0

题目只有4个选项，一共不会超过200道题，就可以用800个列表来记录回答每个答案的学生编号。
对这些编号进行排序。最大所用时间不会超过400亿次，代码不节省的话大约要半个小时。
然后，对200道题进行统计就可以了，这样时间复杂度似乎会降低，我还没想好。

修改删除举报引用回复

goscan
gosan
等级:

发表于：2008-04-26 18:05:3024楼得分:0

好像arong1234的方法只能找出完全一样的答案。。

修改删除举报引用回复

MagiSu
黄埔军校高材生──黄色知识普及军校
等级:

发表于：2008-04-26 18:14:3825楼得分:0

arong的看法有不足。因为考试作弊的形势已经不是那么简单了。作弊的人会有意将其中的一些题目做的不一样，这样就失去了比较的意义。要求的是做错的题的相似率。我认为没有一个很好的方法来做出判断。再说了，譬如张三和李四都做只错了一道题，错的一样，他们考试坐在一起。这样就没有办法判定，因为大家很可能掉进题目设置的陷阱之中，这样错的一样的可能性就会非常大。一个典型的例子是我上初中的时候学英文，looking forward to 后面跟随动名词，是个特例，但是很多人都不慎错选了动词原型。

修改删除举报引用回复

wmj007
海鸟
等级:

发表于：2008-04-26 18:38:3626楼得分:0

看了大家的高论,题目的环境可能不是很好的比喻,但要有一个问题很明确,就是实现这种需求,大数据的情况下如何实现,能高效的得到结果

修改删除举报引用回复

laolaoliu2002
我微微一笑,轻轻地竖起中指!!!!
等级:

发表于：2008-04-26 18:39:0927楼得分:0

引用 10 楼 arong1234 的回复:
这个就是"hash"的妙用了。你不能做两两比较，因为这样会导致计算量变成N^2的
简单的办法就是对于每个考生的答案生成一个hash码，这样我们只要比较对应的hash 码一样的情况一样就可以了。
问题的关键变成怎么去做hash,这需要根据具体情况进行设计，一个草案是（楼主要根据这个方向自己充实，我不会给你提供代码或者提供更复杂的设计的）：
a) 把选择题每几题进行一个组合,假定每个题目有四种答案，需要占据2bit数据，这样一…

修改删除举报引用回复

Inhibitory
等级:

发表于：2008-04-26 18:40:4628楼得分:0

太扯蛋了, 100万考生, 也就只有几十个选项, 出现雷同的也正常, 难道就这样武断别人是作弊?

修改删除举报引用回复

rickone
RickOne
等级:

发表于：2008-04-26 19:11:2229楼得分:80

1，用一个向量描述一份答卷，包括所有和你要的结果相关的信息，比如AB卷，考场号，第几题等，这个向量像这样：

X=(x1,x2,...xn)

x1=0 A卷 x1=1 B卷
x2=0 001考场 x2=1 002考场 ...
x3=0 1题答案A x3=1 1题答案B ...

这是它的含义，也是数据结构，现在来描述它的相似度，可以用距离来描述

D(X,Y)=sqrt((X.x1-Y.x1)^2+(X.x2-Y.x2)^2+...)

再重新看一下D()的意义，它是指X和Y的距离，如果X=Y，必然D(X,Y)=0，如果X和Y很相似（可疑作弊）那D(X,Y)很小，如果X和Y差别很大，那D(X,Y)也很大，最后我们就求D(X,Y)最小的那对。

这不是很合理，可以加权，为了使运算简单，改用绝对值也可以

D'(X,Y)= ¦X-Y ¦*C= ¦X.x1-Y.x1 ¦*C1+ ¦X.x2-Y.x2 ¦*C2+...+ ¦X.xn-Y.xn ¦*Cn

先设计好这个C，比如A卷和B卷，他们作弊的可能就很低，题不同，所以C1可以是很大的数，还如，座位号如果连在一起，那作弊的可能也大，题目的难易，一道很难的题目，如果刚好答得一样，那抄的可能也大，如果简单题，那都可能答对，那作弊的可能小，系数就设计小些。

2，问题就成了，给出有限n维向量空间X和距离函数D,求D(X,Y)最小的两对X，Y，或者是求一个子集H(x,m)，它有x张开，x是那个作弊的学生，同时对任意y属于H(x)满足D(x,y) <m，m为某个阈值。

这样考虑可不可以？

修改删除举报引用回复

jakieken
jakieken
等级:

发表于：2008-04-26 19:27:2330楼得分:0

如果某两个考生之间的错同率(错误选项相同的概率)远远高于此次考试的平均错同率的话这两个考生就存在作弊可能

引用 28 楼 Inhibitory 的回复:
太扯蛋了, 100万考生, 也就只有几十个选项, 出现雷同的也正常, 难道就这样武断别人是作弊?

修改删除举报引用回复

zhoupo
Hen‵→鋭
等级:

发表于：2008-04-26 23:13:5531楼得分:0

路过学习

修改删除举报引用回复

jeff_nie
多C多漂亮!
等级:

发表于：2008-04-26 23:16:3732楼得分:0

MARK

修改删除举报引用回复

liujin_shunzi
顺子
等级:

发表于：2008-04-27 02:35:3033楼得分:0

100万个学生不可能同一个考场
为什么100万个都要两两对比呢？

修改删除举报引用回复

liujin_shunzi
顺子
等级:

发表于：2008-04-27 02:37:0234楼得分:0

确切第说100万个学生不可能同一个课室考试
只要在同一个课室考虑的考生进行两两对比就可以检测是否作弊了

修改删除举报引用回复

leiXure
多写了三五行
等级:

发表于：2008-04-27 04:39:4635楼得分:0

1. 两两比较
最直接的方法是顺次遍历考生，将当前考生的成绩与排其后的考生的成绩一一对比

C/C++ code


    struct StudentAnswer;
    typedef std::vector<StudentAnswer> StudentAnswerArray;

    inline void checkStudentAnswer(const StudentAnswer& answer)
    {
        // 在这里统计单个学生的成绩
</