|
锁定老帖子 主题：迅雷的一个面试题
精华帖 (8) :: 良好帖 (3) :: 新手帖 (0) :: 隐藏帖 (1)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2012-03-01
yinjh 写道 在具体的应用中，每个用户的分数是不是在随时变化着呢？比如游戏得分。
其实准确的名次没什么意义，可以利用概率啊。 随机取万分之一的数据排序 得到的名次乘以2万 就可以了。 这种方案也不错，只要保证最前面的排名实时即可（有些系统会列出top100的排名）。 其他人老想着实时，精确，老想着数据是有序的，难道这些真的有用？？？ 积分排名，又不是金额，干嘛那么精确？ 考虑具体需求的实用性吧 |
| 返回顶楼 | |
|
发表时间：2012-03-01
3005218046 写道 hardPass 写道 tsxm 写道 hardPass 写道 就一定要用数据表来完成么？
CPU，内存，外存 同学们啊！ 桶排序呗， 直接在程序中搞个数组，数组的下标就是分数，元素是每个分数对应的人数。 具体的，如果不需要精确计算，为了减少同步及遍历计算的性能损失，可以为每个数组元素设定一个预留值。 都说内存不够了，用外存估计速度太慢 1G内存还不够？如果现在排名第一的是1亿分，也就是一个长度为1亿的数组而已 300MB左右就够了，剩下的内存还可以再维护个计数缓存的数组(每个元素是上面数组希格玛，0到i)，数组长度是上面数组一样 你只允许255个人得同样的分数啊... 数组的下标就是分数，元素是每个分数对应的人数。 你没看清楚吧？？？？ |
| 返回顶楼 | |
|
发表时间：2012-03-01
一道简单的题目，考察了一个完整的数据库存储原理，2亿条记录，也算海量数据了，
基本处理思想是： 0、如果数据量真的非常大的很多，要考虑数据库分布式处理，数据库也可以负载均衡处理，但2亿条应该可以不用考虑这个。 1、一个统一的数据库内，切分成几个DBF文件，一个文件的最大存储量不要上G，一般来说500M-800M差不多了，保证数据库缓存加载搜索目标文件比较快速； 2、文件内进行分区处理，分区策略采用RANGE的吧，分数肯定都是根据范围切割的； 3、建立分区索引字典，分区内位记录建立关键字索引，比如ID建立索引； 4、查询的时候记录要根据ROWID或ROWNUM进行数据库存储区内分页查询，不要采用上面说的内存内去二分查找，一个内存中的数据不可能一下在全部加载完的，一次性5000条，单点服务器应该就有卡机和延迟现象了，所以要数据库存储区内分页查询搜索。 ================================================================ 给出一个分的话，就可以很轻松的定位到当前分数位于第几个分区了，这个分区的总的记录数，以及RANGE的范围是知道的，所以，计算一下分区的偏移量，计算一下分区内记录的偏移量，然后根据RANGE的范围就可以计算出排名了 |
| 返回顶楼 | |
|
发表时间：2012-03-01
每天排一次，以uid -> rank的对应存起来，呵呵，别的没想到办法
|
| 返回顶楼 | |
|
发表时间：2012-03-01
CshBBrain 写道 kidding87 写道 终于有人说了我说的东西。。。
你们难道就没发现别人说的是数据源，不是数据库 那么多数据select * from table where id=？没有索引这个的效率都低死，数据库还不是一个个找 的确，题目强调了是【数据源】，并且是有序的数据源，没有说具体的存储形式，用数据库，用文件系统，还是用缓存服务器集群......；其实大多数人一看到2亿条数据都想到自己采用怎样形式去存这个数据了，而忽略题目的本意是怎样快速有效的找出用户的排名；依我个人的愚见，用户登录系统时找到用户的分数排名，要到数据库去找，或是到文件系统去找花费不菲而且效率也不见得好，一般会放到缓存服务器集群中。当然其实数据源的存储形式我们不用去操心。用户登录肯定已经获取到id和自己的分数，我们就假设已经知道用户id和用户分数（这是比较合理的假设）。 数据源既然【有序】那么我们肯定就有办法（是什么办法根据数据源具体的存储形式可以写个方法<当然有可能数据源本身可以提供>）取到指定位置的元素。 1.获取数据源的最后一个元素和数据源的第一个元素的 score, 将这2个score 相减 得到的 最大分数与最小分数的差值 S1。 2.用得到的分数差值 除以 数据源的元素数量 得到 平均每个用户之间的 分数差 V1； 3.将用户的分数US 减去 数据源中最小分数 得到用户与最小 分数之间的差值 S2， 4.W = S2 / V1 ,W 为我们估算的用户在所有用户中的排名数量 5.取出W处的元素的score WS 6.如果 用户的分数US 小于 WS，则从 W处开始向前查找用户的排名，如果US大于 WS 则从W处开始向后查找用户的排名，用户的排名就在附近，不用加载太多数据。如果US的只等于WS,那么恭喜你了。 7.这个算法没有考虑分数相同并列排名的处理，我想迅雷也许也没有处理并列排名的情况，只是获取数据源中的具体位置。 8.如果分数分布特别不均匀的话，可以递归使用上面的方法多算几次，直到US 和 WS 相差非常小（小到一个阀值）再从W处开始向前或向后查找定位。 你好牛啊，就算面试官觉得你说的跟迅雷的做法不符，你分析了那么有条理，肯定对你有兴趣。 |
| 返回顶楼 | |
|
发表时间：2012-03-01
id--4Bytes(假如迅雷野心不是那么大的话，2^32≈40多亿用户够用了^_^)
score--4Bytes 2亿数据≈2*10^8*8≈2^31Bytes=2GB。 1.直接二分查找log2^31=31(I/O) 2.若不考虑建立索引的时间，则把分数全部加在到内存中(2GB/2=1GB)，二分查找即可，不需要I/O时间。 3.若考虑建立索引的时间，索引次数应当<31次才能更快,不过这个需要实验加载多大MB外存到内存时间后才能测量。 |
| 返回顶楼 | |
|
发表时间：2012-03-01
freish 写道 select count(1) from tableName where scores>(select scores from tableName where id=MyID)
这方法我看行 |
| 返回顶楼 | |
|
发表时间：2012-03-01
哪有这么多二分查找啊??
如果是按分数排序.. 只给出了用户ID。不给用户的分数 怎么二分查？（先找到用户ID,再二分找分数？那为什么不找到用户ID的同时获取他的排名？） 如果给出了用户ID 又出了分数.. 那用户ID有什么用？？？ 直接根据分数找出排名就行了.. 个人感觉.他应该是在考多线程处理能力访问的 迅雷是下载软件啊 |
| 返回顶楼 | |
|
发表时间：2012-03-01
数据库按名次和分数分区建一个表
客户端缓存用户上次登录时查到的积分，在下次登陆时根据本地缓存的分数在分区表中查询名次区间，然后在分数表中从rownum=名次区间较小值开始查询id=用户id的记录，获取到用户新的rownum和积分。rownum就是排名，积分缓存至客户端用以下次登录访问。 如果客户端没有缓存积分，只能从计分表中直接查询id=用户id记录的rowNum |
| 返回顶楼 | |
|
发表时间：2012-03-01
panshunchang 写道 freish 写道 select count(1) from tableName where scores>(select scores from tableName where id=MyID)
这方法我看行 非常慢，你也可试试 |
| 返回顶楼 | |
