performance - 高效动态地在内存中对多个用户进行排名？

Question

我运行一个 Java 游戏服务器，我需要在其中以各种方式有效地对玩家进行排名。例如，按分数、金钱、赢得的游戏和其他成就。这样我就可以识别给定类别中排名前 25 位的玩家，为这些玩家应用奖牌，并随着排名的变化动态更新它们。性能是重中之重。

请注意，这不能仅在数据库中轻松完成，因为排名将来自不同的数据源和不同的数据库表，所以我希望在内存中处理这一切，并在排名列表上调用方法值需要更新。此外，许多用户可能会获得相同的排名。

例如，假设我在数据库中有一百万玩家。某位玩家可能会获得一些额外积分，并立即从第 21,305 位上升到第 23 位，然后又从前 25 名名单中掉下来。我需要一种方法来有效地处理这个问题。我想象会使用某种双向链表，但我不确定如何处理快速跳转列表中的许多点而不一次遍历它以找到正确的新排名。玩家可以并列的事实让事情变得有点复杂，因为排名列表中的每个元素都可以有多个用户。

你会如何用 Java 处理这个问题？

Answer 1

我不知道是否有库可以帮助你，但我认为你可以在内存中维护一个最小堆。当一个玩家的点更新时，你可以将其与堆的根进行比较，如果小于，什么都不做。否则调整堆。

这意味着，您可以维护一个具有 25 个节点的最小堆，即一个类别中所有玩家中最高的 25 个节点。