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

zszyj

原帖由 benjiam 于 2008-6-25 23:42 发表

7 你10年前过高程系分， 就你的水平 可能吗？ 连个cgi 都搞不清楚。

不爽， 你20分钟内贴你 高程、系分的证书

我马上就不回此帖。

幼稚．

tyc611

这贴挺热闹，费了好半天的劲才看完

philos

真的好精彩，好文啊！

dangk

假如每个用户名有128个字节，那么4k字节可以存储32个用户名＝2^5，假设2^30个用户名，那么共需要2^25个block,由于完全是比较操作没有范围操作，用extendible hash index，那么就需要25bits作为hash值，64bits作为硬盘地址（假设他们使用64为系统）， 也就是89bits一个block,多加一些其他信息例如分隔符，假设128bits一个block，也就是16byte，那么16＊2^25byte需要1GB,这个大小完全可以全部放进内存。也就是说整个查询需要一次内存查询外加一次硬盘操作。硬盘操作都是毫秒级的，因此单纯从数据库角度来看，没有什么太大的难度，而且存储的空间也不大。
而真正困难的地方在于，如果更新这样一张只有用户名的表，保证和其他部分的完整性。
而且一个通用性的数据库一般很少用Hash table,因为对范围搜索完全没有支持

[ 本帖最后由 dangk 于 2008-6-26 07:15 编辑 ]

spender

花了半个小时，大致浏览了一下大家的发言：

我发表两个看法：

一、不能因为服务器足够强劲儿忽略算法问题
　　现在很多程序员认为服务器太强大了，我单位就有配置４８颗ＣＰＵ的小型机，应用还是慢，确实有ｓｅｌｅｃｔ　＊　ｆｒｏｍ　ｔａｂｌｅ　ｗｈｅｒｅ　ｎａｍｅ　ｍａｔｃｈ　＂＊ａｂｃｄｅｆ＊＂的ｓｑｌ，　归根到底，跟这个帖子技术一致，恰恰需要好的算法来处理。这个表大概几千万条记录，还没有达到亿行记录。　头痛的是：客户名称没有索引，有重复。正在研究更好的算法。
　　于是我想到了ＭＤ５把一些可以让操作员提供的信息（客户名、其它可以提供的在本表中存在的字段）组成一个长的串，然后ＭＤ５（＊ＳＴＲ）计算成一个尽可能不重复的数字，并添加到表中，然后建立该字段的索引（当然也不唯一，但重复键非常少），再去测试，看看效果怎么样。

二、不能因为存储足够大，就不考虑对存储空间的消耗
　　存储空间的消耗，最终在处理时都是对内存的消耗，都是对ＣＰＵ计算资源的消耗。希望各位在写程序的时候多看看别人的处理方法，最好使用１个字节（ｂｙｔｅ）的不同位，来表示不同的标志。一个自己长１６位，可以表示１６个状态。

ｇｏｏｇｌｅ我相信也面临跟我们一样的困扰。当然它还要好些，因为它没有重复记录。

不管ｈａｓｈ，或者以来数据库的ｂｔｒｅｅ（索引）都是我认为比较好的处理算法。

[ 本帖最后由 spender 于 2008-6-26 08:03 编辑 ]

pythonor

mark

zszyj

原帖由 spender 于 2008-6-26 07:48 发表
花了半个小时，大致浏览了一下大家的发言：

我发表两个看法：

一、不能因为服务器足够强劲儿忽略算法问题
　　现在很多程序员认为服务器太强大了，我单位就有配置４８颗ＣＰＵ的小型机，应用还是慢，确实 ...

对于看法一提出的问题, 我认为与查找用户名是否重复不是一回事.  google问题其实是按索引查找,即已经明确知道ID号,从已对该字段作索引的表中查找记录, 即"ID='abcdef'"; 而你说的是模糊查询, 即不知道名字的全称,只知道部分字符要找出表中所有名字字段匹配这些字符的的所有记录, 其实是全表扫描,这是两码事,不可比.一般来讲, 在大表中执行like, match之类的操作,即使数据库再强大,也是要避免的.

对于看法二, hash表的搜索方式,只适合小规模的内存数据, 不适合大规模数据量基础上的查找; 只适合静态数据, 不适合象用户信息这类不断增删改查的数据.此外, 我坚持一个观点, 就是大规模数据量上的按索引查找这种简单高效的工作, 数据库的性能足以胜任, 用不着48C, 一颗CPU就可达到惊人的效果,犯不着动则什么高深算法. 算法, 不是用来解决那种1+1=2之类的简单问题的. 而且, 象前面提到的所谓HASH算法, 还要考虑碰撞问题,用户ID是否重复,不是检测正确率达到99%就可以了, 是必须达到100%的.另外还要考虑并发访问,数据持久性的保证等问题,并不是想的那么简单. 因此, 对于这类问题, 数据库是最合适的方案, 即使将全地球人的用户ID都放到一个数据库里, 也不见得是大问题,况且根本不可能出现这种情况.

loser123

原帖由 cugb_cat 于 2008-6-22 11:54 发表
如果做了索引，这个数据量放在数据库中去查也很快的。

这个好像不行,,

单点的数据库肯定不行...

必然有其他的处理,

google怎么作的,不知道啊,,

haiyan_qi

不知道zszyj到底是在阐述一个什么观点，算法无用论吗？

lose

原帖由 haiyan_qi 于 2008-6-26 10:41 发表
不知道zszyj到底是在阐述一个什么观点，算法无用论吗？

不是算法无用论，恰恰是在讨论算法，还有实际的实现。
他提议用数据库，10亿条做查询也就是0.1ms, 感觉上是应该够用了。如果有1000个人在同一时刻，那么也就是0.1S，加上网络时间，对于人来说是感觉不到的。