Hat Python einen geordneten Satz?

477

Python hat ein geordnetes Wörterbuch . Was ist mit einem bestellten Set?

Casebash
quelle
18
Was ist mit dem Gegenteil, einer Tüte mit Dingen? (ungeordnet und nicht eindeutig)
wim
19
@wim collections.Counterist Pythons Tasche.
Flornbeben
1
Was ist, wenn etwas zweimal hinzugefügt wird? Wie soll die Position sein?
McKay
2
@ McKay - wenn es dem Verhalten von Sammlungen folgen würde. OrderDict wäre es immer noch in der Position der ersten Hinzufügung
wojtow

Antworten:

206

Hierfür gibt es ein geordnetes Set- Rezept (möglicher neuer Link ), auf das in der Python 2-Dokumentation verwiesen wird . Dies läuft auf Py2.6 oder höher und 3.0 oder höher ohne Änderungen. Die Schnittstelle ist fast genau die gleiche wie bei einem normalen Satz, außer dass die Initialisierung mit einer Liste erfolgen sollte.

OrderedSet([1, 2, 3])

Dies ist ein MutableSet, daher stimmt die Signatur für .unionnicht mit der von set überein. Da sie jedoch __or__etwas Ähnliches enthält , kann sie 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
Casebash
quelle
6
Ich habe meine eigene Antwort ausgewählt, weil die Referenz aus der Dokumentation dies einer offiziellen Antwort nahe bringt
Casebash
49
Die Schnittstelle ist nicht genau das gleiche wie das normale Set - Objekt, fehlen viele wichtige Methoden wie update, union, intersection.
xApple
5
FYI, bemerkte ich , dass eine leicht modifizierte Version des in dieser Antwort zitiert Rezepts wurde zu PyPI hinzugefügt als „bestellt-Set“
Geoffrey Hängt
7
Ich bin mir ziemlich sicher, dass Sie nicht zwei Methoden unionin derselben Klasse aufrufen dürfen . Der letzte wird "gewinnen" und der erste wird zur Laufzeit nicht existieren. Dies liegt daran, dass OrderedSet.union(keine Eltern) sich auf ein einzelnes Objekt beziehen müssen .
Kevin
3
Es gibt auch ein "orderset" -Paket, das auf demselben Rezept basiert, aber in Cython implementiert ist - pypi.python.org/pypi/orderedset .
mbdevpl
149

Ein geordneter Satz ist funktional ein Sonderfall eines geordneten Wörterbuchs.

Die Schlüssel eines Wörterbuchs sind eindeutig. Wenn man also die Werte in einem geordneten Wörterbuch ignoriert (z. B. indem man sie zuweist None), hat man im Wesentlichen eine geordnete Menge.

Ab Python 3.1 gibt es collections.OrderedDict. Das Folgende ist eine Beispielimplementierung eines OrderedSet. (Beachten Sie, dass nur wenige Methoden definiert oder überschrieben werden müssen: collections.OrderedDictund collections.MutableSetdas schwere Heben.)

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 = __sub__ 
    difference_update = __isub__
    intersection = __and__
    intersection_update = __iand__
    issubset = __le__
    issuperset = __ge__
    symmetric_difference = __xor__
    symmetric_difference_update = __ixor__
    union = __or__
Stephan202
quelle
1
@Casebash: ja, kann man wünschen , eine Klasse zu definieren , OrderedSetwelche Unterklassen OrderedDictund abc.Setdann definieren __len__, __iter__und __contains__.
Stephan202
1
@ Stephan202: Leider leben die Sammlung ABCs in collections, aber ansonsten ein guter Vorschlag
u0b34a0f6ae
4
Dies ist wahr, aber Sie haben viel Platz verschwendet, was zu einer suboptimalen Leistung führt.
Daniel Kats
3
Eine Ergänzung; Sammlungen.OrderedDict ist auch in Python 2.7 verfügbar.
Nurbldoff
2
Dadurch OrderedSet([1,2,3])wirft eine Typeerror. Wie funktioniert der Konstruktor überhaupt? Fehlendes Anwendungsbeispiel.
xApple
90

