如何在Python 3.x中获得类似2.x的sorting行为？

我试图在3.x中复制Python 2.x的sorting行为（如果可能的话还可以改进），以便相互定义的types（如int ， float等）按照预期进行sorting，并将相互无法编码的types分组在输出中。

这是我正在谈论的一个例子：

 >>> sorted([0, 'one', 2.3, 'four', -5]) # Python 2.x [-5, 0, 2.3, 'four', 'one'] 

 >>> sorted([0, 'one', 2.3, 'four', -5]) # Python 3.x Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: unorderable types: str() < int() 

我以前的尝试，使用一个类的关键参数sorted() （请参阅为什么这个关键类sorting异类序列行为奇怪？ ）是根本上打破，因为它的方法

1. 试图比较价值观和
2. 如果失败，则回退到比较其types的string表示forms

会导致不及物动词的sorting，正如BrenBarn的出色答案所解释的那样 。

一个天真的方法，我最初拒绝，甚至没有尝试编码，将使用返回一个(type, value)元组的关键函数：

 def motley(value): return repr(type(value)), value 

但是，这不是我想要的。 首先，它打破了相互可订购types的自然顺序：

 >>> sorted([0, 123.4, 5, -6, 7.89]) [-6, 0, 5, 7.89, 123.4] >>> sorted([0, 123.4, 5, -6, 7.89], key=motley) [7.89, 123.4, -6, 0, 5] 

其次，当input包含两个相同的内部无法编辑的对象时，会引发一个exception：

 >>> sorted([{1:2}, {3:4}], key=motley) Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: unorderable types: dict() < dict() 

…无可否认，这是Python 2.x和3.x中的标准行为 – 但理想情况下，我希望将这些types组合在一起（我并不特别关心它们的sorting，但似乎与之保持一致Python保证稳定的sorting，保留原来的顺序）。

我可以通过特殊的方法解决数字types的第一个问题：

 from numbers import Real from decimal import Decimal def motley(value): numeric = Real, Decimal if isinstance(value, numeric): typeinfo = numeric else: typeinfo = type(value) return repr(typeinfo), value 

…尽可能地发挥作用：

 >>> sorted([0, 'one', 2.3, 'four', -5], key=motley) [-5, 0, 2.3, 'four', 'one'] 

…但是没有考虑到可能存在其他可以相互订购的不同的（可能是用户定义的）types的事实，并且当然仍然以本质上不可判定的types失败：

 >>> sorted([{1:2}, {3:4}], key=motley) Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: unorderable types: dict() < dict() 

是否还有另一种方法可以解决任意的，独特而又相互可订的types和本质上无法编码的types的问题？

Answer 1

愚蠢的想法：首先把所有不同的项目进行分组，把它们相互比较，然后对各个组进行sorting，最后将它们连接起来。 我假设一个项目可以与一个组的所有成员相比，如果它与一个组的第一个成员相当。 像这样（Python3）：

 import itertools def python2sort(x): it = iter(x) groups = [[next(it)]] for item in it: for group in groups: try: item < group[0] # exception if not comparable group.append(item) break except TypeError: continue else: # did not break, make new group groups.append([item]) print(groups) # for debugging return itertools.chain.from_iterable(sorted(group) for group in groups) 

在可悲的情况下，这将有二次运行时间，没有任何项目是可比较的，但我想知道这一点肯定的唯一方法是检查所有可能的组合。 对于任何试图sorting一大堆不可退化项目的人来说，将这种二次方行为看作是一种应有的惩罚，就像复数一样。 在更常见的情况下，一些string和一些整数的混合，速度应该是类似于正常sorting的速度。 快速testing：

 In [19]: x = [0, 'one', 2.3, 'four', -5, 1j, 2j, -5.5, 13 , 15.3, 'aa', 'zz'] In [20]: list(python2sort(x)) [[0, 2.3, -5, -5.5, 13, 15.3], ['one', 'four', 'aa', 'zz'], [1j], [2j]] Out[20]: [-5.5, -5, 0, 2.3, 13, 15.3, 'aa', 'four', 'one', 'zz', 1j, 2j] 

