对Google算法优越性的一点小体会

wwwsq

原帖由 zszyj 于 2008-6-27 13:24 发表

"假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, ...,F8） ...

google那个黑板报是科普性质的东西。

wiki上的说明稍微详细一些：
http://en.wikipedia.org/wiki/Bloom_filter

zszyj

原帖由 wwwsq 于 2008-6-27 13:29 发表



google那个黑板报是科普性质的东西。

wiki上的说明稍微详细一些：
http://en.wikipedia.org/wiki/Bloom_filter

你找哪个材料, 都是一个说明, 即使一个ID一位, 无论如何1亿用户就要大于125M, 几百亿仍然是几十G.可能大家都看不懂高深的中文也看不懂英文,你是很懂的, 说说看怎么几百亿邮件地址就不需要几十G内存了?

[ 本帖最后由 zszyj 于 2008-6-27 13:44 编辑 ]

shan_ghost

原帖由 wwwsq 于 2008-6-27 13:29 发表



google那个黑板报是科普性质的东西。

wiki上的说明稍微详细一些：
http://en.wikipedia.org/wiki/Bloom_filter

说的对。

其实，google黑板报那个，真做过东西看了就明白了。

我在第5页也说过，那是一个8 hash出来的东西——脑子不死的，自然能想到单hash出来也是bloom filter。
google是为了避免冲突，因而搞了个8倍精确的玩意儿，但也占用了8倍的空间。

总之，为了提升精确度，加大hash数，加大空间即可；反之，为节约空间，就搞成单hash。

甚至于，搞8台100MHZ 200M内存的百元机，每台上面都搞一个单hash的bloom filter，就可以轻松支持8亿数据。

如果用户数再多，根据首字符一分，千亿也能支持。

所以说，这个算法是一种特别适合并行的东东。



另，王小波讲过一个故事：
    传说某乡下人进城，见城里人用灯泡，就也买了一个。
    回到家，他拿根皮绳把灯泡一拴，梁上一挂，指着灯泡骂开了：“你TM怎么不亮！”

    这个故事告诉我们： 城里人点灯，别让乡下人看到。



俺就是乡下人。所以说这个绝没有歧视乡下人的意思。
俺的意思是： 夏虫不可语冰。一个从未接触过并发访问，以为多少个用户就必须搞多少个线程的家伙，你一下子和他说bloom filter这么“高”端的东西……他牙齿都还没刷呢～～


      ——“牙齿没刷”引自 周星驰《大话西游》，不是骂人话。

zszyj

原帖由 shan_ghost 于 2008-6-27 13:45 发表



说的对。

其实，google黑板报那个，真做过东西看了就明白了。

我在第5页也说过，那是一个8 hash出来的东西——脑子不死的，自然能想到单hash出来也是bloom filter。
google是为了避免冲突，因而搞 ...

省省吧, 你这半桶水,再拼命跳再拼命抖也抖不出两滴. 从你开始发言开始, 本来你们自已号称随便找个大学生两天即可简单实现的算法问题,已经上升到C/S多层架构,实时数据刷新和同步的系统工程问题了, 这个过程你们自已不断改变方案, 终于也没一个拿得出手的所谓"简单低成本"的设计方案出来, 说得自已象"天下第一", 用屁股代替脑袋说话,对别人恶意喷粪,可显示出你的高级了?
拿点事实来说话, 让我们看看什么是你的"简单实现".
说句实话, 我还是挺爱看你这副狗急跳墙的样子. 为什么这样说, 呵呵, 叫得大声却不会说人话的是什么动物啊?
继续你的表演吧, 期待你的精彩演出.

[ 本帖最后由 zszyj 于 2008-6-27 14:00 编辑 ]

zszyj

原帖由 zszyj 于 2008-6-27 13:55 发表

省省吧, 你这半桶水,再拼命跳再拼命抖也抖不出两滴. 从你开始发言开始, 本来你们自已号称随便找个大学生两天即可简单实现的算法问题,已经上升到C/S多层架构,实时数据刷新和同步的系统工程问题了, 这个过程你们 ...

我看版主该因为我引导的这个贴子,颁个特殊贡献奖了.

shan_ghost

楼上的，保护牙齿要紧

CUDev

要是字符串比较，黄花菜都凉了

shan_ghost

我们现在已经完成了从一亿用户的普通GMail向几百亿用户的超级系统的迁移，只需要把类似分布式事务代码那样的东西修改一点点即可

如果是google，在他们强大完善的底层库支持下，想必工作会更为简单

旺财？这个基础太差的小可怜……跟在后面赶得这么辛苦，累得只会吐脏东西了吧？

feijin

原帖由 shan_ghost 于 2008-6-27 14:08 发表
我们现在已经完成了从一亿用户的普通GMail向几百亿用户的超级系统的迁移，只需要把类似分布式事务代码那样的东西修改一点点即可

如果是google，在他们强大完善的底层库支持下，想必工作会更 ...

天啊，太厉害了
能否通俗的说一下该怎么改呢？那些方面
谢谢

真羡慕你们

wwwsq

原帖由 zszyj 于 2008-6-27 13:41 发表

你找哪个材料, 都是一个说明, 即使一个ID一位, 无论如何1亿用户就要大于125M, 几百亿仍然是几十G.可能大家都看不懂高深的中文也看不懂英文,你是很懂的, 说说看怎么几百亿邮件地址就不需要几十G内存了?

谁告诉你一个ID要一位？

麻烦你认真看下文档。