在网上看到的: 1分钟内用户上线的数目是60万,如果用户在5分钟内重复上线,就给他发警告,问如何设计? 嗯,让我这个自以为是的不知天高地厚的家伙来看看该怎么设计。 嗯,首先确认的是,出题者应该是想考实际算法的,和应试者解决难题的方法,全方位思考问题的意识。所以”花600百万美刀花一套oracle的顶级牛B数据库然后把五分钟内的用户记录入库,连数据库查询“这样回答可能确实解决问题 不过不是出题想要的。 好吧,哪,准确地说,啥数据结构,啥算法? 让我们先想象数据容量和运算量。嗯,五分钟内可能有300万用户名要存储。这个嘛,不大,完全在单机范围之内,内存稍大的机呖器,就能全装下这个量级的用户名或id数据。再看时间要求:一分钟内要上线60万用户,每个用户上线时都要查询是否重复了,呀,这是一秒钟1万次查询。如果说是网络服务器的话,比如web这种效率低一点的服务,一万次每秒还是相当复杂的。不过如果是机器内运算1万次,嗯,还是可行的。 接下来,咱们要看是最麻烦的部分,也是要点一:如何应对一秒内完成一万次对该用户是否在五分钟后上线过的查询。这实际是一个要查询一个数据是否在一个列表中存在的问题。嗯,当然我们可以挨个去比对,这个列表比对完了我们就知道这个数据是不是存在了。不过,做为搞软件开发的,大家都知道,如果这个列表能够事先排好序,那是最好不过了。好吧,让我们确定一点:我们最好应该将某一时间的用户名排个序。 接下来我们假定我们把每秒钟内上线的1万个用户放在一个桶里,然后对该秒中的所有用户按名字排序,从小到大或都是从大到小,都行。现在我们时间每推进一秒,我们就噌地新建建一桶,这一秒时间内的新增的一万用户呀,就存这个桶里了。嗯,做为开发者,实际情况是,我们一始就建了300秒这么多桶,申请了大小为300的内存块。然后每块内存里要能有足够容纳一万个用户的内存大小。 嗯,每当时间的车轮进入新的一秒,我们就去这300个中间去找到已经过期的那一“秒“,给它打上当前时间标记,嗯,把它个1万个用户数据清空。每进来一个用户,我们就丢进去,让它们按用户名大小排队。 每一个新用户上线时,我们都需要向这个300个桶发出查询请求。嗯,学过二分法的话,就应该知道,一万个排好序的数据,要查询是否包含某一数据只需要log10000就行了,啊,大概是14次查找。嗯,比你一万个挨个查好了吧,那可是1万次查找啊。 再接下来,我们再思考一下,检查一下:如果是实际场景的话,我们用户们可能不那么听话,每分钟内的60万用户未必刚好平均分配到一秒一万。嗯,而且就跟电灯炮一般能承受的电压都不是220v,而会高出不少,比如250v也能工作,180v也能点亮。比如,明天突然出了个重大新闻,一秒钟内涌进了13000名用户,那我们这么桶的大小就不能承受了。这个,我们做一点点改进,因为二分法最多反正也得比较14次,我们就以2的14次方做为桶大小。如果再还不能承受,那就在用户超出时2的14次方时单独再申请内存。 嗯,这样看上去好多了,不过,排序也是一个比较繁琐的过程,嗯。假设这样一个场景….算了,直接说吧。对于这种从一堆数据中查询是否存在某一个数据的做法,有一个算法叫布隆算法,可以google 一下bloom algorithm或是bloom filter,就专门干这些事。布隆算法做这个查询会有误差,比如,有的用户明明是没有登陆,可是却被提示重复登陆了。这个误差机率我们是可以计算的。 接下来我们可以试际测试一下,看看单机测试的结果。如果实在还不行,那就需要把这300个秒上的数据分布到几台机器上去计算。比如每分钟内的时间分在一台机器上… 有的哥们是这样考虑的: 做一个长度为300的循环链表,每个链接项的数据是一个hashtable,这样来判断。也是删掉过期数据。我觉得这样难度挺大的,因为这样每秒种进1万个用户,对300个链表项中每一个项的1万个数据都要做比较,大致相当于一秒内做了10k*300*10k次比较。我的印象中,就是一亿次for循环,每个循环基本上啥也不干,这个时间,也应该在一秒左右。我偷了下懒, 用c写了个简单的测试: #include “stdlib.h” #include “stdio.h” int main(int argc,void ** argv){ int i=0; int j=10000*10000*3; for(;i 如果再100倍,时间就远超出1秒了。还没有做其他事情呢。我用的是10000*10000*3是因为,如果是10000*10000*300,就溢出了。 不过至于究竟分桶排序后效率如何,也还不好说。没有实战。只是我凭经验觉得一秒钟几百亿次比较是不靠谱的。嗯,不知道有没有时间写个程序验证一下。