这似乎也是一个“稳定的sorting”，因为这些组织是按照无与伦比的项目的顺序组成的。

Answer 2

这个答案旨在忠实地重新创buildPython 2的sorting顺序，在Python 3中，每一个细节。

实际的Python 2实现是相当object.c的 ，但是object.c的default_3way_compare在实例被赋予实现正常比较规则的机会之后进行最后的回退。 这是在个别types被给予机会比较之后（通过__cmp__或__lt__钩子）。

在封装器中将该函数实现为纯Python，再加上模拟规则的exception（特别是dict和复数）给了我们Python 3中相同的Python 2sorting语义：

 from numbers import Number # decorator for type to function mapping special cases def per_type_cmp(type_): try: mapping = per_type_cmp.mapping except AttributeError: mapping = per_type_cmp.mapping = {} def decorator(cmpfunc): mapping[type_] = cmpfunc return cmpfunc return decorator class python2_sort_key(object): _unhandled_types = {complex} def __init__(self, ob): self._ob = ob def __lt__(self, other): _unhandled_types = self._unhandled_types self, other = self._ob, other._ob # we don't care about the wrapper # default_3way_compare is used only if direct comparison failed try: return self < other except TypeError: pass # hooks to implement special casing for types, dict in Py2 has # a dedicated __cmp__ method that is gone in Py3 for example. for type_, special_cmp in per_type_cmp.mapping.items(): if isinstance(self, type_) and isinstance(other, type_): return special_cmp(self, other) # explicitly raise again for types that won't sort in Python 2 either if type(self) in _unhandled_types: raise TypeError('no ordering relation is defined for {}'.format( type(self).__name__)) if type(other) in _unhandled_types: raise TypeError('no ordering relation is defined for {}'.format( type(other).__name__)) # default_3way_compare from Python 2 as Python code # same type but no ordering defined, go by id if type(self) is type(other): return id(self) < id(other) # None always comes first if self is None: return True if other is None: return False # Sort by typename, but numbers are sorted before other types self_tname = '' if isinstance(self, Number) else type(self).__name__ other_tname = '' if isinstance(other, Number) else type(other).__name__ if self_tname != other_tname: return self_tname < other_tname # same typename, or both numbers, but different type objects, order # by the id of the type object return id(type(self)) < id(type(other)) @per_type_cmp(dict) def dict_cmp(a, b, _s=object()): if len(a) != len(b): return len(a) < len(b) adiff = min((k for k in a if a[k] != b.get(k, _s)), key=python2_sort_key, default=_s) if adiff is _s: # All keys in a have a matching value in b, so the dicts are equal return False bdiff = min((k for k in b if b[k] != a.get(k, _s)), key=python2_sort_key) if adiff != bdiff: return python2_sort_key(adiff) < python2_sort_key(bdiff) return python2_sort_key(a[adiff]) < python2_sort_key(b[bdiff]) 

我并入处理Python 2中实现的字典sorting ，因为这将通过types本身通过__cmp__钩子来支持。 我自然也坚持Python 2的键和值的sorting。

我还为复数添加了特殊的shell，因为当你尝试对这些数据进行sorting时，Python 2引发了一个exception：

 >>> sorted([0.0, 1, (1+0j), False, (2+3j)]) Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: no ordering relation is defined for complex numbers 

如果您想精确模拟Python 2的行为，则可能需要添加更多特殊情况。

如果你想sorting复杂的数字无论如何，你需要始终把他们与非数字组; 例如：

 # Sort by typename, but numbers are sorted before other types if isinstance(self, Number) and not isinstance(self, complex): self_tname = '' else: self_tname = type(self).__name__ if isinstance(other, Number) and not isinstance(other, complex): other_tname = '' else: other_tname = type(other).__name__ 