Die Antwort lautet Nein, aber Sie können collections.OrderedDictaus der Python-Standardbibliothek nur Schlüssel (und Werte als None) für denselben Zweck verwenden.

Update : Ab Python 3.7 (und CPython 3.6), Standard dictist garantiert , um zu erhalten , und ist leistungsfähiger als OrderedDict. (Aus Gründen der Abwärtskompatibilität und insbesondere der Lesbarkeit möchten Sie diese jedoch möglicherweise weiterhin verwenden OrderedDict.)

Hier ist ein Beispiel für die Verwendung dictals geordneter Satz, um doppelte Elemente herauszufiltern und gleichzeitig die Reihenfolge beizubehalten, wodurch ein geordneter Satz emuliert wird. Verwenden Sie die dictKlassenmethode fromkeys(), um ein Diktat zu erstellen, und fragen Sie dann einfach nach der keys()Rückseite.

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

>>> list(dict.fromkeys(keywords))
['foo', 'bar', 'baz']
jrc
quelle
4
Erwähnenswert ist vielleicht, dass dies auch (schneller) mit Vanille funktioniert dict.fromkeys(). In diesem Fall bleibt die Schlüsselreihenfolge jedoch nur in CPython 3.6+ -Implementierungen erhalten. Dies OrderedDictist eine portablere Lösung, wenn es um die Reihenfolge geht.
Jez
1
funktioniert nicht, wenn die Werte nicht string sind
Anwar Hossain
4
@AnwarHossain keys = (1,2,3,1,2,1) list(OrderedDict.fromkeys(keys).keys())-> [1, 2, 3], Python-3.7. Es klappt.
Raratiru
1
Können wir daraus schließen, dass Set in Python 3.7+ auch die Reihenfolge beibehält?
user474491
2
Im Gegensatz zu @ user474491 dict, setin Python 3.7+ leider nicht beibehalten Ordnung.
cz
39

Ich kann Ihnen eines besser machen als ein OrderedSet: Boltons hat einen reinen Python, 2/3-kompatiblen IndexedSetTyp , der nicht nur ein geordneter Satz ist, sondern auch die Indizierung unterstützt (wie bei Listen).

Importieren Sie einfach pip install boltons(oder kopieren Sie es setutils.pyin Ihre Codebasis) das IndexedSetund:

>>> 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 einzigartig und in Ordnung gehalten. Vollständige Offenlegung: Ich habe das geschrieben IndexedSet, aber das bedeutet auch, dass Sie mich nerven können, wenn es irgendwelche Probleme gibt . :) :)

Mahmoud Hashemi
quelle
39

Implementierungen auf PyPI

Während andere darauf hingewiesen haben, dass es in Python (noch) keine integrierte Implementierung eines Satzes zur Beibehaltung der Einfügereihenfolge gibt, fehlt dieser Frage meines Erachtens eine Antwort, die angibt, was auf PyPI zu finden ist .

Es gibt die Pakete:

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

Einige Unterschiede

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

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

Daniel K.
quelle
2
Ein neuer Anwärter ist collection_extended.setlist . Funktionen wie funktionieren set.unionjedoch nicht, obwohl es erbt collections.abc.Set.
Timdiels
3
OrderedSetunterstützt jetztremove
warvariuc
17

Wenn Sie den geordneten Satz verwenden, um eine sortierte Reihenfolge beizubehalten, sollten Sie eine Implementierung eines sortierten Satzes von PyPI in Betracht ziehen. Das sortedcontainers- Modul bietet zu diesem Zweck ein SortedSet . Einige Vorteile: Pure-Python, C-schnelle Implementierungen, 100% Unit-Test-Abdeckung, stundenlange Stresstests.

Die Installation von PyPI ist mit pip einfach:

pip install sortedcontainers

