posort 0.1

比较器

比较器接受两个元素 a 和 b 并返回

0 - 如果它们相等，如果 a > b 则返回一个正数，如果 a < b 则返回一个负数

例如，整数上的自然比较器是

def small_first(a, b)

return a - b

Python 的 sorted 函数将比较器函数作为关键字参数

>>> sorted([1, 5, 2, 4, 3], cmp=small_first)
[1, 2, 3, 4, 5]

我们可以选择按不同的标准进行排序。例如，我们可能选择优先考虑偶数

def evens_first(a, b)

return a%2 - b%2

>>> sorted([1, 5, 2, 4, 3], cmp=evens_first)
[4, 2, 5, 1, 3]

注意在上面的例子中，所有偶数都排在所有奇数之前；evens_first 被满足。另外，请注意有几种可能的解决方案。在这种情况下，有 12 种可能的解决方案，都满足比较器函数。 sorted 会随机返回一个。

posort

要获得 [2, 4, 1, 3, 5] 这样的解决方案，其中数字首先按偶数性排序，然后按大小排序，我们可以使用 posort 函数。

posort 函数试图满足一系列按优先级递减的比较器函数。

>>> posort([1, 5, 2, 4, 3], evens_first, small_first)
[2, 4, 1, 3, 5]

偶数的规则优于小数的规则。可以指定任意数量的比较器函数。

等效结构

比较器函数完全指定了一个 [偏序](http://en.wikipedia.org/wiki/Partial_order#Formal_definition)。

比较器函数可以描述任何 [有向无环图 (DAG)](http://en.wikipedia.org/wiki/Directed_acyclic_graph)

作者

[Matthew Rocklin](http://matthewrocklin.com)

许可证

新BSD许可证。见LICENSE.txt

历史

这个想法最初是为 [Theano项目](http://github.com/theano/theano) 开发的