迅雷的一个面试题

我看到的是已经排序好了，为什么不直接查找这个用户的信息看看他排序标识是多少呢？

的确，题目强调了是【数据源】，并且是有序的数据源，没有说具体的存储形式，用数据库，用文件系统，还是用缓存服务器集群......；其实大多数人一看到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处开始向前或向后查找定位。

二楼的方法很好啊，这玩艺用不到数据库吧

人家已经说的很清楚了，真不明白还要说的多具体。

我觉得这个问题完全可以这样解决，前提是oracle数据库：
select scores,rownum from table where id=xx
都说了已经排好序了，rownum完全就是当前用户的排名。
再补充一下，用户登录就有自己的分数，这说明了什么，说明他是要从这个表中查分数的，那么完全可以顺便查rownum。而count(1)这种形式，一旦数据量大，非常消耗时间，有人说select * from table_name在数据量大的时候就不消耗时间吗？没错，数据量大的确比小要多消耗一点，但是根据我个人经验，一旦做了索引，那么select * from table_name where id=xx这样的语句在2条和2百万条时，响应时间几乎没有差别。

我写了一篇文章来解答《海量用户积分排名算法探讨》
http://www.cnblogs.com/weidagang2046/archive/2012/03/01/massive-user-ranking.html

这个肯定是二分查找，但是数据那麽大，没法一下子拉到内存，所以是存文件，存文件的化采用跳表得方式，进行二分查找。

create table rank(id bigint not null primary key, rank bigint not null);

在具体的应用中，每个用户的分数是不是在随时变化着呢？比如游戏得分。
其实准确的名次没什么意义，可以利用概率啊。
随机取万分之一的数据排序
得到的名次乘以2万
就可以了。

你只允许255个人得同样的分数啊...