Das Konvertieren einer Liste in eine Menge ändert die Elementreihenfolge

119

Kürzlich habe ich festgestellt, dass beim Konvertieren von a listin setdie Reihenfolge der Elemente geändert und nach Zeichen sortiert wird.

Betrachten Sie dieses Beispiel:

x=[1,2,20,6,210]
print x 
# [1, 2, 20, 6, 210] # the order is same as initial order

set(x)
# set([1, 2, 20, 210, 6]) # in the set(x) output order is sorted

Meine Fragen sind -

  1. Warum passiert dies?
  2. Wie kann ich Set-Operationen (insbesondere Set Difference) ausführen, ohne die ursprüngliche Reihenfolge zu verlieren?
d.putto
quelle
8
Warum möchten Sie die ursprüngliche Bestellung nicht verlieren, insbesondere wenn Sie festgelegte Operationen ausführen? "Ordnung" ist ein bedeutungsloses Konzept für Mengen, nicht nur in Python, sondern auch in der Mathematik.
Karl Knechtel
129
@ KarlKnechtel - Ja "Ordnung ist ein bedeutungsloses Konzept für Mengen ... in der Mathematik", aber ich habe Probleme in der realen Welt :)
d.putto
Auf CPython 3.6+ unique = list(dict.fromkeys([1, 2, 1]).keys()). Dies funktioniert, weil dictdie Einfügereihenfolge jetzt beibehalten wird.
Boris

Antworten:

105
  1. A setist eine ungeordnete Datenstruktur, sodass die Einfügereihenfolge nicht beibehalten wird.

  2. Dies hängt von Ihren Anforderungen ab. Wenn Sie eine normale Liste haben und einige Elemente entfernen möchten, während die Reihenfolge der Liste beibehalten wird, können Sie dies mit einem Listenverständnis tun:

    >>> a = [1, 2, 20, 6, 210]
    >>> b = set([6, 20, 1])
    >>> [x for x in a if x not in b]
    [2, 210]

    Wenn Sie eine Datenstruktur benötigen, die sowohl schnelle Mitgliedschaftstests als auch die Beibehaltung der Einfügereihenfolge unterstützt , können Sie die Schlüssel eines Python-Wörterbuchs verwenden, das ab Python 3.7 garantiert die Einfügereihenfolge beibehält:

    >>> a = dict.fromkeys([1, 2, 20, 6, 210])
    >>> b = dict.fromkeys([6, 20, 1])
    >>> dict.fromkeys(x for x in a if x not in b)
    {2: None, 210: None}

    bmuss hier nicht wirklich bestellt werden - Sie können auch eine verwenden set. Beachten Sie, dass a.keys() - b.keys()die eingestellte Differenz als zurückgegeben wird set, sodass die Einfügereihenfolge nicht beibehalten wird.

    In älteren Versionen von Python können Sie collections.OrderedDictstattdessen Folgendes verwenden:

    >>> a = collections.OrderedDict.fromkeys([1, 2, 20, 6, 210])
    >>> b = collections.OrderedDict.fromkeys([6, 20, 1])
    >>> collections.OrderedDict.fromkeys(x for x in a if x not in b)
    OrderedDict([(2, None), (210, None)])
