系统设计-排行榜

• 精确、近似排行榜
• 实时非实时排行榜
• 最近一天的排行榜

是否要那么及时？离线在线相结合。

是否要准确？近似算法，lossy counting， 桶计数等，可以省略小数点。 准确的只能排名，比如维护有序树结构可以o(logn)

是否可以Top K? 堆，节省内存。

排行榜

• 实时的可以利用zset，如何数据量大，可以按分数分成多个zset。然后排名时前缀和累加即可。
• 实时性不高的可以离线跑， 定时任务。比如map reduce
• 对于最近7天这种 可以存每天排行榜，然后最近7天就是取并集。

Top K

• 回答点关键是 分治和堆, 分片后进行归并。

近似

• 桶排序，比如分数100分 每0.1分一个桶计数，对于分数集中统计结果误差更大。

• Lossy Counting

  • 比如每秒维护一个map, hashmap counting, 每次轮换counter减1， 不停轮换清counter为0的，因此对于counting小于map数的可能漏掉。
  • 优点就是map对于counting小于map数的直接给丢掉了，节省内存。

• 计数 count-min sketch

  • bloom filter基础上增加计数，以最小那个hash计数为值