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 是 而不是 跟踪 "keys"。每次进行比较时，它都会调用您的比较函数。所以你的函数可以被调用超过 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]

Answer 2

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

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

Python排序有很好的描述：https://wiki.python.org/moin/HowTo/Sorting

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

Answer 4

how the comparator is working

这个不错documented:

Compare the two objects x and y and return an integer according to the outcome. The return value is negative if x < y, zero if x == y and strictly positive if x > y.

您可以这样写来代替调用 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

which two values are being passed

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

((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。

and how many such comparisons would happen?

我猜你真正想问的是：排序是如何工作的，只调用一个函数？

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

要了解正在发生的事情，想象一下自己对值列表进行排序，比如 v = [4,2,6,3]。如果您系统地进行此操作，您可能会这样做：

从第一个值开始，索引 i = 0
比较 v[i] 和 v[i+1]
如果 v[i+1] < v[i]，交换它们
增加 i，从 2 开始重复直到 i == len(v) - 2
从 1 开始，直到不再发生交换

所以你得到，我=

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 次。原因是它采用了一种比上面解释的简单算法更有效的排序算法。

Also the behavior seems to be very random.

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

Is it creating a sorted list of keys internally where it keeps track of each comparison made?

不，它没有在内部保留密钥列表。相反，排序算法本质上是遍历您提供的列表。事实上，它构建了列表的子集以避免进行太多比较 - 在 Visualising Sorting Algorithms: Python's timsort by Aldo Cortesi

处可以很好地直观地了解排序算法的工作原理

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

How does a Python custom comparator work?

python

python-2.x