以文本方式查看主题 - 中文XML论坛 - 专业的XML技术讨论区 (http://bbs.xml.org.cn/index.asp) -- 『 算法理论与分析 』 (http://bbs.xml.org.cn/list.asp?boardid=60) ---- [讨论]大数据量的统计 (http://bbs.xml.org.cn/dispbbs.asp?boardid=60&rootid=&id=31887) |
-- 作者:binaryluo -- 发布时间:5/8/2006 9:54:00 AM -- [讨论]大数据量的统计 问题描述: 有1000000个随机数,每个随机数都是16字节(128bits),它们被保存在文件里面,格式如下: --------------------------------------- /* 序号 随机数*/ 1 aeb42ead5f67983e 2 db32a10a76f3f1b5 …… --------------------------------------- 现在为了衡量我的随机数生成算法,所以需要对这1000000个随机数进行统计,看每个随机数是否有重复的,如果出现重复,要记录下:随机数、重复的随机数的序号、重复的次数。 我的分析: 大家有没有什么好的想法或建议的一起来交流下。 P.S.这个题目有点类似于baidu招聘时候的一个面试题(大体意思如下,具体题目记不清了): |
-- 作者:Logician -- 发布时间:5/8/2006 3:52:00 PM -- 你的意思是不是这样,要求: 1、对内存空间需求量足够地小。 2、对外存访问次数足够地少(最好每个数据读取只读写一、两次)。 3、在内存中的操作次数还不能太大(为了达到前两个目标,常数项可以大一些,但渐进复杂度还是要控制住)。 |
-- 作者:Logician -- 发布时间:5/8/2006 4:09:00 PM -- 我想到的方法还是“选择置换排序”+“多路归并”这样的外排序方法。 注意到,在最后一次归并时,就可以直接计数了。 |
-- 作者:binaryluo -- 发布时间:5/8/2006 5:04:00 PM --
恩,是的。 |
-- 作者:binaryluo -- 发布时间:5/8/2006 5:12:00 PM --
谢谢Logician兄。 另外就是我一个同学他想到了一种方法: 我觉得他这个方法从算法角度分析应该还没有这种情况好——每条记录与它后面的所有记录比较,但是他说他测试的结果却是他的方法的执行速度比刚才说的那种情况的速度快很多。 Logician兄能谈谈你的看法吗? |
-- 作者:Logician -- 发布时间:5/8/2006 8:58:00 PM -- 能解释一下“统计方法是第 i 条记录与它后面的 n - i 条记录比较”和“每条记录与它后面的所有记录比较”的意思吗? 关于实现时的速度,我觉得影响它的原因有很多。 比如:最初分类(把它划成256个子集)时,如果是要节省内存,就要在一定情况下把分好类的随机数写回硬盘。这个工作如果由操作系统来控制的话,操作系统应该会按页面进行调度。这种情况下,操作系统的具体调度策略、划分存储区时设置的存储区大小(那256个存储区的大小是静态分配还是动态增长呢?初始时设为多大呢?)、系统目前空闲的物理内存空间大小似乎对性能都会有比较大的影响。 你说的“每条记录与它后面的所有记录比较”是说:对第i条记录,把它与第i+1条直至第1000000条记录依次比较,如果有相同的,就删除那个相同的,并把该条记录的“重复度”加1。是这样吗? 如果是的话,我觉得这样似乎比较低效。因为它的渐进复杂度是O(n^2)的。 如果你同学的意思是说把它划成256块,并且只在块内逐一比较,其渐进复杂度也是O(n^2)的,只不过他的n大约是你的n的1/256。也就说是,假如你的方法需要做比较k*n^2次比较的话,他的方法大约只需要做k* 256 * (n/256)^2 = k*(n^2)/256 次。 但这种方法的话,我觉得还不如分成256组之后,逐一进行内排序,然后再数。我觉得这样应该比你同学现在的方法还要快些。 另外,你同学的方法,当待统计的随机数数量再增加几个数量级时,似乎就不适用的…… |
-- 作者:binaryluo -- 发布时间:5/8/2006 11:24:00 PM --
“统计方法是第 i 条记录与它后面的 n - i 条记录比较”和“每条记录与它后面的所有记录比较”指的是第一条跟他后面的N-1条比较,第二条跟他后面的N-2条比较,第三条跟他后面的N-3条比较……以此类推,一直到最后一条。这样的时间复杂度为O(n方),而且空间也是相当耗费,所以不可取。 我同学那种开多个线程的方法在单CPU的机子上实际性能我觉得也跟上述的那种差不多甚至会更差。因为多线程在指令级上仍然是顺序执行的,而且他的那种方法还涉及到线程的切换等,也要消耗CPU时间。但是他说他的时间比上述方法快得多我就有点不大明白了。。。。 |
-- 作者:Logician -- 发布时间:5/9/2006 2:08:00 AM -- 你是说你同学把256个线程同时开起来?@_@ 我觉得如果一个一个开的话,效果应该会好一些。(不太清楚Windows在线程调度方面的策略,不知道对于256个线程同时开、内存空间又有限的情况下,Windows是不是有什么好的调度方法保证一定的效率) 但正如我刚才分析过的,他的方法需要的总比较次数你的少很多。所以,只要Windows能有效地避免因多线程争用内存空间而造成的“颠簸”(我觉得是可能的,因为你的数据总共才16MB而已,腾出10来兆的物理内存空间并不是难事,至于线程切换的开销,一般也就是总CPU时间的百分之几甚至千分之几,实在算不上什么的),速度快一些是自然的(我们前面算过了,他的方法需要做的比较数是你的方法的1/256,这种几百倍的差距,绝对不是那一点线程调度开销能弥补的)。 简单地说,我觉得如果要测试这种External算法(外排序、外查找等)的话,得要数据量足够大(最好是拿不同规模的数据多次测试),而且注意监控(最好是能手动控制)内存使用量,测出来的数据才有意义。你这里用固定的16MB数据进行测试,很难说它代表了External算法的优劣…… |
-- 作者:binaryluo -- 发布时间:5/9/2006 10:26:00 AM --
明白了。3q!^_^ |
W 3 C h i n a ( since 2003 ) 旗 下 站 点 苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》 |
6,800.781ms |