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) 操作。