Skip to content

Wie kann ich 2.x-ähnliches Sortierverhalten in Python 3.x erhalten?

Unsere besten Programmierer haben ihre Kaffeevorräte erschöpft und täglich nach der Lösung gesucht, bis Olivia die Entdeckung auf Beanstalk gefunden hat, und jetzt teilen wir sie hier.

Lösung:

Blöde Idee: In einem ersten Durchgang alle verschiedenen Elemente in Gruppen aufteilen, die untereinander vergleichbar sind, die einzelnen Gruppen sortieren und schließlich verketten. Ich gehe davon aus, dass ein Item mit allen Mitgliedern einer Gruppe vergleichbar ist, wenn es mit dem ersten Mitglied einer Gruppe vergleichbar ist. Etwa so (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)

Dies führt zu einer quadratischen Laufzeit in dem armseligen Fall, dass keines der Elemente vergleichbar ist, aber ich schätze, der einzige Weg, dies mit Sicherheit zu wissen, ist, alle möglichen Kombinationen zu überprüfen. Betrachten Sie das quadratische Verhalten als eine verdiente Strafe für jeden, der versucht, eine lange Liste unsortierbarer Elemente wie komplexe Zahlen zu sortieren. In einem häufigeren Fall einer Mischung aus einigen Zeichenketten und einigen ganzen Zahlen sollte die Geschwindigkeit ähnlich der einer normalen Sortierung sein. Schneller Test:

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]

Es scheint sich auch um eine "stabile Sortierung" zu handeln, da die Gruppen in der Reihenfolge gebildet werden, in der die unvergleichbaren Elemente auftauchen.

Diese Antwort zielt darauf ab, die Sortierreihenfolge von Python 2 in Python 3 detailgetreu nachzubilden.

Die eigentliche Python-2-Implementierung ist recht aufwendig, aber object.c's default_3way_compare führt den endgültigen Fallback durch, nachdem die Instanzen die Möglichkeit erhalten haben, normale Vergleichsregeln zu implementieren. Dies geschieht, nachdem einzelnen Typen die Möglichkeit gegeben wurde, zu vergleichen (über die __cmp__ oder __lt__ Häkchen).

Die Implementierung dieser Funktion als reines Python in einem Wrapper, plus die Emulation der Ausnahmen von den Regeln (dict und komplexe Zahlen im Besonderen) gibt uns die gleiche Sortiersemantik wie in Python 2 in 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])

Ich habe die Sortierung von Wörterbüchern, wie sie in Python 2 implementiert ist, in den Wrapper integriert, da dies vom Typ selbst durch eine __cmp__ Hook. Natürlich habe ich auch die Python-2-Sortierung für die Schlüssel und Werte beibehalten.

Ich habe auch ein spezielles Gehäuse für komplexe Zahlen hinzugefügt, da Python 2 eine Ausnahme auslöst, wenn man versucht, nach diesen zu sortieren:

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

Möglicherweise müssen Sie weitere Sonderfälle hinzufügen, wenn Sie das Verhalten von Python 2 genau emulieren wollen.

Wenn Sie komplexe Zahlen sortieren wollen trotzdem muss man sie konsequent in die Gruppe der Nicht-Zahlen einordnen; z.B:

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

Einige Testfälle:

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

Ich verwende hier nicht Python 3, aber vielleicht würde so etwas funktionieren. Testen Sie, ob ein "kleiner als"-Vergleich mit "Wert" eine Ausnahme erzeugt, und tun Sie dann "etwas", um diesen Fall zu behandeln, z. B. die Umwandlung in eine Zeichenkette.

Natürlich bräuchte man immer noch eine spezielle Behandlung, wenn es andere Typen in der Liste gibt, die nicht vom gleichen Typ sind, aber gegenseitig bestellbar sind.

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

Wenn unser Artikel für Sie nützlich war, möchten wir Sie bitten, ihn mit anderen Programmierern zu teilen und uns dabei zu helfen, unsere Inhalte zu verbreiten.



Nutzen Sie unsere Suchmaschine

Suche
Generic filters

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.