Как я могу получить 2.x-подобное поведение сортировки в Python 3.x?

Ответ 1

Глупое представление: сделайте первый проход, чтобы разделить все разные элементы в группах, которые можно сравнить друг с другом, сортировать отдельные группы и, наконец, объединить их. Я предполагаю, что элемент сопоставим со всеми членами группы, если он сопоставим с первым членом группы. Что-то вроде этого (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)

Это будет иметь квадратичное время работы в жалком случае, когда ни один из элементов не сопоставим, но, я думаю, единственный способ узнать, что наверняка будет проверять все возможные комбинации. См. Квадратичное поведение как заслуженное наказание для тех, кто пытается сортировать длинный список несортируемых предметов, например, сложных чисел. В более общем случае из сочетания некоторых строк и некоторых целых чисел скорость должна быть похожа на скорость нормальной сортировки. Быстрый тест:

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]

Кажется, что это тоже "стабильный вид", так как группы формируются в том порядке, в котором встречаются несравнимые элементы.

Ответ 2

Этот ответ направлен на то, чтобы точно воссоздать порядок сортировки Python 2 в Python 3 во всех деталях.

Реальная реализация Python 2 довольно object.c, но object.c default_3way_compare делает окончательный откат после того, как экземплярам была предоставлена возможность реализовать нормальные правила сравнения. Это происходит после того, как отдельным типам была предоставлена возможность сравнить (через __cmp__ или __lt__).

Реализация этой функции как чистого Python в оболочке плюс эмуляция исключений из правил (в частности, dict и комплексных чисел) дает нам ту же семантику сортировки Python 2 в Python 3:

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, так как это будет поддерживаться самим типом через __cmp__. Естественно, я придерживался порядка Python 2 для ключей и значений.

Я также добавил специальный регистр для комплексных чисел, так как Python 2 вызывает исключение, когда вы пытаетесь сортировать эти:

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

В любом случае, если вы хотите отсортировать комплексные числа, вам необходимо последовательно поместить их в группу без номеров; например:

# 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__

Некоторые тестовые случаи:

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

Ответ 3

Не работает Python 3 здесь, но, возможно, что-то подобное будет работать. Тест, чтобы увидеть, делает ли "меньше" сравнение "значение", создает исключение, а затем выполняет "что-то", чтобы обрабатывать этот случай, например, преобразовать его в строку.

Конечно, вам понадобится дополнительная обработка, если в вашем списке есть другие типы, которые не являются одним и тем же типом, но взаимно упорядочены.

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']

Ответ 4

Чтобы избежать использования исключений и для решения на основе типа, я придумал следующее:

#! /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)))

Обратите внимание, что необходим дополнительный словарь для хранения различных типов в списке и переменной хранения типа (notImpl). Обратите внимание, что float и ints здесь не смешиваются.

Вывод:

================================================================================
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]

Ответ 5

Один из способов для Python 3.2+ - использовать functools.cmp_to_key(). С помощью этого вы можете быстро реализовать решение, которое пытается сравнить значения, а затем отпадает при сравнении строкового представления типов. Вы также можете избежать возникновения ошибки при сравнении неупорядоченных типов и оставить порядок, как в исходном случае:

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

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

Это имеет тот недостаток, что всегда выполняется трехстороннее сравнение, что увеличивает временную сложность. Тем не менее, решение низкое накладное, короткое, чистое, и я думаю, что cmp_to_key() был разработан для такого типа использования эмуляции Python 2.

Ответ 6

Мы можем решить эту проблему следующим образом.

• Группировать по типу.
• Найдите, какие типы сопоставимы, пытаясь сравнить один представитель каждого типа.
• Объединение групп сопоставимых типов.
• Сортируйте объединенные группы, если это возможно.
• выход из (отсортированных) объединенных групп

Мы можем получить детерминированную и упорядочиваемую ключевую функцию из типов с помощью repr(type(x)). Обратите внимание, что здесь иерархия типов определяется репрезентацией самих типов. Недостатком этого метода является то, что если два типа имеют одинаковые __repr__ (сами типы, а не экземпляры), вы будете "путать" типы. Это можно решить, используя ключевую функцию, которая возвращает кортеж (repr(type), id(type)), но я не реализовал это в этом решении.

Преимущество моего метода над Bas Swinkel - это более удобная обработка группы неуправляемых элементов. У нас нет квадратичного поведения; вместо этого функция отбрасывается после первого попытки упорядочения во время сортировки()).

Мой метод работает хуже всего в сценарии, где в итерабельном имеется очень большое количество разных типов. Это редкий сценарий, но я предполагаю, что он может появиться.

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

Ответ 7

Я бы хотел порекомендовать начать эту задачу (например, имитировать другое поведение системы очень близко к этому) с подробным уточнением целевой системы. Как это должно работать с различными угловыми случаями. Один из лучших способов сделать это - напишите кучу тестов, чтобы обеспечить правильное поведение. Наличие таких тестов дает:

• Лучше понять, какие элементы должны предшествовать,
• Основные документы
• Обеспечивает надежную работу системы с некоторыми функциями рефакторинга и добавления функций. Например, если добавлено еще одно правило - как убедиться, что предыдущие не нарушены?

Можно написать такие тестовые примеры:

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

Далее может быть такая функция сортировки:

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

Использование довольно простое и задокументировано в тестах:

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

Ответ 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)

Ответ 9

Я попытался как можно точнее реализовать код С++ для сортировки Python 2 в python 3.

Используйте его так: 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

Ответ 10

@martijn-pieters Я не знаю, есть ли у списка в python2 также __cmp__ для обработки объектов списка или как он был обработан в python2.

В любом случае, в дополнение к ответу @martijn-pieters я использовал следующий компаратор списка, так что, по крайней мере, он не дает различного отсортированного вывода на основе разного порядка элементов в одном и том же входном наборе.

@per_type_cmp(list) def list_cmp(a, b): for a_item, b_item in zip(a, b): if a_item == b_item: continue return python2_sort_key(a_item) < python2_sort_key(b_item) return len(a) < len(b)

Итак, соединив его с оригинальным ответом Мартина:

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

@per_type_cmp(list)
def list_cmp(a, b):
    for a_item, b_item in zip(a, b):
        if a_item == b_item:
            continue
        return python2_sort_key(a_item) < python2_sort_key(b_item)
    return len(a) < len(b)

PS: имеет больше смысла создавать его как комментарий, но у меня не было достаточно репутации, чтобы комментировать. Итак, вместо этого я создаю это как ответ.