|
锁定老帖子 主题：迅雷的一个面试题
精华帖 (8) :: 良好帖 (3) :: 新手帖 (0) :: 隐藏帖 (1)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2012-02-29
wangqj 写道 分区思路肯定没错
比较奇怪的是，实际情况中，他表中的数据怎么可能是排好序的？ 一直在维护索引？ |
| 返回顶楼 | |
|
发表时间：2012-02-29
shoushou2001 写道 假设：
分区：1 2 3 4 5。。。 分数：[0, 1000),[1000, 2000),[2000, 3000),[3000, 4000),[)。。。 分别给id、score加索引，用户一登录，就知道id,通过id查找score，即可知道该score所在的分区，如score=2300，位于分区3. 通过select计算3以后的比2300大的共有多少个，可以通过分数范围，一个分区一个分区地求，最后累加的结果再加1就是该用户的排名。 --------------- 允许扔XX，但请手下留情 id 都被分开了，怎么通过找id？ |
| 返回顶楼 | |
|
发表时间：2012-02-29
最后修改：2012-02-29
就一定要用数据表来完成么？
CPU，内存，外存 同学们啊！ 桶排序呗， 直接在程序中搞个数组，数组的下标就是分数，元素是每个分数对应的人数。 具体的，如果不需要精确计算，为了减少同步及遍历计算的性能损失，可以为每个数组元素设定一个预留值。 |
| 返回顶楼 | |
|
发表时间：2012-02-29
hardPass 写道 就一定要用数据表来完成么？
CPU，内存，外存 同学们啊！ 桶排序呗， 直接在程序中搞个数组，数组的下标就是分数，元素是每个分数对应的人数。 具体的，如果不需要精确计算，为了减少同步及遍历计算的性能损失，可以为每个数组元素设定一个预留值。 表示不知道你在说什么，但是感觉很牛b是的，能不能讲清楚点呢 |
| 返回顶楼 | |
|
发表时间：2012-02-29
hardPass 写道 就一定要用数据表来完成么？
CPU，内存，外存 同学们啊！ 桶排序呗， 直接在程序中搞个数组，数组的下标就是分数，元素是每个分数对应的人数。 具体的，如果不需要精确计算，为了减少同步及遍历计算的性能损失，可以为每个数组元素设定一个预留值。 都说内存不够了，用外存估计速度太慢 |
| 返回顶楼 | |
|
发表时间：2012-02-29
最后修改：2012-02-29
tsxm 写道 hardPass 写道 就一定要用数据表来完成么？
CPU，内存，外存 同学们啊！ 桶排序呗， 直接在程序中搞个数组，数组的下标就是分数，元素是每个分数对应的人数。 具体的，如果不需要精确计算，为了减少同步及遍历计算的性能损失，可以为每个数组元素设定一个预留值。 都说内存不够了，用外存估计速度太慢 1G内存还不够？如果现在排名第一的是1亿分，也就是一个长度为1亿的数组而已 300MB左右就够了，剩下的内存还可以再维护个计数缓存的数组(每个元素是上面数组希格玛，0到i)，数组长度是上面数组一样 |
| 返回顶楼 | |
|
发表时间：2012-02-29
tsxm 写道 hardPass 写道 就一定要用数据表来完成么？
CPU，内存，外存 同学们啊！ 桶排序呗， 直接在程序中搞个数组，数组的下标就是分数，元素是每个分数对应的人数。 具体的，如果不需要精确计算，为了减少同步及遍历计算的性能损失，可以为每个数组元素设定一个预留值。 都说内存不够了，用外存估计速度太慢 如果分数相同的记录不多（极端情况，每条记录的分数都不同），那么这么干内存确实是不够。 |
| 返回顶楼 | |
|
发表时间：2012-02-29
“一共2亿条记录，其中分数已经是排好了序的。”这句话很关键！
表中应该有数据库自增长的行号吧，结合实际，一旦用户注册了迅雷账号，是不会物理删除其账户信息的，so!该表第一列序号，就是你Scores的排名了，一句话： select id from tableName where userId=? 结果就是了！ 个人意见，如果说的不对，请指正！ |
| 返回顶楼 | |
|
发表时间：2012-02-29
jiuyuehe 写道 hardPass 写道 就一定要用数据表来完成么？
CPU，内存，外存 同学们啊！ 桶排序呗， 直接在程序中搞个数组，数组的下标就是分数，元素是每个分数对应的人数。 具体的，如果不需要精确计算，为了减少同步及遍历计算的性能损失，可以为每个数组元素设定一个预留值。 表示不知道你在说什么，但是感觉很牛b是的，能不能讲清楚点呢 关键字：桶排序。 |
| 返回顶楼 | |
|
发表时间：2012-02-29
phk070832 写道 tsxm 写道 hardPass 写道 就一定要用数据表来完成么？
CPU，内存，外存 同学们啊！ 桶排序呗， 直接在程序中搞个数组，数组的下标就是分数，元素是每个分数对应的人数。 具体的，如果不需要精确计算，为了减少同步及遍历计算的性能损失，可以为每个数组元素设定一个预留值。 都说内存不够了，用外存估计速度太慢 如果分数相同的记录不多（极端情况，每条记录的分数都不同），那么这么干内存确实是不够。 逻辑啊…… |
| 返回顶楼 | |
