迅雷的一个面试题

平僧不才 2亿减去select count(id) from table where score>用户分数

这....
题目说这个数据源有俩字段，你们真以为就两字段？真以为2亿数据都放在一个表里？

居然还用sql来解决......

2亿用户，那么在线用户得多少？用数据库不爆才怪

为什么不能用数据库解决呢？
又不是说只有一个数据库。

这问题用数据库来解决，DBA就跟着哭了。

1：数据库那么昂贵的资源用来干这活...

适合数据库干的就是 需要非常精确的数据、事务非常严谨的数据，比如订单、交易数据。

其他的能不用数据库就不用。

2：数据库操作是很慢的，你用count，即使你分库怎么着也得1s，数据量摆在那里。大数据量高并发访问，一次请求1s，想想吧

3：积分排名本身又不是特别重要的功能，又不需要实时，准实时即可（保证前面的名次实时即可，比如前100名）。因此用缓存数据即可，当然能实时更新缓存数据更好。

4：无论有多少用户，分数一般都有个顶值吧（理论上没有，实际上是有的），比如说1w，100w。如果无限上升，那应该是产品需求有问题

综上：hardPass提出的方案就非常不错：

直接在程序中搞个数组，数组的下标就是分数，元素是每个分数对应的人数。
具体的，如果不需要精确计算，为了减少同步及遍历计算的性能损失，可以为每个数组元素设定一个预留值。

数据库能比内存快吗

数据源不等于数据库吧?

终于有人说了我说的东西。。。
你们难道就没发现别人说的是数据源，不是数据库
那么多数据select * from table where id=？没有索引这个的效率都低死，数据库还不是一个个找

1. 问题转化为查找用户id那条记录

2. 如果问题中不知道登录用户的分数，那么问题很难优化；老老实实的线性查找、计数，平均复杂度为O(n)

3. 如果问题中知道登录用户的分数，问题可以进行优化；
a. 读取n条记录，如果第n条记录的分数大于登录用户分数，则在n条记录中用折半查找进行检索
b. 第n条记录的分数小于登录用户分数，则读取从n到2n之间的数据，如此反复直到读取完
简单的说就是折半查找，但是这里并不一定真的是“一半”而是尽可能的“靠近”一半（由于内存有限）。所以总体复杂度应该是稍微高于O(log)，纯粹理论分析的话就是O(log)

LZ的思维。。。又是分区，又是分表，又是lucene。。感觉像是找不到办法“胡乱拼凑”。

分数是排了序的.
那这个时候.一般会有个总人数...假设有N个人.. N=2亿.

根据这个分数进行分段查找.
比如10个线程.（线程数可控）从不同的段找.ID相等的.
比如.这样就是
每个线程负责 2000W 进行查找 ,找到ID相同的就退出,打印
伪代码

线程2(线程1的查找范围是0-2000W)
int index = 2000W + 1;

for (int i = index; i < index + 2000W;i++){
//不管什么方式,反正是排序了的.肯定是可以直接获取第N个人的分数的
//比如获取 第一名多少分,第10名多少分.
    if (当事人ID == 数据源[i] ){
        通知其他线程停止查找;
        print(当时人排名=   [2(第二段) - 1] * 2000W + count)
        break;
    }else{
      count++;
   }
}

根据这种方式.也可以将其在分配到其他机器上去查找.
如.PC1 找到 0-1亿,  PC2  查找 1亿-2亿
这样时间只花费在数据源获取的时间..

如果需要减少从数据源获取数据的时间..
可以每次获取..500个.用完了在去拿一次...

不会用太多内存,一般说内存只有多少,不能超过多少.都是吓人的...

如果需要考虑分数相同的情况.可以添加一个记录值如. .
int equals = 0
  if (如果与上次分数相同){ equals++;}
  else {
    equals = 0;
  }
如果当前找到的人ID,分数与上次相同.就继续往下找..并且 equals++ 至于与当前找到的人数不相同为止.

最后.按 找到的人数.减去 equals 就等于他的倒数并列名次
如果要正数并列名次的..就从高分往下找..