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

我试图在3.x中复制Python 2.x的sorting行为(如果可能的话还可以改进),以便相互定义的types(如intfloat等)按照预期进行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的问题?

愚蠢的想法:首先把所有不同的项目进行分组,把它们相互比较,然后对各个组进行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”,因为这些组织是按照无与伦比的项目的顺序组成的。

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

实际的Python 2实现是相当object.c的 ,但是object.cdefault_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}] 

不在这里运行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'] 

为了避免使用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] 

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仿真用例开发的。

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

  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)) 

我想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}] 

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

 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) 

我尽可能忠实地实现了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