本站首页    管理页面    写新日志    退出


«February 2026»
日一二三四五六
1234567
891011121314
15161718192021
22232425262728


公告
暂无公告...

我的分类（专题）

日志更新

最新评论

留言板

链接


Blog信息
blog名称:
日志总数:32
评论数量:9
留言数量:-1
访问次数:112605
建立时间:2008年12月3日




记得看百度某人博客，弱问一题
原创空间

liangbin 发表于 2008/12/3 23:52:44

发信人: pennyliang (pennyliang), 信区: SearchEngineTech标  题: 记得看百度某人博客，弱问一题发信站: 水木社区 (Tue Nov 27 05:34:21 2007), 站内    此博客好像是周利民同学的，说百度入职工程师都要做一个扫描千万量级的文件，要求在10分钟内完成。    我想了解一下实现细节，除了用多线程把CPU和I/O重叠起来的技术外，还用了那些special的技术呢？    另外这个千万量级的文件是文本行呢？还是一个个序列化后的数据对象啊？哪位达人介绍一下啊。--※ 来源:·水木社区 http://newsmth.net·[FROM: 58.30.83.*] [本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部] 2 发信人: pennyliang (pennyliang), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Tue Nov 27 06:17:41 2007), 站内我说的数据有误，原文如下：百度招聘的工程师在加入公司后，有一道入门练习题，就是编写一个数据扫描分析程序，要求写出的程序能在1分钟之内扫描分析完千万量级的数据，才算及格。高水平的程序员可以利用高效的算法在10秒以内解决问题，甚至只要六七秒。但如果没用对算法，花一星期的时间，也做不到1分钟之内。大家可以设想一下，百度有十亿以上的网页，如果要在一周甚至三天内处理一遍，平均每秒处理要多少个？每天1亿次的检索又意味着峰值时每秒要处理多少次检索？事实上，针对一个问题，我们可以想出很多的算法，但如果效率不高，是无法真正投入使用的。 link:http://hi.baidu.com/wujixiaofeng/blog/item/f2e7dbf24e0f2212b07ec5a1.html【 在 pennyliang (pennyliang) 的大作中提到: 】:     此博客好像是周利民同学的，说百度入职工程师都要做一个扫描千万量级的文件，要求在10分钟内完成。:     我想了解一下实现细节，除了用多线程把CPU和I/O重叠起来的技术外，还用了那些special的技术呢？:     另外这个千万量级的文件是文本行呢？还是一个个序列化后的数据对象啊？哪位达人介绍一下啊。--※ 来源:·水木社区 http://newsmth.net·[FROM: 58.30.83.*] [本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部] 3 发信人: pennyliang (pennyliang), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Tue Nov 27 19:39:39 2007), 站内我来猜想一下啊。可能百度搞一个千万行的一个文件，然后10秒内在控制台输出某一行的某一个数，算作扫描一遍，不知道版上有没有人说说怎么搞。【 在 pennyliang (pennyliang) 的大作中提到: 】: 我说的数据有误，原文如下：: 百度招聘的工程师在加入公司后，有一道入门练习题，就是编写一个数据扫描分析程序，要求写出的程序能在1分钟之内扫描分析完千万量级的数据，才算及格。高水平的程序员可以利用高效的算法在10秒以内解决问题，甚至只要六七秒。但如果没用对算法，花一星期的时间，也做不到1分钟之内。: 大家可以设想一下，百度有十亿以上的网页，如果要在一周甚至三天内处理一遍，平均每秒处理要多少个？每天1亿次的检索又意味着峰值时每秒要处理多少次检索？事实上，针对一个问题，我们可以想出很多的算法，但如果效率不高，是无法真正投入使用的。 : ...................--※ 来源:·水木社区 http://newsmth.net·[FROM: 58.30.83.*] [本篇全文] [回复文章] [本篇作者：youngvonlee] [回信给作者] [进入讨论区] [返回顶部] 4 发信人: youngvonlee (cls), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Tue Dec  4 10:01:39 2007), 站内同问，另外，周利民同学的百度空间地址是？--自然语言处理，算法，嵌入式开发。python.※ 来源:·水木社区 http://newsmth.net·[FROM: 211.144.112.*] [本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部] 5 发信人: pennyliang (pennyliang), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Tue Dec  4 20:57:16 2007), 站内问了个百度朋友，据说是有10分钟内排序千万量级的数据，采用naive的多路归并排序就可以了，而且还不用本地（空间复杂度O(1)）的归并排序。。。古老搜索引擎入门书（MG）中提到过一种归并方法，称作R路归并（R远小于临时归并段数）。不知道搜索引擎怎么做这种归并的，那位达人出来介绍一下。。。【 在 pennyliang (pennyliang) 的大作中提到: 】: 我说的数据有误，原文如下：: 百度招聘的工程师在加入公司后，有一道入门练习题，就是编写一个数据扫描分析程序，要求写出的程序能在1分钟之内扫描分析完千万量级的数据，才算及格。高水平的程序员可以利用高效的算法在10秒以内解决问题，甚至只要六七秒。但如果没用对算法，花一星期的时间，也做不到1分钟之内。: 大家可以设想一下，百度有十亿以上的网页，如果要在一周甚至三天内处理一遍，平均每秒处理要多少个？每天1亿次的检索又意味着峰值时每秒要处理多少次检索？事实上，针对一个问题，我们可以想出很多的算法，但如果效率不高，是无法真正投入使用的。 : ...................--※ 修改:·pennyliang 于 Dec  4 20:57:50 修改本文·[FROM: 58.30.83.*]※ 来源:·水木社区 http://newsmth.net·[FROM: 58.30.83.*] [本篇全文] [回复文章] [本篇作者：godking] [回信给作者] [进入讨论区] [返回顶部] 6 发信人: godking (oh my godking), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Tue Dec  4 21:35:37 2007), 站内去算法版问，会有一堆人跳出来。。【 在 pennyliang (pennyliang) 的大作中提到: 】: 问了个百度朋友，据说是有: 10分钟内排序千万量级的数据，采用naive的多路归并排序就可以了，而且还不用本地（空间复杂度O(1)）的归并排序。。。: 古老搜索引擎入门书（MG）中提到过一种归并方法，称作R路归并（R远小于临时归并段数）。: ...................--※ 来源:·水木社区 newsmth.net·[FROM: 60.28.238.*] [本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部] 7 发信人: pennyliang (pennyliang), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Tue Dec  4 21:58:28 2007), 站内不混算法版很多年。。。这种问题主要是工程经验，算法版能给出的解答想都想的出来，就那么些。。。【 在 godking (oh my godking) 的大作中提到: 】: 去算法版问，会有一堆人跳出来。。--※ 修改:·pennyliang 于 Dec  4 22:00:39 修改本文·[FROM: 58.30.83.*]※ 来源:·水木社区 http://newsmth.net·[FROM: 58.30.83.*] [本篇全文] [回复文章] [本篇作者：godking] [回信给作者] [进入讨论区] [返回顶部] 8 发信人: godking (oh my godking), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Wed Dec  5 09:42:29 2007), 站内好吧，呵呵【 在 pennyliang (pennyliang) 的大作中提到: 】: 不混算法版很多年。。。: 这种问题主要是工程经验，算法版能给出的解答想都想的出来，就那么些。。。--※ 来源:·水木社区 newsmth.net·[FROM: 60.30.134.*] [本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部] 9 发信人: pennyliang (pennyliang), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Wed Dec  5 17:29:45 2007), 站内其实我发文的目的是勾引大牛入坑，答案对我来说不重要了，哈哈。。。【 在 godking (oh my godking) 的大作中提到: 】好吧，呵呵【 在 pennyliang (pennyliang) 的大作中提到: 】: 不混算法版很多年。。。: 这种问题主要是工程经验，算法版能给出的解答想都想的出来，就那么些。。。----※ 来源:·水木社区 newsmth.net·[FROM: 211.99.222.*] [本篇全文] [回复文章] [本篇作者：kabbesy] [回信给作者] [进入讨论区] [返回顶部] 10 发信人: kabbesy (Arthas), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Wed Dec  5 17:30:17 2007), 站内【 在 pennyliang (pennyliang) 的大作中提到: 】: 其实我发文的目的是勾引大牛入坑，答案对我来说不重要了，哈哈。。。...................: 好吧，呵呵--There can be miracles When you believe !※ 来源:·水木社区 newsmth.net·[FROM: 61.49.185.*] [本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部] 11 发信人: pennyliang (pennyliang), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Sun Dec  9 09:01:29 2007), 站内我来抛个方案，进行归并排序，大家拍首先，给出一个common sense的东西，便于下面讨论。如果两个有序段（L1，L2），其中L1的最小元素小于L2的最小元素（L1[0]<L2[0]）进行归并，则实际上需要的辅助空间大小不是Len（L1）+Len（L2），而是min(Len(L1),Len(L2)).归并的方法如下：这里假定Len(L1)=Len(L2)=k (1)申请一个段长为K的大小作为辅助数组为E。（2）E不空时，将L1，L2当前最大的数与E中的数swap（后面有例子说明）（3）最后的排序结果为L1,E例子L1:  1 3 5 8L2:  4 6 7 9E:   10 20 30 40(1)9>8,则有L1:  1 3 5 8L2:  4 6 7 40E:   10 20 30 9(2)8>7,则有L1:  1 3 5 30L2:  4 6 7 40E:   10 20 8 9(3)7>5,则有L1:  1 3 5 30L2:  4 6 20 40E:   10 7 8 9(3)6>5,则有L1:  1 3 5 30L2:  4 10 20 40E:   6 7 8 9(3)5>4,（此时E已经Full，交换5，30）L1:  1 3 30 5L2:  4 10 20 40E:   6 7 8 9(3)4>3,（交换4，30）L1:  1 3 30 5L2:  4 10 20 40E:   6 7 8 9(3)4>3,（交换4，30）L1:  1 3 4 5L2:  30 10 20 40E:   6 7 8 9此时 归并的结果为L1+E,为1,3,4,5,6,7,8,9 而原来有序的10,20,30,40这个段作为辅组数组，自身的顺序在排序后被破坏了（这个性质很重要）--※ 来源:·水木社区 http://newsmth.net·[FROM: 58.30.83.*] [本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部] 12 发信人: pennyliang (pennyliang), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Sun Dec  9 09:13:54 2007), 站内其次，多路合并众所周知，这种归并在搜索引擎中将多个临时到排文件归并成一个时大量应用，这里我们只是一般性的讨论。假定有16个归并段（这是有可能的），进行归并排序L1L2L3...L16(1)对L1,L2,L3,L4进行归并，假定段长均为K,则申请3K的辅助空间可以进行归并(2)归并后，L1,和这个3K的辅助空间构成了有序段，而L2,L3,L4,作为辅助空间为后来的归并充当辅助数组（这里解释一下用最小段，是为了节约最后的几次拷贝，从上面的例子可以看出，L1的最小几个元素是不需要move的）(3)L1,..L4归并为M1，L5,...,L8归并为M2,..这样归并变为对M1,M2,M3,M4进行归并。。。。(4)最后必须对两个有序段进行归并，这样辅助空间还是需要相当与问题规模的一半大小。当然也可以采用辅组空间为O(1)的归并方法，大家先拍，稍后再发出这种归并方法。。。【 在 pennyliang (pennyliang) 的大作中提到: 】: 我来抛个方案，进行归并排序，大家拍: 首先，给出一个common sense的东西，便于下面讨论。: 如果两个有序段（L1，L2），其中L1的最小元素小于L2的最小元素（L1[0]<L2[0]）进行归并，则实际上需要的辅助空间大小不是Len（L1）+Len（L2），而是min(Len(L1),Len(L2)).归并的方法如下：这里假定Len(L1)=Len(L2)=k: ...................--※ 来源:·水木社区 http://newsmth.net·[FROM: 58.30.83.*] [本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部] 13 发信人: pennyliang (pennyliang), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Sun Dec  9 09:21:17 2007), 站内参考此贴，获得空间复杂度O(1)的归并排序，我就不写了，呵呵。。。http://bbs.nju.edu.cn/vd89098/bbsanc?path=/groups/GROUP_3/Algorithm/D82FEB0BE/D89D07C10/M.1072426129.A【 在 pennyliang (pennyliang) 的大作中提到: 】: 其次，多路合并: 众所周知，这种归并在搜索引擎中将多个临时到排文件归并成一个时大量应用，这里我们只是一般性的讨论。: 假定有16个归并段（这是有可能的），进行归并排序: ...................--※ 来源:·水木社区 http://newsmth.net·[FROM: 58.30.83.*] [本篇全文] [回复文章] [本篇作者：godking] [回信给作者] [进入讨论区] [返回顶部] 14 发信人: godking (oh my godking), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Sun Dec  9 09:28:10 2007), 站内简单的说就是把l1和l2多路归并到E，然后把l2中剩下的插入到l1【 在 pennyliang (pennyliang) 的大作中提到: 】: 我来抛个方案，进行归并排序，大家拍: 首先，给出一个common sense的东西，便于下面讨论。: 如果两个有序段（L1，L2），其中L1的最小元素小于L2的最小元素（L1[0]<L2[0]）进行归并，则实际上需要的辅助空间大小不是Len（L1）+Len（L2），而是min(Len(L1),Len(L2)).归并的方法如下：这里假定Len(L1)=Len(L2)=k: ...................--※ 来源:·水木社区 newsmth.net·[FROM: 60.28.238.*] [本篇全文] [回复文章] [本篇作者：godking] [回信给作者] [进入讨论区] [返回顶部] 15 发信人: godking (oh my godking), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Sun Dec  9 09:30:19 2007), 站内搜原地归并有一些paper，有个基于块交换的原地归并算法还不错，呵呵【 在 pennyliang (pennyliang) 的大作中提到: 】: 参考此贴，获得空间复杂度O(1)的归并排序，我就不写了，呵呵。。。: http://bbs.nju.edu.cn/vd89098/bbsanc?path=/groups/GROUP_3/Algorithm/D82FEB0BE/D89D07C10/M.1072426129.A--※ 来源:·水木社区 newsmth.net·[FROM: 60.28.238.*] [本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部] 16 发信人: pennyliang (pennyliang), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Sun Dec  9 09:32:59 2007), 站内L2中的还需要和L1余部进行比较，确定那个插，那个不插在L1的尾部。比较形象的一个说法，可以参见Sara Basse的哪本算法书。。。【 在 godking (oh my godking) 的大作中提到: 】: 简单的说就是把l1和l2多路归并到E，然后把l2中剩下的插入到l1--※ 来源:·水木社区 http://newsmth.net·[FROM: 58.30.83.*] [本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部] 17 发信人: pennyliang (pennyliang), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Sun Dec  9 09:35:19 2007), 站内简单说来就是拿自己的一个最大块（或最小块）做辅助空间，最后再排序这个辅助空间剩下的块，按最小元素排序，然后顺序归并。细节就看这个链接：http://bbs.nju.edu.cn/vd89098/bbsanc?path=/groups/GROUP_3/Algorithm/D82FEB0BE/D89D07C10/M.1072426129.A。【 在 godking (oh my godking) 的大作中提到: 】: 搜原地归并有一些paper，有个基于块交换的原地归并算法还不错，呵呵--※ 修改:·pennyliang 于 Dec  9 09:35:54 修改本文·[FROM: 58.30.83.*]※ 来源:·水木社区 http://newsmth.net·[FROM: 58.30.83.*] [本篇全文] [回复文章] [本篇作者：pennyliang] [回信给作者] [进入讨论区] [返回顶部] 18 发信人: pennyliang (pennyliang), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Sun Dec  9 09:37:06 2007), 站内但不知道人家搜索引擎采用了什么special的排序方法，大牛给大家介绍介绍吧。最关键的是，搜索引擎doclist是压缩的，在这种压缩的情况下，如何进行归并，这个我始终没想明白，我猜测大概有这几种可能（1）例如n个临时到排文件，都有termx的doclist,且是压缩的，那么归并n个压缩的doclist,就必须使得压缩的doclist采用同步点，或者自同步编码的方式，可以便将长的doclist cut掉（2），每个临时到排文件对term的doclist的长度进行限制，当达到某个长度后，写在其他的临时到排文件中。【 在 godking (oh my godking) 的大作中提到: 】: 搜原地归并有一些paper，有个基于块交换的原地归并算法还不错，呵呵--※ 修改:·pennyliang 于 Dec  9 09:41:23 修改本文·[FROM: 58.30.83.*]※ 来源:·水木社区 http://newsmth.net·[FROM: 58.30.83.*] [本篇全文] [回复文章] [本篇作者：godking] [回信给作者] [进入讨论区] [返回顶部] 19 发信人: godking (oh my godking), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Sun Dec  9 09:39:14 2007), 站内可能说的不是一种,那种是l1和l2等大小的块交换的,能抓到耗子就行，呵呵，不说了【 在 pennyliang (pennyliang) 的大作中提到: 】: 简单说来就是拿自己的一个最大块（或最小块）做辅助空间，最后再排序这个辅助空间: 剩下的块，按最小元素排序，然后顺序归并。: 细节就看这个链接：http://bbs.nju.edu.cn/vd89098/bbsanc?path=/groups/GROUP_3/Algorithm/D82FEB0BE/D89D07C10/M.1072426129.A。: ...................--※ 来源:·水木社区 newsmth.net·[FROM: 60.28.238.*] [本篇全文] [回复文章] [本篇作者：godking] [回信给作者] [进入讨论区] [返回顶部] 20 发信人: godking (oh my godking), 信区: SearchEngineTech标  题: Re: 记得看百度某人博客，弱问一题发信站: 水木社区 (Sun Dec  9 09:40:33 2007), 站内大侠你把baidu贴出来，找xuchuan把google的贴出来，找glass把sogou的贴出来。。。【 在 pennyliang (pennyliang) 的大作中提到: 】: 但不知道人家搜索引擎采用了什么special的排序方法，大牛给大家介绍介绍吧。--※ 来源:·水木社区 newsmth.net·[FROM: 60.28.238.*]http://www.newsmth.net/bbstcon.php?board=SearchEngineTech&gid=3026


阅读全文(1266) | 回复(0) | 编辑 | 精华
 



发表评论：
昵称：
密码：
主页：
标题：
验证码：  (不区分大小写,请仔细填写,输错需重写评论内容！)



站点首页 | 联系我们 | 博客注册 | 博客登陆

Sponsored By W3CHINA
W3CHINA Blog 0.8 Processed in 0.377 second(s), page refreshed 144811155 times.
《全国人大常委会关于维护互联网安全的决定》  《计算机信息网络国际联网安全保护管理办法》
苏ICP备05006046号