Python自定义比较器是如何工作的？

Question

I have the following Python dict:

[(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])]

现在我无法理解比较器是如何工作的，哪两个值正在被传递以及会发生多少次这样的比较？它是否在内部创建了一个排序后的键列表，以跟踪每个比较所做的情况？此外，行为似乎非常随机。 我很困惑，希望能得到帮助。

- avinash shah

---

您正在尝试对字典或列表进行排序吗？字典是无序的，这意味着您不能更改它们的顺序。在您的示例中，您展示了一个元组列表。您想要排序什么？ - MikeTGW

请注意，虽然Python 2支持将自定义比较函数传递给sort()，但Python 3不支持。主要原因是使用自定义键函数要比使用自定义比较函数更高效，因为键函数只需要针对每个列表项调用一次，而比较函数必须为进行的每次比较调用一次。有关详细信息，请参见RussellLuo回答中的链接。 - PM 2Ring

这是一个类似的问题：https://dev59.com/k6nka4cB1Zd3GeqPU96x#49327441 - Eziz Durdyyev

Answer 1

“比较的数字和方式并未在文档中记录，实际上，它可以在不同的实现中自由更改。唯一的保证是，如果比较函数是有意义的，该方法将对列表进行排序。”

“CPython使用Timsort算法来对列表进行排序，因此您看到的是该算法执行比较的顺序（如果我没有错，对于非常短的列表，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]

- Bakuriu

---

漂亮的答案！感谢您的帮助。 - avinash shah

Answer 2

“比较器如何工作”

这个已经有很好的文档记录了：

“比较两个对象x和y，并根据结果返回一个整数，若xy则返回正数。”

你可以不用调用cmp函数，直接像下面这样写：

sum_a=sum(a[1])
sum_b=sum(b[1])
if sum_a < sum_b: 
   return -1
elif sum_a == sum_b:
   return 0
else:
   return 1

“传递了哪两个值”

从您的打印语句中，可以看到传递的两个值。让我们看一下第一个迭代：

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

在这里打印的是一个元组(a, b)，因此传递到比较函数中的实际值为：

a = (3, [1, 0, 0, 0, 1])
b = (2, [3, 4, 5]))

通过您的函数，您比较每个元组中两个列表的总和，您在代码中将其表示为sum_a和sum_b。

“那么会有多少此类比较呢？”

我猜你真正想问的是：如何通过调用单个函数来实现排序？

简短的答案是：它使用Timsort算法，并调用比较函数O(n * log n)次（注意实际调用次数为c * n * log n，其中c>0）。

要理解发生了什么，请想象一下对值列表进行排序，例如v = [4,2,6,3]。如果您按系统方式进行操作，可能会这样做：

1.从第一个值开始，即索引i = 0

2.将v[i]与v[i + 1]进行比较

3.如果v[i + 1] < v[i]，则交换它们

4.增加i，从2重复，直到i == len(v) - 2

5.从1开始，直到不再发生进一步交换

所以你得到，i =

0: 2 < 4 => [2, 4, 6, 3] (swap)
1: 6 < 4 => [2, 4, 6, 3] (no swap)
2: 3 < 6 => [2, 4, 3, 6] (swap)

重新开始：

0: 4 < 2 => [2, 4, 3, 6] (no swap)
1: 3 < 4 => [2, 3, 4, 6] (swap)
2: 6 < 4 => [2, 3, 4, 6] (no swap)

重新开始 - 不会再有交换了，所以停止。您的列表已经排序。在这个例子中，我们运行了3次列表，并进行了3 * 3 = 9次比较。

显然这不是很有效率--sort()方法只调用了你的比较函数5次。原因是它使用比上面解释的简单算法更高效的排序算法。

此外，行为似乎非常随机。

请注意，传递给比较函数的值序列通常未定义。但是，sort函数会对其接收到的可迭代对象的任何两个值之间进行所有必要的比较。

它是否在内部创建一个已排序的键列表，以跟踪进行的每次比较？

不，它并没有在内部维护一个键的列表。相反，排序算法基本上是在给定的列表上进行迭代。实际上，它构建了列表的子集，以避免进行太多的比较 - 在Aldo Cortesi的Visualising Sorting Algorithms: Python's timsort中有一个很好的可视化展示了排序算法的工作方式。

- miraculixx

---

感谢您对比较器在示例列表上工作的逐步演示，非常棒。+1。 - avinash shah

Answer 3

首先，是cmp()函数：

cmp(...)
    cmp(x, y) -> integer
    Return negative if x<y, zero if x==y, positive if x>y.

您正在使用此行代码：items.sort(myComparator)，这相当于说：items.sort(-1)或items.sort(0)或items.sort(1)

由于您想要按每个元组列表的总和进行排序，因此可以使用以下方法：

mylist = [(2, [3, 4, 5]), (3, [1, 0, 0, 0, 1]), (4, [-1]), (10, [1, 2, 3])]
sorted(mylist, key=lambda pair: sum(pair[1]))

这段代码的作用是，我认为，正是你想要的。根据每个元组列表的sum()对mylist进行排序。

- MikeTGW

Answer 4

基本上，对于简单列表（例如[2, 4, 6, 3, 1]）和您提供的复杂列表，排序算法是相同的。

唯一的区别在于列表中元素的复杂性以及如何比较任何两个元素的比较方案（例如您提供的myComparator）。

有一个关于Python排序的良好描述：https://wiki.python.org/moin/HowTo/Sorting

- RussellLuo