动态排行榜有什么高效算法吗

lymslive

像游戏排行榜这类问题，应该算是部分有序的排序问题吧。
从开服开始，榜上无人算起，随后逐渐加入更多的人排在里面，而且已经在榜上的人，其排序指标数值也经常变化，因而要对他重新定位排序。

对这类问题，做游戏服务端开发的同学们是怎么实现功能，怎样的算法比较高效。
我以前待过的一个项目，基本是用类似“插入排序”的算法，更新榜内的人的位置。请问有什么更好的算法思路吗？

sea_bug

一般不用那么麻烦，填到库里，一条sql语句就出来了。

looncity

首先很荣幸回答你的这个问题。
先说点题外话，本人有很多年的游戏行业经验。ARPG类型游戏的所有功能都做过，当然包括游戏排行榜的设计。
我当时的设计思路是这样的，当然也经过的市场的验证。
1.因为确实如你所说，排行榜需要经常更新，所以常驻内存，定期保存数据库才是正道。
2.排行榜一般每隔半小时更新一次，如果是到点了才去取所有玩家的数据，包括离线玩家的，数据量太大，这样子肯定性能是不行的。
3.配合建立一个排行榜的数据库，里面只有很简单的“战力：玩家名，玩家等级”之类的，战力作为索引，当然也有可能等级也作为索引，多索引来操作。
4.每个玩家进来，新建号或重新进入，战力改变了，怎么办？很简单，不用管，等到玩家定期保存，或者下线的时候，把当前数据保存一下排行榜的数据库，相同玩家名的替换掉，当然这个数据库也可以常驻内存，定期再保存。
5.这个时候如果排行榜到点了，需要更新，就直接可以从排行榜的数据库里取数据了，因为数据量很小，速度可以很快，取的时候再做下数量的限制，和做下排序也是很快的事情。
6.当然你可能觉得担心排序性能不好，有办法，可以在保存的时候自己做下排序，插入到合适的地方，或者假如数据常驻在内存的话，那就更方便了，用你擅长的结构来存储。
7.上面是主要思路，也是本人很多年前的做法，当然肯定有更好的优化的方法，需要大家一起交流。
最后打个小广告，本人写的一款引擎：Fly3D，可以发布页游，微端，手游，也可以支持服务端，代码全部用lua编写，工具完整，文档丰富，官网完善。我在这个论坛发了原创帖子，叫Fly3D引擎，有兴趣的同学可以进去看看，谢谢。

lymslive

谢谢楼上的详细解答。
我原来想问的确实在内存的实时排序，倒是没提及保存，定时保存这是不言而喻要做的。
我就是在想，数据规模足够全放在内存时（比如一般游戏比较关注前几百名或几千名吧），怎样的数据结构与算法设计会高效点。
ps，如果真要排所有玩家，数据规模没法放在内存中了，那真是另一个更头痛的问题。

looncity

其实当你真正做这个事情的时候，问题都会迎刃而解，现在的服务器随便可以开个8G16G的内存，对于存储排行榜这种数据来说小菜一碟，甚至存储游戏所有几千个玩家数据都是可以的，不用把问题想复杂化了。