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

zszyj

原帖由 wwwsq 于 2008-6-27 12:44 发表



首先，这个概率非常低。低到你可能一辈子都遇不到。

第二，谁告诉你用户需要重新输入？注册的时候发现用户名重复，就让客户改下用户名就是了。

第三，注册检查通不过有很多可能的原因，用户名重复只 ...

低不低, 看网站的规模了, 小网站上注册,可能一辈子都遇不到.但全球性的大网站呢? 概率多少, 恐怕谁都不好说.至于你说的0.00001%，更是没有理论是实践的根据了．
是否只改名? 相信大家都遇到过好多这种经验, 除了大部分不用重输, 还是有不少要重输的, 用户名,密码(两次), 如果内容多了,要分几页, 恐怕整个过程都得重来一次.
至于1w vs 100w，这个更不靠谱．即使google真象你们以为的好样，将这种技术也应用到ＩＤ重复检查去了，但其成本可能是1w吗？　直接数据库查找就100w？先不说用户信息最后都是保存在库里的，　这个成本没有差异．　即使只算数据库成本，难道mysql要收钱吗？　即便是oracle,　在普通ＰＣ服务器上，能卖这么贵吗？
最后, 讨论到了这个地步, 已经不是技术问题, 而已经是客户对应用系统的"系统观"问题了. 取决于客户对系统的看法和要求, 我相信, 不管是哪个行业, 高要求的客户仍然是主流的, 不仅是银行或者电信行业.
对于技术问题, 我也不想再讨论下去了, 细节都已经很清楚，剩下只是自已选择的问题. 只等着真有人拿出堪称＂高手级＂的代码，让我开开眼界吧．

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

zszyj

原帖由 wwwsq 于 2008-6-27 12:58 发表



你恰恰说反了。小网站是不在乎这点性能和成本的，直接去查数据库就好了，反正用户少请求少，机器空着也是空着，查查数据库也无所谓。

布隆过滤器过滤几百亿的垃圾邮件地址都没问题，何况过滤区区几亿的 ...

你又在逃避一个问题了．布隆过滤器 的概率，指的是已经进过滤器的ＩＤ，只是错判的概率．　并不包含你前面说的几天内的新增用户，对于大型网站，如果每天新增几万，漏判的概率会低吗？
布隆过滤器过滤几百亿的垃圾邮件？　消耗几十Ｇ的内存做这个小事情？　服务器的内存几十Ｇ，会比数据库硬盘的成本低？而且这么强大的服务器，成本是多少？一个服务器光做这个事情，　其它都不做了？　如果还做其它事，这台服务器又是什么规模，价格多高？
准确率，成本，效益．希望会有人选择你的方案吧．

zszyj

我看某些人啊，　当＂打手＂合适，＂高手＂是没份了，骂不倒别人，总能动手打倒吧？
进程也好，线程也好，自已做出来瞧瞧吧．
apache５０００并发？　那得看什么机器上了.普通服务器，几百就不错了．
apache的并发接受请求, 与你说的并发访问同一块内存的加锁控制问题, 是一码事吗?
就算apache做到了，又与你何干，它是个简单算法吗？　是你做出来的吗？　扯这么远，还是没拿得出手的，哪怕一行代码，可笑哪！　丢人哪！

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

zszyj

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



一个小时更新一次可不可以？一分钟更新一次可不可以？

真是无语言。

另外，谁告诉你要几十G内存？去看下Bloom filter的原理再来。你连什么叫bloom filter都还没搞清楚，讨论怎么继续下去？

"假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, ...,F8） 产生八个信息指纹（f1, f2, ..., f8）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。"
这是引用原文的话，　１亿个邮件地址，需要两亿字节=200MB, 你说的几百亿邮件地址，　不是几十Ｇ的内存是什么？　你很懂啊，给我说说看？

另外，不反对你们实时刷新，　就是拿点实时刷新的代码来看看吧．

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 编辑 ]

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多层架构,实时数据刷新和同步的系统工程问题了, 这个过程你们 ...

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

