Как сортировать последовательности смешанного типа (например, с числами и строками) в python3.x? [Дубликат]

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

#! /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 и int не смешиваются здесь.

Выход:

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

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

Итак, присоединившись к нему с оригинальным ответом Martijn:

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: У него больше смысла создавать его в качестве комментария, но у меня не было достаточной репутации, чтобы сделать комментарий. Поэтому я создаю это как ответ.

Вот один из способов достижения этого:

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)

Я попытался как можно точнее реализовать код C ++ для сортировки 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

Один из способов для 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 ):

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.

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

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

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

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

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

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

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

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

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

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

Не работает 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']