Beachten Sie, dass Sie, wenn Sie dies nicht können pip install, einfach die Dateien sortedlist.py und sortedset.py aus dem Open-Source-Repository abrufen .

Einmal installiert, können Sie einfach:

from sortedcontainers import SortedSet
help(SortedSet)

Das Sortedcontainer-Modul führt auch einen Leistungsvergleich mit mehreren alternativen Implementierungen durch.

Für den Kommentar zum Python-Bag-Datentyp gibt es alternativ einen SortedList- Datentyp, mit dem ein Bag effizient implementiert werden kann.

GrantJ
quelle
Beachten Sie, dass für die SortedSetKlasse dort Mitglieder vergleichbar und hashbar sein müssen.
Gsnedders
4
@gsnedders Die eingebauten setund frozensetauch Elemente müssen hashbar sein. Die vergleichbare Einschränkung ist die Ergänzung für SortedSet, aber es ist auch eine offensichtliche Einschränkung.
Gotgenes
2
Wie der Name schon sagt, bleibt die Reihenfolge nicht erhalten. Es ist nichts anderes als sortiert (set ([sequence])), was besser macht?
ldmtwo
@ldmtwo Ich bin mir nicht sicher, auf was Sie sich beziehen, aber um ganz klar zu sein, SortedSet als Teil von Sorted Containers behält die sortierte Reihenfolge bei.
GrantJ
2
@GrantJ - Es ist der Unterschied zwischen , ob es hält Einführungs Ordnung oder sortieren Reihenfolge. Die meisten anderen Antworten beziehen sich auf die Einfügereihenfolge. Ich denke, Sie sind sich dessen bereits aufgrund Ihres ersten Satzes bewusst, aber es ist wahrscheinlich das, was ldmtwo sagt.
Justin
8

Falls Sie in Ihrem Code bereits Pandas verwenden, Indexverhält sich das Objekt wie ein geordneter Satz, wie in diesem Artikel gezeigt .

Beispiele aus dem Artikel:

indA = pd.Index([1, 3, 5, 7, 9])
indB = pd.Index([2, 3, 5, 7, 11])

indA & indB  # intersection
indA | indB  # union
indA - indB  # difference
indA ^ indB  # symmetric difference
Berislav Lopac
quelle
Können Sie dieser Antwort ein Beispiel hinzufügen? Links neigen dazu, nach einiger Zeit unterbrochen zu werden.
Alechan
1
Für den Unterschied zwischen Sätzen, den Sie tatsächlich verwenden müssen, indA.difference(indB)führt das Minuszeichen eine Standard-Subtraktion durch
gg349
7

Ein bisschen spät zum Spiel, aber ich habe eine Klasse geschrieben, setlistals Teil davon collections-extendedimplementiert sowohl SequenceundSet

>>> from collections_extended import setlist
>>> sl = setlist('abracadabra')
>>> sl
setlist(('a', 'b', 'r', 'c', 'd'))
>>> sl[3]
'c'
>>> sl[-1]
'd'
>>> 'r' in sl  # testing for inclusion is fast
True
>>> sl.index('d')  # so is finding the index of an element
4
>>> sl.insert(1, 'd')  # inserting an element already in raises a ValueError
ValueError
>>> sl.index('d')
4

GitHub: https://github.com/mlenzen/collections-extended

Dokumentation: http://collections-extended.lenzm.net/en/latest/

PyPI: https://pypi.python.org/pypi/collections-extended

Michael Lenzen
quelle
7

Es gibt keine OrderedSetin der offiziellen Bibliothek. Ich erstelle ein ausführliches Cheatsheet der gesamten Datenstruktur als Referenz.

