中文XML论坛--[讨论]大数据量的统计

新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚

XML论坛

W3CHINA.ORG讨论区

计算机科学论坛

SOAChina论坛

Blog

开放翻译计划

新浪微博

首页

软件下载

资料下载

核心成员

帮助

>> We choose to study algorithmic problems, not because they are easy, but because they are hard.

[返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『算法理论与分析』 → [讨论]大数据量的统计

◇查看新帖 ◇ 用户列表 ◇

(订阅本版)

您是本帖的第 9852 个阅读者　　

*	贴子主题： [讨论]大数据量的统计	举报打印推荐 IE收藏夹
	本主题类别:

binaryluo

  威望：6
  等级：研二(Pi-Calculus看得一头雾水)(版主)
  文章：679
  积分：5543
  门派：IEEE.ORG.CN
  注册：2005/2/19

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	楼主

[讨论]大数据量的统计

问题描述：
有1000000个随机数，每个随机数都是16字节（128bits），它们被保存在文件里面，格式如下：
---------------------------------------
/* 序号     随机数*/
    1         aeb42ead5f67983e
    2         db32a10a76f3f1b5
   ……
---------------------------------------
现在为了衡量我的随机数生成算法，所以需要对这1000000个随机数进行统计，看每个随机数是否有重复的，如果出现重复，要记录下：随机数、重复的随机数的序号、重复的次数。
我的分析：
要对这1000000个随机数进行统计，最好先对其进行排序，排序算法我选择了快速排序，时间复杂度O(nlgn)。但是由于快速排序是内存排序法，所以要先把这1000000个16字节的数据读到内存里才能进行。1000000的数据量说大也不是很大，但说小也不小，还是会消耗很大的一块内存的，而且这是一块连续的内存。但是如果用外存排序算法的话时间复杂度又很高。
大家有没有什么好的想法或建议的一起来交流下。
P.S.这个题目有点类似于baidu招聘时候的一个面试题（大体意思如下，具体题目记不清了）：
有4G的一个日志文件，该文件中保存着人们检索的关键字记录。该文件中一行保存着一个关键字，每行最多256个字符。现在要将这个日志文件中的关键字进行一个统计，统计出检索次数最多的前100个关键字，并按检索次数将这100个关键字列出。

   收藏   分享
顶(0)

2006/5/8 9:54:00

Logician

  威望：9
  头衔：逻辑爱好者
  等级：研三(收到IBM CRL的Offer了)(版主)
  文章：1219
  积分：10357
  门派：IEEE.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第2楼

你的意思是不是这样，要求：
1、对内存空间需求量足够地小。
2、对外存访问次数足够地少（最好每个数据读取只读写一、两次）。
3、在内存中的操作次数还不能太大（为了达到前两个目标，常数项可以大一些，但渐进复杂度还是要控制住）。
----------------------------------------------
Three passions, simple but overwhelmingly strong,
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
- Bertrand Russell

2006/5/8 15:52:00

Logician

  威望：9
  头衔：逻辑爱好者
  等级：研三(收到IBM CRL的Offer了)(版主)
  文章：1219
  积分：10357
  门派：IEEE.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第3楼

我想到的方法还是“选择置换排序”+“多路归并”这样的外排序方法。
注意到，在最后一次归并时，就可以直接计数了。
----------------------------------------------
Three passions, simple but overwhelmingly strong,
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
- Bertrand Russell

2006/5/8 16:09:00

binaryluo

  威望：6
  等级：研二(Pi-Calculus看得一头雾水)(版主)
  文章：679
  积分：5543
  门派：IEEE.ORG.CN
  注册：2005/2/19

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第4楼

以下是引用Logician在2006-5-8 15:52:00的发言：
你的意思是不是这样，要求：
1、对内存空间需求量足够地小。
2、对外存访问次数足够地少（最好每个数据读取只读写一、两次）。
3、在内存中的操作次数还不能太大（为了达到前两个目标，常数项可以大一些，但渐进复杂度还是要控制住）。

恩，是的。

2006/5/8 17:04:00

binaryluo

  威望：6
  等级：研二(Pi-Calculus看得一头雾水)(版主)
  文章：679
  积分：5543
  门派：IEEE.ORG.CN
  注册：2005/2/19

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第5楼

以下是引用Logician在2006-5-8 16:09:00的发言：
我想到的方法还是“选择置换排序”+“多路归并”这样的外排序方法。
注意到，在最后一次归并时，就可以直接计数了。

谢谢Logician兄。
另外就是我一个同学他想到了一种方法：
先对这1000000个随机数分类，分类的方法是以随机数的第一个字节来分，若第一字节相同的就归为一类，这样分下来的结果最多可能存在256类（一个字节能表示的数最大是256）。然后在分出来的这256个子集中分别进行统计，统计方法是第 i 条记录与它后面的 n － i 条记录比较。而对于这256个子集的比较每个子集开一个线程运行。
我觉得他这个方法从算法角度分析应该还没有这种情况好——每条记录与它后面的所有记录比较，但是他说他测试的结果却是他的方法的执行速度比刚才说的那种情况的速度快很多。
Logician兄能谈谈你的看法吗？

2006/5/8 17:12:00

Logician

  威望：9
  头衔：逻辑爱好者
  等级：研三(收到IBM CRL的Offer了)(版主)
  文章：1219
  积分：10357
  门派：IEEE.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第6楼

能解释一下“统计方法是第 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组之后，逐一进行内排序，然后再数。我觉得这样应该比你同学现在的方法还要快些。
另外，你同学的方法，当待统计的随机数数量再增加几个数量级时，似乎就不适用的……
到时，为了减小每个块的尺寸（以免第二步比较时因内存不够而反复从内存中调入调出数据）就得增加块数（比如，根据前2个或3个字节分块），但这样一来，内存中的块数太多，可能导致每个块中才写了几个数就不得不写回（因为总的容量已经满了），而我们知道，往硬盘中写入一个page（往往是几KB的大小）和写入一个字节所需的时间是差不多的，一次往硬盘中写入几个字节是不划算的……
----------------------------------------------
Three passions, simple but overwhelmingly strong,
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
- Bertrand Russell

2006/5/8 20:58:00

binaryluo

  威望：6
  等级：研二(Pi-Calculus看得一头雾水)(版主)
  文章：679
  积分：5543
  门派：IEEE.ORG.CN
  注册：2005/2/19

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第7楼

以下是引用Logician在2006-5-8 20:58:00的发言：
能解释一下“统计方法是第 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组之后，逐一进行内排序，然后再数。我觉得这样应该比你同学现在的方法还要快些。
另外，你同学的方法，当待统计的随机数数量再增加几个数量级时，似乎就不适用的……
到时，为了减小每个块的尺寸（以免第二步比较时因内存不够而反复从内存中调入调出数据）就得增加块数（比如，根据前2个或3个字节分块），但这样一来，内存中的块数太多，可能导致每个块中才写了几个数就不得不写回（因为总的容量已经满了），而我们知道，往硬盘中写入一个page（往往是几KB的大小）和写入一个字节所需的时间是差不多的，一次往硬盘中写入几个字节是不划算的……

“统计方法是第 i 条记录与它后面的 n － i 条记录比较”和“每条记录与它后面的所有记录比较”指的是第一条跟他后面的N-1条比较，第二条跟他后面的N-2条比较，第三条跟他后面的N-3条比较……以此类推，一直到最后一条。这样的时间复杂度为O(n方)，而且空间也是相当耗费，所以不可取。
我同学那种开多个线程的方法在单CPU的机子上实际性能我觉得也跟上述的那种差不多甚至会更差。因为多线程在指令级上仍然是顺序执行的，而且他的那种方法还涉及到线程的切换等，也要消耗CPU时间。但是他说他的时间比上述方法快得多我就有点不大明白了。。。。

2006/5/8 23:24:00

Logician

  威望：9
  头衔：逻辑爱好者
  等级：研三(收到IBM CRL的Offer了)(版主)
  文章：1219
  积分：10357
  门派：IEEE.ORG.CN
  注册：2005/3/12

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第8楼

你是说你同学把256个线程同时开起来？@_@
我觉得如果一个一个开的话，效果应该会好一些。（不太清楚Windows在线程调度方面的策略，不知道对于256个线程同时开、内存空间又有限的情况下，Windows是不是有什么好的调度方法保证一定的效率）
但正如我刚才分析过的，他的方法需要的总比较次数你的少很多。所以，只要Windows能有效地避免因多线程争用内存空间而造成的“颠簸”（我觉得是可能的，因为你的数据总共才16MB而已，腾出10来兆的物理内存空间并不是难事，至于线程切换的开销，一般也就是总CPU时间的百分之几甚至千分之几，实在算不上什么的），速度快一些是自然的（我们前面算过了，他的方法需要做的比较数是你的方法的1/256，这种几百倍的差距，绝对不是那一点线程调度开销能弥补的）。
简单地说，我觉得如果要测试这种External算法（外排序、外查找等）的话，得要数据量足够大（最好是拿不同规模的数据多次测试），而且注意监控（最好是能手动控制）内存使用量，测出来的数据才有意义。你这里用固定的16MB数据进行测试，很难说它代表了External算法的优劣……
----------------------------------------------
Three passions, simple but overwhelmingly strong,
have governed my life: the longing for love, the
search for knowledge, and unbearable pity for the
suffering of mankind.
- Bertrand Russell

2006/5/9 2:08:00

binaryluo

  威望：6
  等级：研二(Pi-Calculus看得一头雾水)(版主)
  文章：679
  积分：5543
  门派：IEEE.ORG.CN
  注册：2005/2/19

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

	第9楼

以下是引用Logician在2006-5-9 2:08:00的发言：
你是说你同学把256个线程同时开起来？@_@
我觉得如果一个一个开的话，效果应该会好一些。（不太清楚Windows在线程调度方面的策略，不知道对于256个线程同时开、内存空间又有限的情况下，Windows是不是有什么好的调度方法保证一定的效率）
但正如我刚才分析过的，他的方法需要的总比较次数你的少很多。所以，只要Windows能有效地避免因多线程争用内存空间而造成的“颠簸”（我觉得是可能的，因为你的数据总共才16MB而已，腾出10来兆的物理内存空间并不是难事，至于线程切换的开销，一般也就是总CPU时间的百分之几甚至千分之几，实在算不上什么的），速度快一些是自然的（我们前面算过了，他的方法需要做的比较数是你的方法的1/256，这种几百倍的差距，绝对不是那一点线程调度开销能弥补的）。
简单地说，我觉得如果要测试这种External算法（外排序、外查找等）的话，得要数据量足够大（最好是拿不同规模的数据多次测试），而且注意监控（最好是能手动控制）内存使用量，测出来的数据才有意义。你这里用固定的16MB数据进行测试，很难说它代表了External算法的优劣……

明白了。3q!^_^

2006/5/9 10:26:00

GoogleAdSense

  等级：大一新生
  文章：1
  积分：50
  门派：无门无派
  院校：未填写
  注册：2007-01-01

	广告

2025/1/5 2:24:44

本主题贴数9，分页： [1]

管理选项：修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告


	W 3 C h i n a ( since 2003 ) 旗下站点苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》	109.375ms