一些testing用例：

 >>> sorted([0, 'one', 2.3, 'four', -5], key=python2_sort_key) [-5, 0, 2.3, 'four', 'one'] >>> sorted([0, 'one', 2.3, 'four', -5], key=python2_sort_key) [-5, 0, 2.3, 'four', 'one'] >>> sorted([0, 123.4, 5, -6, 7.89], key=python2_sort_key) [-6, 0, 5, 7.89, 123.4] >>> sorted([{1:2}, {3:4}], key=python2_sort_key) [{1: 2}, {3: 4}] >>> sorted([{1:2}, None, {3:4}], key=python2_sort_key) [None, {1: 2}, {3: 4}] 

Answer 3

不在这里运行Python 3，但也许这样的事情会工作。 testing一下，如果在“值”上做一个“小于”的比较会创build一个exception，然后做“某事”来处理这种情况，比如将其转换为string。

当然如果列表中的其他types不是相同的types，但是可以相互订购的话，你仍然需要更多的特殊处理。

 from numbers import Real from decimal import Decimal def motley(value): numeric = Real, Decimal if isinstance(value, numeric): typeinfo = numeric else: typeinfo = type(value) try: x = value < value except TypeError: value = repr(value) return repr(typeinfo), value >>> print sorted([0, 'one', 2.3, 'four', -5, (2+3j), (1-3j)], key=motley) [-5, 0, 2.3, (1-3j), (2+3j), 'four', 'one'] 

Answer 4

为了避免使用exception，并采取基于types的解决scheme，我想出了这个：

 #! /usr/bin/python3 import itertools def p2Sort(x): notImpl = type(0j.__gt__(0j)) it = iter(x) first = next(it) groups = [[first]] types = {type(first):0} for item in it: item_type = type(item) if item_type in types.keys(): groups[types[item_type]].append(item) else: types[item_type] = len(types) groups.append([item]) #debuggng for group in groups: print(group) for it in group: print(type(it),) # for i in range(len(groups)): if type(groups[i][0].__gt__(groups[i][0])) == notImpl: continue groups[i] = sorted(groups[i]) return itertools.chain.from_iterable(group for group in groups) x = [0j, 'one', 2.3, 'four', -5, 3j, 0j, -5.5, 13 , 15.3, 'aa', 'zz'] print(list(p2Sort(x))) 

请注意，需要一个额外的字典来保存列表中的不同types和一个types的控股variables（notImpl）是需要的。 还有一点要注意的是，浮动和整数不是在这里混合的。

输出：

 ================================================================================ 05.04.2017 18:27:57 ~/Desktop/sorter.py -------------------------------------------------------------------------------- [0j, 3j, 0j] <class 'complex'> <class 'complex'> <class 'complex'> ['one', 'four', 'aa', 'zz'] <class 'str'> <class 'str'> <class 'str'> <class 'str'> [2.3, -5.5, 15.3] <class 'float'> <class 'float'> <class 'float'> [-5, 13] <class 'int'> <class 'int'> [0j, 3j, 0j, 'aa', 'four', 'one', 'zz', -5.5, 2.3, 15.3, -5, 13] 

Answer 5

Python 3.2+的一个方法是使用functools.cmp_to_key() 。 有了这个，你可以快速实现一个解决scheme，试图比较这些值，然后再比较types的string表示。 您还可以避免比较无序types时出现的错误，并保留原始情况下的顺序：

 from functools import cmp_to_key def cmp(a,b): try: return (a > b) - (a < b) except TypeError: s1, s2 = type(a).__name__, type(b).__name__ return (s1 > s2) - (s1 < s2) 

示例（从Martijn Pieters的回答中得到的input列表）：

 sorted([0, 'one', 2.3, 'four', -5], key=cmp_to_key(cmp)) # [-5, 0, 2.3, 'four', 'one'] sorted([0, 123.4, 5, -6, 7.89], key=cmp_to_key(cmp)) # [-6, 0, 5, 7.89, 123.4] sorted([{1:2}, {3:4}], key=cmp_to_key(cmp)) # [{1: 2}, {3: 4}] sorted([{1:2}, None, {3:4}], key=cmp_to_key(cmp)) # [None, {1: 2}, {3: 4}] 