DataStructure = {
    'Collections': {
        'Map': [
            ('dict', 'OrderDict', 'defaultdict'),
            ('chainmap', 'types.MappingProxyType')
        ],
        'Set': [('set', 'frozenset'), {'multiset': 'collection.Counter'}]
    },
    'Sequence': {
        'Basic': ['list', 'tuple', 'iterator']
    },
    'Algorithm': {
        'Priority': ['heapq', 'queue.PriorityQueue'],
        'Queue': ['queue.Queue', 'multiprocessing.Queue'],
        'Stack': ['collection.deque', 'queue.LifeQueue']
        },
    'text_sequence': ['str', 'byte', 'bytearray']
}
Infinitesimalrechnung
quelle
3

Das ParallelRegression- Paket bietet eine setList () - geordnete Set-Klasse, die methodisch vollständiger ist als die Optionen, die auf dem ActiveState-Rezept basieren. Es unterstützt alle für Listen verfügbaren Methoden und die meisten, wenn nicht alle für Sets verfügbaren Methoden.

RichardB
quelle
2

Wie in anderen Antworten erwähnt, ist das Diktat wie in Python 3.7+ per Definition geordnet. Anstelle von Unterklassen können OrderedDictwir Unterklassen verwenden abc.collections.MutableSetoder typing.MutableSetdie Schlüssel des Diktats verwenden, um unsere Werte zu speichern.

class OrderedSet(typing.MutableSet[T]):
    """A set that preserves insertion order by internally using a dict."""

    def __init__(self, iterable: t.Iterator[T]):
        self._d = dict.fromkeys(iterable)

    def add(self, x: T) -> None:
        self._d[x] = None

    def discard(self, x: T) -> None:
        self._d.pop(x)

    def __contains__(self, x: object) -> bool:
        return self._d.__contains__(x)

    def __len__(self) -> int:
        return self._d.__len__()

    def __iter__(self) -> t.Iterator[T]:
        return self._d.__iter__()

Dann einfach:

x = OrderedSet([1, 2, -1, "bar"])
x.add(0)
assert list(x) == [1, 2, -1, "bar", 0]

Ich habe diesen Code in eine kleine Bibliothek gestellt , damit jeder es einfach pip installkann.

Bustawin
quelle
-4

Für viele Zwecke reicht es aus, einfach sortiert aufzurufen. Zum Beispiel

>>> s = set([0, 1, 2, 99, 4, 40, 3, 20, 24, 100, 60])
>>> sorted(s)
[0, 1, 2, 3, 4, 20, 24, 40, 60, 99, 100]

Wenn Sie dies wiederholt verwenden, entsteht durch das Aufrufen der sortierten Funktion ein Overhead, sodass Sie die resultierende Liste möglicherweise speichern möchten, solange Sie mit dem Ändern des Satzes fertig sind. Wenn Sie eindeutige und sortierte Elemente beibehalten müssen, stimme ich dem Vorschlag zu, OrderedDict aus Sammlungen mit einem beliebigen Wert wie "Keine" zu verwenden.

hwrd
quelle
43
Der Zweck von OrderedSet besteht darin, die Artikel in der Reihenfolge abzurufen, in der sie dem Set hinzugefügt wurden. Ihr Beispiel könnte vielleicht SortedSet heißen ...
Periodic Maintenance
-4

Also hatte ich auch eine kleine Liste, in der ich eindeutig die Möglichkeit hatte, nicht eindeutige Werte einzuführen.

Ich suchte nach einer eindeutigen Liste, stellte dann aber fest, dass das Testen der Existenz des Elements vor dem Hinzufügen einwandfrei funktioniert.

if(not new_element in my_list):
    my_list.append(new_element)

Ich weiß nicht, ob dieser einfache Ansatz Vorbehalte enthält, aber er löst mein Problem.

Loïc N.
quelle
Das Hauptproblem bei diesem Ansatz ist, dass das Hinzufügen von Läufen in O (n) erfolgt. Das heißt, es wird langsamer mit großen Listen. Die in Python integrierten Sets sind sehr gut darin, das Hinzufügen von Elementen zu beschleunigen. Aber für einfache Anwendungsfälle funktioniert es auf jeden Fall!
Draconis