高效的排行榜数据结构

Question

我想要实现一个排行榜，但我意识到即使这看起来是一个简单的任务，也可能会变得非常复杂。我可以使用正确索引的数据库，但我想知道是否有一种高效的数据结构可以支持以下操作。

• 为给定玩家添加分数
• 检索给定玩家的最佳得分
• 检索给定玩家的排名
• 检索得分高于和低于当前玩家排名的玩家
• 支持不同的时间范围：今天的得分、本周、今年等
• 适用于大约100,000个玩家
• 尽可能小的内存占用（即在廉价机器上运行）

感谢您的帮助！

- Martin

---

你们有每个玩家的最大分数限制吗？如果没有，如果有10万个玩家，你们可能会有很多分数……整个游戏需要一次性全部放在内存中吗，还是可以大部分放在磁盘（闪存等）上？分数看起来像什么（0-255？0-65525？字符串？）。当你说“便宜的机器”时，你是指旧PC，对吧，而不是手机或Arduino。 - angelatlarge

Answer 1

解决方案是使用两种数据结构。更新操作将需要O(n)的时间，因为不仅给定的玩家，所有玩家的排名都必须重新计算。"最初的回答"

We will use two DS for this:
    a. Balanced Binary Search Tree
    b. Hash Map

Each node of a Binary Search Tree is [Uid, Score, Reverse-rank]
    Uid: is the user id of a player.
    Score: is the score of a player.
    Reverse-rank: This is a rank of a player but in reverse order. The player scoring lowest will
    have this value as 1. The player scoring highest will have this value as the size of a BST.

    The Binary Search Tree is implemented based on the score of a player.

The Hash Map structure is as follows:
    Key: Uid
    Value: BST Node.

updateRank(userId, score)
    if player is new (userid not in map)
        1. Insert the player in a BST.
        2. Insert the player in a Map.
        3. Calculate Rank: If a node is inserted to right, then its rank will be one less than its
        parent. If a node is inserted to left, then its rank will be one more than its parent.

    if player is old (userid exists in map)
        1. Fetch the node from Map.
        2. if new score and old score is same then do nothing.
        3. Delete the old node.
        4. Insert the new node.
        5. Calculate Rank: Perform in-order and mark all the nodes from 1 to n (length).
           This op is expensive among all. It takes O(n)
    O(n)

getRank(userId)
    Find a node from the map.
    return rank as (n + 1) - reverse rank
    O(1)

display()
    Perform inorder traversal and return all the players.
    O(n)

NOTE: 1. The tree has to be balanced BST.
      2. We cannot use heap because, the display() would be difficult to implement. We would have
      to remove every element from heap which would take O(nlogn).

- Juvenik

Answer 2

你可以使用二叉搜索树（平衡的 AVL 或红黑树）来存储基于总分数的玩家信息。在玩家结构中，您可以使用不同的数组来表示不同的时间框架，同时还有单独的变量来记录总分数和最高分数。要查找某个玩家的排名或比他强的玩家，需要进行一次中序遍历。

- uba