这样做的缺点是总是进行三方比较，增加了时间复杂度。 然而，这个解决scheme开销很小，简洁，干净。我认为cmp_to_key()是为这种Python 2仿真用例开发的。

Answer 6

我们可以通过以下方式解决这个问题。

1. 按types分组。
2. 通过尝试比较每种types的单个代表来查找哪些types是可比较的。
3. 合并可比types的组。
4. 如果可能的话，sorting合并的组。
5. （sorting）合并组的收益率

我们可以通过使用repr(type(x))从types中获得确定性和可定制的关键函数。 请注意，这里的“types层次”是由types本身的repr决定的。 这种方法的一个缺陷是，如果两种types具有相同的__repr__ （types本身，而不是实例），则会“混淆”types。 这可以通过使用返回元组(repr(type), id(type))的键函数来解决，但是我没有在这个解决scheme中实现。

我的方法优于Bas Swinkel的方法是对一组不可处理的元素进行更简洁的处理。 我们没有二次行为; 相反，函数在sort（）中第一次尝试sorting后放弃。

在迭代中存在极大数量的不同types的情况下，我的方法function最差。 这是一个罕见的情况，但我想它可能会出现。

 def py2sort(iterable): by_type_repr = lambda x: repr(type(x)) iterable = sorted(iterable, key = by_type_repr) types = {type_: list(group) for type_, group in groupby(iterable, by_type_repr)} def merge_compatible_types(types): representatives = [(type_, items[0]) for (type_, items) in types.items()] def mergable_types(): for i, (type_0, elem_0) in enumerate(representatives, 1): for type_1, elem_1 in representatives[i:]: if _comparable(elem_0, elem_1): yield type_0, type_1 def merge_types(a, b): try: types[a].extend(types[b]) del types[b] except KeyError: pass # already merged for a, b in mergable_types(): merge_types(a, b) return types def gen_from_sorted_comparable_groups(types): for _, items in types.items(): try: items = sorted(items) except TypeError: pass #unorderable type yield from items types = merge_compatible_types(types) return list(gen_from_sorted_comparable_groups(types)) def _comparable(x, y): try: x < y except TypeError: return False else: return True if __name__ == '__main__': print('before py2sort:') test = [2, -11.6, 3, 5.0, (1, '5', 3), (object, object()), complex(2, 3), [list, tuple], Fraction(11, 2), '2', type, str, 'foo', object(), 'bar'] print(test) print('after py2sort:') print(py2sort(test)) 

Answer 7

我想build议开始这样的任务（如模仿另一个系统的行为，非常接近这个任务），详细阐明目标系统。 它应该如何处理不同的angular落情况。 最好的方法之一 – 写一堆testing，以确保正确的行为。 有这样的testing给出：

• 更好地了解哪些元素应该在哪个之前
• 基本文件
• 使系统对某些重构和添加function具有强大的function。 例如，如果增加了一个规则 – 如何确定以前没有被破坏？

可以编写这样的testing用例：