Sven Marnach
quelle
3
Kein Objekt kostet 16 Bytes. Wenn es nur ein Standard-OrderedSet () gibt. :(
Sean
2
@ Sean nein, das tun sie nicht. Noneist eine Sprache garantiert Singleton. In CPython sind die tatsächlichen Kosten nur der Zeiger (obwohl diese Kosten immer vorhanden sind, aber für ein Diktat können Sie fast Noneandere Singletons oder gemeinsame Referenzen als "kostenlos" betrachten), also ein Maschinenwort, wahrscheinlich 8 Bytes auf modernen Computern . Aber ja, es ist nicht so platzsparend wie ein Set sein könnte.
juanpa.arrivillaga
2
Auf CPython 3.6+ können Sie dies nur tun, dict.fromkeys([1, 2, 1]).keys()weil reguläre dicts auch die Reihenfolge beibehalten.
Boris
@Boris Dies war nur ein Teil der Sprachspezifikation ab Python 3.7. Während die CPython-Implementierung bereits in Version 3.6 die Einfügereihenfolge beibehält, wird dies als Implementierungsdetail betrachtet, auf das andere Python-Implementierungen möglicherweise nicht folgen.
Sven Marnach
@Sven Ich sagte CPython. Ich poste dies überall, ich habe es einfach satt, "CPython 3.6 oder eine andere Implementierung ab Python 3.7" zu schreiben. Es ist nicht einmal wichtig, jeder benutzt CPython
Boris
52

In Python 3.6, set()jetzt sollte die Reihenfolge halten, aber es gibt eine andere Lösung für Python 2 und 3:

>>> x = [1, 2, 20, 6, 210]
>>> sorted(set(x), key=x.index)
[1, 2, 20, 6, 210]
Tiger-222
quelle
8
Zwei Hinweise zur Auftragserhaltung: Nur ab Python 3.6, und selbst dort wird es als Implementierungsdetail betrachtet. Verlassen Sie sich also nicht darauf. Abgesehen davon ist Ihr Code sehr ineffizient, da bei jedem x.indexAufruf eine lineare Suche durchgeführt wird. Wenn Sie mit quadratischer Komplexität zufrieden sind, gibt es überhaupt keinen Grund, a zu verwenden set.
Thijs van Dien
27
@ThijsvanDien Dies ist falsch, set()ist nicht in Python 3.6 bestellt, auch nicht als Implementierungsdetail, Sie denken an dicts
Chris_Rands
8
@ThijsvanDien Nein, sie sind nicht sortiert, obwohl sie manchmal so erscheinen, weil sie sich intoft selbst stapeln. Stackoverflow.com/questions/45581901/…
Chris_Rands
3
Versuchen Sie x=[1,2,-1,20,6,210], es zu einem Set zu machen. Sie werden sehen, dass es überhaupt nicht bestellt ist und in Python 3.6 getestet wurde.
GabrielChu
3
Ich kann nicht verstehen, warum diese Antwort so viele positive Stimmen hat, dass sie weder die Einfügereihenfolge beibehält noch einen Satz zurückgibt.
Igor Rodriguez
20

Bei der Beantwortung Ihrer ersten Frage handelt es sich bei einem Satz um eine Datenstruktur, die für Satzoperationen optimiert ist. Wie eine mathematische Menge erzwingt oder behält sie keine bestimmte Reihenfolge der Elemente bei. Das abstrakte Konzept einer Menge erzwingt keine Reihenfolge, daher ist die Implementierung nicht erforderlich. Wenn Sie einen Satz aus einer Liste erstellen, kann Python die Reihenfolge der Elemente an die Anforderungen der internen Implementierung anpassen, die für einen Satz verwendet wird, der Satzoperationen effizient ausführen kann.

lvella
quelle
9

Entfernen Sie Duplikate und behalten Sie die Reihenfolge durch die unten stehende Funktion bei

def unique(sequence):
    seen = set()
    return [x for x in sequence if not (x in seen or seen.add(x))]

Überprüfen Sie diesen Link

Sana
quelle
Schön, viel besser als meine Lösung :)
Tiger-222
8

In der Mathematik gibt es Mengen und geordnete Mengen (Osets).

  • set : ein ungeordneter Container mit eindeutigen Elementen (implementiert)
  • oset : ein geordneter Container mit eindeutigen Elementen (NotImplemented)

In Python werden nur Mengen direkt implementiert. Wir können Osets mit regulären Diktiertasten ( 3.7+ ) emulieren .

Gegeben

a = [1, 2, 20, 6, 210, 2, 1]
b = {2, 6}

Code

oset = dict.fromkeys(a).keys()
# dict_keys([1, 2, 20, 6, 210])

Demo

Replikate werden entfernt, die Einfügereihenfolge bleibt erhalten.

list(oset)
# [1, 2, 20, 6, 210]

Set-ähnliche Operationen an Diktiertasten.

oset - b
# {1, 20, 210}

oset | b
# {1, 2, 5, 6, 20, 210}

oset & b
# {2, 6}

oset ^ b
# {1, 5, 20, 210}

Einzelheiten

Hinweis: Eine ungeordnete Struktur schließt geordnete Elemente nicht aus. Vielmehr ist eine aufrechterhaltene Bestellung nicht garantiert. Beispiel:

assert {1, 2, 3} == {2, 3, 1}                    # sets (order is ignored)

assert [1, 2, 3] != [2, 3, 1]                    # lists (order is guaranteed)

Man kann erfreut sein zu entdecken, dass eine Liste und ein Multiset (mset) zwei weitere faszinierende mathematische Datenstrukturen sind:

  • Liste : Ein geordneter Container mit Elementen, der Replikate zulässt (implementiert)
  • mset : Ein ungeordneter Container mit Elementen, der Replikate zulässt (NotImplemented) *

Zusammenfassung

Container | Ordered | Unique | Implemented
----------|---------|--------|------------
set       |    n    |    y   |     y
oset      |    y    |    y   |     n
list      |    y    |    n   |     y
mset      |    n    |    n   |     n*  

* Ein Multiset kann indirekt mit collections.Counter()einer diktartigen Abbildung von Multiplizitäten (Zählungen) emuliert werden .

Pylang
quelle
4

Wie in anderen Antworten angegeben, sind Mengen Datenstrukturen (und mathematische Konzepte), die die Elementreihenfolge nicht beibehalten -