zszyj

原帖由 wwwsq 于 2008-6-27 14:38 发表



谁告诉你一个ID要一位？

麻烦你认真看下文档。

A Bloom filter with 1% error and an optimal value of k, on the other hand, requires only about 9.6 bits per element — regardless of the size of the elements.
google说是两上字节, 这里说的是每个元素1.2个字节,所以我说1亿还是要125M,没错吧?几百亿地址需要几十G内存, 难道不对吗?

zszyj

原帖由 bbpet 于 2008-6-27 22:48 发表


这个ia64是个很普通的hp服务器，跟我上次测db2得出主索引0.1ms时的z990不可同日而语
连z990的零头的零头的零头的 …… 都不到~
毕竟国内能买得起（或者会买来用）z990的企业用手指头就能数出来了~
恩，快 ...

不知道你的Z990配了多少C, tpmC有多大. 你的ia64 4c/8g, 也不弱了. 不过, 对于单个DB查询或者bloom filter, 都只用到单个CPU的1/4以下资源.因此真正决定其速度的是单个CPU的频率. 不信的话,你可以只有HP上测试一下DB的性能. 我在自已笔记本上的装了个LINUX虚拟机,上面装了个ORACLE,查询一次也是<1ms, 当然, 我没法装入大量数据.
cpu的增加, 只提升了其并发处理的能力.
另外,碰撞的程度,与KEY值的离散程度有关, 越相似,碰撞的可能性就越大. google要8组,还是有其道理的.
补充一些测试数据.
我发现原来生成的名字, 过于离散, 而且名字前几个字符都不同.我想这就是碰撞不大的原因, 我觉得, 用户ID一般前面字符重复的多,因为前面几个字符通常是姓名的拼音或者英文名,而且以3-8个字符的为多,超过8个的少. 因此我修改了一下生成名字的程序, 生成的名字将如下:
aaaaaaaa;
aaaaaaab;
......
Z9999999;
......
Z________;

并增加碰撞结果的统计,程序如下:

static int
fillname()
{
  inti;
  intj;
  intbit;
  unsigned int    code;
  charusername[10];
  intbits[10];
  intres;
  intcollision;

     for (i=0; i<10; i++)
       bits [ i ] =0;

    memset(username, 0, 10);

    collision=0;
    for (i = STARTPOS; i < NAMESIZE; i++) {
        for (j=0; j<8; j++)
            username[j] = nametab[bits[j]];

        bits[7] += 1;
        for (j=7; j>=0; j--)
        {
            if (bits[j]==37)
            {
                bits[j]=0;
                bits[j-1] += 1;
            }
        }

        code = hash_larbin(username);
        res = 0;
        res=testSet1(code);
        code = hash_php(username);
        res += testSet2(code);
        if (res==2)
            collision++;
    }
    printf("%d names, %d collision\n", i, collision);
}

测试结果:
/home/house/tmp>./tt
126934395 names, 3293092 collision // 冲突
1214187341
2 ignore!
to ignore!
nice ignore!
great ignore!
aaaaaa ignore!
aaaaab ignore!
aaaaac ignore!
aaaaad ignore!
baaaaa ignore!
caaaaa ignore!
daaaaa ignore!
aaaaca ignore!
bbbbba ignore!
bbbbbb ignore!
bbbbbc ignore!
bbbbbd ignore!
abbbbb ignore!
bbbbbb known!  // 误判
cbbbbb ignore!
dbbbbb ignore!
fi3a87 ignore!
fi3a8asfasvaf7 ignore!
1214187341

也就是说, 1.2亿个名字中,有3百多万是冲突的.
而且20多个检查中,就已经有一个误判.
说明了一点, 好的hash函数,很重要, 而且, 只靠2个,恐怕是不够的.
这里还是要感谢bbpet的热心,希望能找出更多更好的hash函数.

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