|
锁定老帖子 主题：迅雷的一个面试题
精华帖 (8) :: 良好帖 (3) :: 新手帖 (0) :: 隐藏帖 (1)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2012-02-29
hardPass 写道 tsxm 写道 hardPass 写道 就一定要用数据表来完成么？
CPU，内存，外存 同学们啊！ 桶排序呗， 直接在程序中搞个数组，数组的下标就是分数，元素是每个分数对应的人数。 具体的，如果不需要精确计算，为了减少同步及遍历计算的性能损失，可以为每个数组元素设定一个预留值。 都说内存不够了，用外存估计速度太慢 1G内存还不够？如果现在排名第一的是1亿分，也就是一个长度为1亿的数组而已 300MB左右就够了，剩下的内存还可以再维护个计数缓存的数组(每个元素是上面数组希格玛，0到i)，数组长度是上面数组一样 不知道你怎么算的。假设极端情况，每个记录的分数都不相同，那么如果全部加载到内存，对于2亿条记录，假设scores用4个字节的整型保存，那么需要64*10^8bit，1G约为10^9bit，内存明显放不下。 |
| 返回顶楼 | |
|
发表时间：2012-02-29
最后修改：2012-02-29
phk070832 写道 hardPass 写道 tsxm 写道 hardPass 写道 就一定要用数据表来完成么？
CPU，内存，外存 同学们啊！ 桶排序呗， 直接在程序中搞个数组，数组的下标就是分数，元素是每个分数对应的人数。 具体的，如果不需要精确计算，为了减少同步及遍历计算的性能损失，可以为每个数组元素设定一个预留值。 都说内存不够了，用外存估计速度太慢 1G内存还不够？如果现在排名第一的是1亿分，也就是一个长度为1亿的数组而已 300MB左右就够了，剩下的内存还可以再维护个计数缓存的数组(每个元素是上面数组希格玛，0到i)，数组长度是上面数组一样 不知道你怎么算的。假设极端情况，每个记录的分数都不相同，那么如果全部加载到内存，对于2亿条记录，假设scores用4个字节的整型保存，那么需要64*10^8bit，1G约为10^9bit，内存明显放不下。 他的数组不是直接存放分数，而是数组下表存放，即使这样，1亿的分数就得1个数组，每个数组你就算定义为1个字节，也得1个g啊，题目给给出的元素有序应该是很重要的提示，不然他说着干嘛 |
| 返回顶楼 | |
|
发表时间：2012-02-29
tsxm 写道 phk070832 写道 hardPass 写道 tsxm 写道 hardPass 写道 就一定要用数据表来完成么？
CPU，内存，外存 同学们啊！ 桶排序呗， 直接在程序中搞个数组，数组的下标就是分数，元素是每个分数对应的人数。 具体的，如果不需要精确计算，为了减少同步及遍历计算的性能损失，可以为每个数组元素设定一个预留值。 都说内存不够了，用外存估计速度太慢 1G内存还不够？如果现在排名第一的是1亿分，也就是一个长度为1亿的数组而已 300MB左右就够了，剩下的内存还可以再维护个计数缓存的数组(每个元素是上面数组希格玛，0到i)，数组长度是上面数组一样 不知道你怎么算的。假设极端情况，每个记录的分数都不相同，那么如果全部加载到内存，对于2亿条记录，假设scores用4个字节的整型保存，那么需要64*10^8bit，1G约为10^9bit，内存明显放不下。 他的数组不是直接存放分数，而是数组下表存放，即使这样，1亿的分数就得1个数组，每个数组你就算定义为1个字节，也得1个g啊，题目给给出的元素有序应该是很重要的提示，不然他说着干嘛 打字的时候想错了，把scores改为id |
| 返回顶楼 | |
|
发表时间：2012-02-29
最后修改：2012-02-29
通过id获得score。
2亿条数据又是按score排序的。 计算下小于score有多少就知道排名了。 |
| 返回顶楼 | |
|
发表时间：2012-02-29
用户的id是已知的
1：根据id获得score 2：count出 >score的数量a 3：取出等于这个score的记录 遍历查找这个id 的下标b 排名即为 a + b+1 个人浅见。。望各位大虾指正~ |
| 返回顶楼 | |
|
发表时间：2012-02-29
最后修改：2012-02-29
我觉得ls回答的有问题，lz问题也有歧义。到底这个id, score里的id是不是用户id?还是只是一个pk?
如果说题目实质上是求在这个表结构下，已知score，求score的排名，那么 select count(1) from table where score<=score# 不就完了么？score是有index的，这样的操作用的了几秒钟？ 楼上说什么分区，对于这种显然是要跨分区查询的sql，并没有什么特别的好处。 求喷。 |
| 返回顶楼 | |
|
发表时间：2012-02-29
iatneh 写道 用户的id是已知的
1：根据id获得score 2：count出 >score的数量a 3：取出等于这个score的记录 遍历查找这个id 的下标b 排名即为 a + b+1 个人浅见。。望各位大虾指正~ 不错，与我的思路差不多。 |
| 返回顶楼 | |
|
发表时间：2012-02-29
Kisses99 写道 我觉得ls回答的有问题，lz问题也有歧义。到底这个id, score里的id是不是用户id?还是只是一个pk?
如果说题目实质上是求在这个表结构下，已知score，求score的排名，那么 select count(1) from table where score<=score# 不就完了么？score是有index的，这样的操作用的了几秒钟？ 楼上说什么分区，对于这种显然是要跨分区查询的sql，并没有什么特别的好处。 求喷。 是用户id ，我试了下，600w要28s。蛮满的 |
| 返回顶楼 | |
|
发表时间：2012-02-29
我看题目之说了数据源，不一定是数据库吧。。
我觉得其实就是通过分数从高到低来找id int rank=1; //记录上个分数相同节点的排名 Node preNode; //一条一条的去记录集 Collection c; while(c.hasNext()){ c=c.next(); if(c.score!=preNode.score){ proNode = <rank+1,c.score>; } if(c.id!=searchId){ rank++; }else{ break; } } |
| 返回顶楼 | |
|
发表时间：2012-02-29
这个最好能有个全局变量记录当前每个分数都有多少人 , 请求过来先根据路由规则找到所在的表 , 查到分数后 , 对小于该分数的用户数进行连加就OK了 , 不过需要应用一开始就有这个设计
|
| 返回顶楼 | |
