关于实时动态排名的算法？

youareeverythin

比如像卖书的网站，怎么算出最受欢迎的top100？
怎样算保证最快最简便？

tonykee

如果是数据库：
select top 100 from book order by visted desc
如果不是数据库，最简单的，用stl，定义一个带comparetor的容器，能自动按你指定的要求排列对象。

youareeverythin

没讲到点子上啊，如果记录数有几亿也这么去算？能不能拿个具体点设计方案，计算量要求最小，然后能比较动态。

vinjn

比如按点击数来算
1.数据的实时更新
万数量级的放一个map中（ISBN到点击数的映射表，以下同）
千数量级的放一个map中
百数量级的放一个map中
等等
2.查找
从万数量级开始，递归划分，9万的，8万的，7万的，等等
只要100个满了就退出

开始排序的间隔设多大可以参考从网站以往的数据

youareeverythin

楼上的想法和空间划分的算法类似，可以减少计算量，但是计数量统计怎么优化？比如我要算出近2小时的计数量。然后每隔5分钟或10分钟更新一次。

tonykee

如果涉及到几亿的数据量的排序，那基本上可以说是设计思路本身就有问题的。这样的数据排序难道不能避免吗？你可以设置几个数据区域，范围分区来存放数据，类似于orale的分区表结构

另外实在不能避免，建议你借鉴一下数据库的分区＋索引机制，其存储结构本身就是按顺序的 ，我提到的stl里面的compare接口也是起这个作用的，你想的问题stl其实早就实现了

youareeverythin

分区能理解，但是分区和compare有什么关系？

现在的问题是收集信息，总不能每个时间段弄个字段，然后更新的时候把这些字段相加再去比较，即使有个累加字段计算量还是挺大的。你说算几亿的设计思路有问题，当然有问题了，我不正在问怎么设计吗。

tonykee

stl的compare能实现自动排序，有点类似于索引
你把你的数据分为一些大的范围区域，一个区域建立一个容器
分区＋自动排序 还不明白吗？这其中还要用到序列化的策略，不可能实时加载所有的数据，最多一次加载某一个页或区的数据

要我怎么说呢，还是你自己好好想想吧，也许可以有更好的办法
建议你用纯数据库内部来解决你的问题（索引＋范围分区就搞定）效率高，非数据库可以用上面的做法，复杂的事情都要由你自己来做了