Durch die Verwendung einer Kombination aus Sätzen und Wörterbüchern ist es jedoch möglich, dass Sie das erreichen, was Sie möchten - versuchen Sie es mit folgenden Ausschnitten:

# save the element order in a dict:
x_dict = dict(x,y for y, x in enumerate(my_list) )
x_set = set(my_list)
#perform desired set operations
...
#retrieve ordered list from the set:
new_list = [None] * len(new_set)
for element in new_set:
   new_list[x_dict[element]] = element
jsbueno
quelle
1

Aufbauend auf Svens Antwort fand ich die Verwendung von Sammlungen. OrderedDict hat mir so geholfen, das zu erreichen, was Sie wollen, und ich kann dem Diktat weitere Elemente hinzufügen:

import collections

x=[1,2,20,6,210]
z=collections.OrderedDict.fromkeys(x)
z
OrderedDict([(1, None), (2, None), (20, None), (6, None), (210, None)])

Wenn Sie Elemente hinzufügen möchten, diese aber dennoch wie ein Set behandeln möchten, können Sie Folgendes tun:

z['nextitem']=None

Und Sie können eine Operation wie z.keys () für das Diktat ausführen und das Set erhalten:

z.keys()
[1, 2, 20, 6, 210]
Jimh
quelle
Sie müssen tun list(z.keys()), um die Listenausgabe zu erhalten.
jxn
in Python 3 ja. nicht in Python 2, obwohl ich hätte angeben sollen.
Jimh
0

Eine Implementierung des oben genannten Konzepts mit der höchsten Punktzahl bringt es zurück zu einer Liste:

def SetOfListInOrder(incominglist):
    from collections import OrderedDict
    outtemp = OrderedDict()
    for item in incominglist:
        outtemp[item] = None
    return(list(outtemp))

Getestet (kurz) auf Python 3.6 und Python 2.7.

Mike Stucka
quelle
0

Wenn Ihre beiden Anfangslisten eine kleine Anzahl von Elementen enthalten, für die Sie eine Differenzoperation festlegen möchten, anstatt collections.OrderedDictdie Implementierung zu verwenden, die die Implementierung kompliziert und weniger lesbar macht, können Sie Folgendes verwenden:

# initial lists on which you want to do set difference
>>> nums = [1,2,2,3,3,4,4,5]
>>> evens = [2,4,4,6]
>>> evens_set = set(evens)
>>> result = []
>>> for n in nums:
...   if not n in evens_set and not n in result:
...     result.append(n)
... 
>>> result
[1, 3, 5]

Die zeitliche Komplexität ist nicht so gut, aber ordentlich und leicht zu lesen.

Ultrablendz
quelle
0

Es ist interessant, dass die Leute immer das Problem der realen Welt benutzen, um Witze über die Definition in der theoretischen Wissenschaft zu machen.

Wenn set die Reihenfolge hat, müssen Sie zuerst die folgenden Probleme herausfinden. Wenn Ihre Liste doppelte Elemente enthält, wie sollte die Reihenfolge sein, wenn Sie sie in ein Set verwandeln? Was ist die Reihenfolge, wenn wir zwei Mengen vereinen? Wie ist die Reihenfolge, wenn wir zwei Mengen mit unterschiedlicher Reihenfolge auf denselben Elementen schneiden?

Außerdem ist set bei der Suche nach einem bestimmten Schlüssel viel schneller, was bei der Set-Operation sehr gut ist (und deshalb benötigen Sie ein Set, aber keine Liste).

Wenn Sie sich wirklich für den Index interessieren, behalten Sie ihn einfach als Liste bei. Wenn Sie dennoch die Set-Operation für die Elemente in vielen Listen ausführen möchten, erstellen Sie am einfachsten ein Wörterbuch für jede Liste mit denselben Schlüsseln im Set sowie einen Listenwert, der den gesamten Index des Schlüssels in der ursprünglichen Liste enthält.

def indx_dic(l):
    dic = {}
    for i in range(len(l)):
        if l[i] in dic:
            dic.get(l[i]).append(i)
        else:
            dic[l[i]] = [i]
    return(dic)

a = [1,2,3,4,5,1,3,2]
set_a  = set(a)
dic_a = indx_dic(a)

print(dic_a)
# {1: [0, 5], 2: [1, 7], 3: [2, 6], 4: [3], 5: [4]}
print(set_a)
# {1, 2, 3, 4, 5}
Po-Yao Niu
quelle
-8

Hier ist eine einfache Möglichkeit, dies zu tun:

x=[1,2,20,6,210]
print sorted(set(x))
Aappu Shankar
quelle
3
Dadurch bleibt die Bestellung nicht unbedingt erhalten.
David Boshton