algorithm - 输赢系统的排序算法选择

Question

我有一堆元素与其他一些元素进行了比较，要么赢要么输。没有完整的数据，例如与所有其他元素相比的所有元素。相反，我有一个这样的列表：

win_id | lose_id
12       73
992      25
22       12
2382     999
etc etc

我想为大量元素找到一种相当快的算法，该算法还考虑到与赢得很多胜利的人的胜利（将被认为比与普通人获胜更重要）。

Elo 是一个不错的选择吗，还是有什么东西可以跑得更快一些？我对此的单独用例将是：

寻找前 10 名（需要准确）

寻找整体位置（不需要完美的准确性）

Answer 1

您是否考虑过将 ELO 与红黑树之类的东西结合起来以保持数据排序？ELO 是您所描述内容的自然选择，而且速度与您希望的一样快，因为更新 ELO 是一个恒定时间操作。

然后，您可以使用红黑树按 ELO 对整个数据集进行排序。每当发生新匹配时，更新将花费 O(log n): O(1) 重新计算每个 ELO 分数，然后 O(log n) 重新配置红黑树。您描述的所有其他操作：查找前 10 个，或计算任何给定元素的排名，或查找第 n 个元素，都将是 O(log n) 操作。