python - Python 自定义比较器如何工作？

Question

我有以下 Python 字典:

[(2, [3, 4, 5]), (3, [1, 0, 0, 0, 1]), (4, [-1]), (10, [1, 2, 3])]

现在我想根据字典值的总和对它们进行排序，因此对于第一个键，值的总和为 3+4+5=12。

我编写了以下代码来完成这项工作:

def myComparator(a,b):
    print "Values(a,b): ",(a,b)
    sum_a=sum(a[1])
    sum_b=sum(b[1])
    print sum_a,sum_b
    print "Comparision Returns:",cmp(sum_a,sum_b)
    return cmp(sum_a,sum_b)

items.sort(myComparator)
print items

这是我在上面运行后得到的输出:

Values(a,b):  ((3, [1, 0, 0, 0, 1]), (2, [3, 4, 5]))
2 12
Comparision Returns: -1
Values(a,b):  ((4, [-1]), (3, [1, 0, 0, 0, 1]))
-1 2
Comparision Returns: -1
Values(a,b):  ((10, [1, 2, 3]), (4, [-1]))
6 -1
Comparision Returns: 1
Values(a,b):  ((10, [1, 2, 3]), (3, [1, 0, 0, 0, 1]))
6 2
Comparision Returns: 1
Values(a,b):  ((10, [1, 2, 3]), (2, [3, 4, 5]))
6 12
Comparision Returns: -1
[(4, [-1]), (3, [1, 0, 0, 0, 1]), (10, [1, 2, 3]), (2, [3, 4, 5])]

现在我无法理解比较器是如何工作的，传递了哪两个值以及会发生多少次这样的比较？它是否在内部创建了一个排序的键列表，用于跟踪每次比较？此外，行为似乎非常随机。我很困惑，任何帮助将不胜感激。

Answer 1

没有记录数量和进行了哪些比较，事实上，它可以根据不同的实现自由更改。唯一的保证是，如果比较函数有意义，该方法将对列表进行排序。

CPython 使用 Timsort algorithm对列表进行排序，所以您看到的是该算法执行比较的顺序(如果我没有误认为是非常短的列表，Timsort 只是使用插入排序)

Python 不跟踪“键”。每次进行比较时，它都会调用您的比较函数。因此，您的函数可以被调用的次数远远超过 len(items) 次。

如果你想使用键，你应该使用 key 参数。事实上你可以这样做:

items.sort(key=lambda x: sum(x[1]))

这将创建键，然后使用键上常用的比较运算符进行排序。这保证仅调用 key 传递的函数 len(items) 次。

---

鉴于您的列表是:

[a,b,c,d]

您看到的比较顺序是:

b < a   # -1  true   --> [b, a, c, d]
c < b   # -1  true   --> [c, b, a, d]
d < c   # 1   false
d < b   # 1   false
d < a   # -1  true   --> [c, b, d, a]