Gibt es in Python eine geordnete Menge?

Question

Python hat eine geordnetes Wörterbuch . Wie wäre es mit einem geordneten Satz?

Answer 1

Die Antwort ist nein, aber Sie können die collections.OrderedDict aus der Python-Standardbibliothek nur mit Schlüsseln (und Werten als None ) für den gleichen Zweck.

Update : Ab Python 3.7 (und CPython 3.6) ist die Standard dict es garantiert die Aufrechterhaltung der Ordnung und ist leistungsfähiger als OrderedDict . (Aus Gründen der Abwärtskompatibilität und vor allem der Lesbarkeit sollten Sie jedoch weiterhin die OrderedDict .)

Hier ist ein Beispiel für die Verwendung dict als geordnete Menge, um doppelte Elemente herauszufiltern und dabei die Reihenfolge beizubehalten und so eine geordnete Menge zu emulieren. Verwenden Sie die dict Klassenmethode fromkeys() um ein Diktat zu erstellen, dann fragen Sie einfach nach dem keys() zurück.

>>> keywords = ['foo', 'bar', 'bar', 'foo', 'baz', 'foo']

>>> list(dict.fromkeys(keywords))
['foo', 'bar', 'baz']

Answer 2

Es gibt eine Bestellmenge (möglich neue Verbindung ) Rezept dafür, auf das in der Python 2 Dokumentation . Dies läuft auf Py2.6 oder höher und 3.0 oder höher ohne irgendwelche Änderungen. Die Schnittstelle ist fast genau die gleiche wie bei einem normalen Set, außer dass die Initialisierung mit einer Liste erfolgen sollte.

OrderedSet([1, 2, 3])

Dies ist ein MutableSet, so dass die Signatur für .union nicht mit dem von set übereinstimmt, aber da es auch __or__ kann etwas Ähnliches leicht hinzugefügt werden:

@staticmethod
def union(*sets):
    union = OrderedSet()
    union.union(*sets)
    return union

def union(self, *sets):
    for set in sets:
        self |= set

Answer 3

Update : Diese Antwort ist ab Python 3.7 veraltet. Siehe jrc's Antwort oben für eine bessere Lösung. Ich werde diese Antwort hier nur aus historischen Gründen aufbewahren.

---

Eine geordnete Menge ist funktionell ein Spezialfall eines geordneten Wörterbuchs.

Die Schlüssel eines Wörterbuchs sind eindeutig. Wenn man also die Werte in einem geordneten Wörterbuch außer Acht lässt (z. B. durch Zuweisung von None ), dann hat man im Wesentlichen eine geordnete Menge.

Ab Python 3.1 y 2.7 Es gibt collections.OrderedDict . Es folgt ein Beispiel für die Implementierung eines OrderedSet. (Beachten Sie, dass nur wenige Methoden definiert oder überschrieben werden müssen: collections.OrderedDict y collections.MutableSet die Schwerstarbeit leisten).

import collections

class OrderedSet(collections.OrderedDict, collections.MutableSet):

    def update(self, *args, **kwargs):
        if kwargs:
            raise TypeError("update() takes no keyword arguments")

        for s in args:
            for e in s:
                 self.add(e)

    def add(self, elem):
        self[elem] = None

    def discard(self, elem):
        self.pop(elem, None)

    def __le__(self, other):
        return all(e in other for e in self)

    def __lt__(self, other):
        return self <= other and self != other

    def __ge__(self, other):
        return all(e in self for e in other)

    def __gt__(self, other):
        return self >= other and self != other

    def __repr__(self):
        return 'OrderedSet([%s])' % (', '.join(map(repr, self.keys())))

    def __str__(self):
        return '{%s}' % (', '.join(map(repr, self.keys())))

    difference = property(lambda self: self.__sub__)
    difference_update = property(lambda self: self.__isub__)
    intersection = property(lambda self: self.__and__)
    intersection_update = property(lambda self: self.__iand__)
    issubset = property(lambda self: self.__le__)
    issuperset = property(lambda self: self.__ge__)
    symmetric_difference = property(lambda self: self.__xor__)
    symmetric_difference_update = property(lambda self: self.__ixor__)
    union = property(lambda self: self.__or__)

Answer 4

Implementierungen auf PyPI

Während andere darauf hingewiesen haben, dass es (noch) keine eingebaute Implementierung einer einfügeordnungserhaltenden Menge in Python gibt, habe ich das Gefühl, dass dieser Frage eine Antwort fehlt, die angibt, was es auf PyPI .

Es gibt die Pakete:

• Bestellmenge (Python-basiert)
• Bestellset (Cython-basiert)
• Sammlungen-erweitert
• Boltons (unter iterutils.IndexedSet , Python-basiert)
• oset (zuletzt aktualisiert im Jahr 2012)

Einige dieser Implementierungen basieren auf dem Rezept von Raymond Hettinger an ActiveState gesendet was auch in anderen Antworten hier erwähnt wird.

Einige Unterschiede

• geordneter Satz (Version 1.1)
• Vorteil: O(1) für Suchvorgänge nach Index (z. B. my_set[5] )
• oset (Version 0.1.3)
• Vorteil: O(1) für remove(item)
• Nachteil: Offensichtlich O(n) für Suchvorgänge nach Index

Beide Implementierungen haben O(1) für add(item) y __contains__(item) ( item in my_set ).

Answer 5

Ich kann Ihnen etwas Besseres bieten als ein OrderedSet: boltons hat ein reines Python, 2/3-kompatibel IndexedSet Typ die nicht nur eine geordnete Menge ist, sondern auch die Indexierung (wie bei Listen) unterstützt.

Einfach pip install boltons (oder Kopie setutils.py in Ihre Codebasis), importieren Sie die IndexedSet und:

>>> from boltons.setutils import IndexedSet
>>> x = IndexedSet(list(range(4)) + list(range(8)))
>>> x
IndexedSet([0, 1, 2, 3, 4, 5, 6, 7])
>>> x - set(range(2))
IndexedSet([2, 3, 4, 5, 6, 7])
>>> x[-1]
7
>>> fcr = IndexedSet('freecreditreport.com')
>>> ''.join(fcr[:fcr.index('.')])
'frecditpo'

Alles ist einmalig und bleibt in Ordnung. Vollständige Offenlegung: Ich habe die IndexedSet aber das bedeutet auch Sie können mich nerven, wenn es irgendwelche Probleme gibt . :)