sort2_test.py

 import unittest from sort2 import sorted2 class TestSortNumbers(unittest.TestCase): """ Verifies numbers are get sorted correctly. """ def test_sort_empty(self): self.assertEqual(sorted2([]), []) def test_sort_one_element_int(self): self.assertEqual(sorted2([1]), [1]) def test_sort_one_element_real(self): self.assertEqual(sorted2([1.0]), [1.0]) def test_ints(self): self.assertEqual(sorted2([1, 2]), [1, 2]) def test_ints_reverse(self): self.assertEqual(sorted2([2, 1]), [1, 2]) class TestSortStrings(unittest.TestCase): """ Verifies numbers are get sorted correctly. """ def test_sort_one_element_str(self): self.assertEqual(sorted2(["1.0"]), ["1.0"]) class TestSortIntString(unittest.TestCase): """ Verifies numbers and strings are get sorted correctly. """ def test_string_after_int(self): self.assertEqual(sorted2([1, "1"]), [1, "1"]) self.assertEqual(sorted2([0, "1"]), [0, "1"]) self.assertEqual(sorted2([-1, "1"]), [-1, "1"]) self.assertEqual(sorted2(["1", 1]), [1, "1"]) self.assertEqual(sorted2(["0", 1]), [1, "0"]) self.assertEqual(sorted2(["-1", 1]), [1, "-1"]) class TestSortIntDict(unittest.TestCase): """ Verifies numbers and dict are get sorted correctly. """ def test_string_after_int(self): self.assertEqual(sorted2([1, {1: 2}]), [1, {1: 2}]) self.assertEqual(sorted2([0, {1: 2}]), [0, {1: 2}]) self.assertEqual(sorted2([-1, {1: 2}]), [-1, {1: 2}]) self.assertEqual(sorted2([{1: 2}, 1]), [1, {1: 2}]) self.assertEqual(sorted2([{1: 2}, 1]), [1, {1: 2}]) self.assertEqual(sorted2([{1: 2}, 1]), [1, {1: 2}]) 

下一个可能有这样的sortingfunction：

sort2.py

 from numbers import Real from decimal import Decimal from itertools import tee, filterfalse def sorted2(iterable): """ :param iterable: An iterable (array or alike) entity which elements should be sorted. :return: List with sorted elements. """ def predicate(x): return isinstance(x, (Real, Decimal)) t1, t2 = tee(iterable) numbers = filter(predicate, t1) non_numbers = filterfalse(predicate, t2) sorted_numbers = sorted(numbers) sorted_non_numbers = sorted(non_numbers, key=str) return sorted_numbers + sorted_non_numbers 

用法非常简单，并在testing中logging：

 >>> from sort2 import sorted2 >>> sorted2([1,2,3, "aaa", {3:5}, [1,2,34], {-8:15}]) [1, 2, 3, [1, 2, 34], 'aaa', {-8: 15}, {3: 5}] 

Answer 8

这是完成这个的一个方法：

 lst = [0, 'one', 2.3, 'four', -5] a=[x for x in lst if type(x) == type(1) or type(x) == type(1.1)] b=[y for y in lst if type(y) == type('string')] a.sort() b.sort() c = a+b print(c) 

Answer 9

我尽可能忠实地实现了python 3中的Python 2sorting代码。

像这样使用它： mydata.sort(key=py2key())或mydata.sort(key=py2key(lambda x: mykeyfunc))

 def default_3way_compare(v, w): # Yes, this is how Python 2 sorted things :) tv, tw = type(v), type(w) if tv is tw: return -1 if id(v) < id(w) else (1 if id(v) > id(w) else 0) if v is None: return -1 if w is None: return 1 if isinstance(v, (int, float)): vname = '' else: vname = type(v).__name__ if isinstance(w, (int, float)): wname = '' else: wname = type(w).__name__ if vname < wname: return -1 if vname > wname: return 1 return -1 if id(type(v)) < id(type(w)) else 1 def py2key(func=None): # based on cmp_to_key class K(object): __slots__ = ['obj'] __hash__ = None def __init__(self, obj): self.obj = func(obj) if func else obj def __lt__(self, other): try: return self.obj < other.obj except TypeError: return default_3way_compare(self.obj, other.obj) < 0 def __gt__(self, other): try: return self.obj > other.obj except TypeError: return default_3way_compare(self.obj, other.obj) > 0 def __eq__(self, other): try: return self.obj == other.obj except TypeError: return default_3way_compare(self.obj, other.obj) == 0 def __le__(self, other): try: return self.obj <= other.obj except TypeError: return default_3way_compare(self.obj, other.obj) <= 0 def __ge__(self, other): try: return self.obj >= other.obj except TypeError: return default_3way_compare(self.obj, other.obj) >= 0 return K