list comprehension über set instabil

[psharper]

Hallo, das Verhalten des folgenden Kodes finde ich merkwürdig.

Code: Alles auswählen

import datetime
from icecream import ic

def why_unstable():
    li = [datetime.datetime(2020, 1, 1, 12, 0),
          datetime.datetime(2021, 1, 1, 12, 0),
          datetime.datetime(2022, 1, 1, 12, 0)]
    ic(li)
    for i in range(3):
        s=set(li)
        ic(s)
        li_c=[x for x in s]
        ic(li_c)

if __name__ == '__main__':
    why_unstable()
    exit()

Ich würde erwarten, dass li_c in der Reihenfolge des sets s gebildet wird. Tatsächlich aber, wird es zufällig und abhängig von der aktuellen Python-Interpreter Instanz gebildet.

Also mehrfaches ausführen des .py führt zu anderen Reihenfolgen in li_c, während innerhalb einer Ausführung immer die gleiche Reihenfolge besteht, wie diese Ausgabe zeigt.

Code: Alles auswählen

ic| li: [datetime.datetime(2020, 1, 1, 12, 0),
         datetime.datetime(2021, 1, 1, 12, 0),
         datetime.datetime(2022, 1, 1, 12, 0)]
ic| s: {datetime.datetime(2020, 1, 1, 12, 0),
        datetime.datetime(2021, 1, 1, 12, 0),
        datetime.datetime(2022, 1, 1, 12, 0)}
ic| li_c: [datetime.datetime(2020, 1, 1, 12, 0),
           datetime.datetime(2022, 1, 1, 12, 0),
           datetime.datetime(2021, 1, 1, 12, 0)]
ic| s: {datetime.datetime(2020, 1, 1, 12, 0),
        datetime.datetime(2021, 1, 1, 12, 0),
        datetime.datetime(2022, 1, 1, 12, 0)}
ic| li_c: [datetime.datetime(2020, 1, 1, 12, 0),
           datetime.datetime(2022, 1, 1, 12, 0),
           datetime.datetime(2021, 1, 1, 12, 0)]
ic| s: {datetime.datetime(2020, 1, 1, 12, 0),
        datetime.datetime(2021, 1, 1, 12, 0),
        datetime.datetime(2022, 1, 1, 12, 0)}
ic| li_c: [datetime.datetime(2020, 1, 1, 12, 0),
           datetime.datetime(2022, 1, 1, 12, 0),
           datetime.datetime(2021, 1, 1, 12, 0)]

Andere Python-Interpreter Instanz, selber Kode

Code: Alles auswählen

ic| s: {datetime.datetime(2020, 1, 1, 12, 0),
        datetime.datetime(2021, 1, 1, 12, 0),
        datetime.datetime(2022, 1, 1, 12, 0)}
ic| li_c: [datetime.datetime(2021, 1, 1, 12, 0),
           datetime.datetime(2020, 1, 1, 12, 0),
           datetime.datetime(2022, 1, 1, 12, 0)]

Anm..: Verwendet man anstelle von datetime einen einfachen Datentyp z.B. int bleibt es stabil. Allerdings kann ich da keinen Zusammenhang sehen.

Getestet gegen 3.9.2 / 3.10.12 Linux und 3.10.4 Windows.

Frage: Würdet ihr dieses Verhalten erwarten und wenn ja, wieso?

[narpfel]

Ich würde das so erwarten. Wieso? Darum:

A set object is an unordered collection of distinct hashable objects.

Die Elemente in einem `set` haben keine Reihenfolge.

[bords0]

Ich würde das so erwarten. Wieso? Darum:

A set object is an unordered collection of distinct hashable objects.

Die Elemente in einem `set` haben keine Reihenfolge.

@narpfel
Ich würde das nicht erwarten. Ich würde erwarten, dass das `set` bei jedem Programmaufruf eine andere Reihenfolge hat (haben kann). Es wird jedoch immer die gleiche Reihenfolge angezeigt. Wenn es keine Reihenfolge gibt, würde man doch auch eine nicht stabile Reihenfolge erwarten.

Bei einem `set` ist die Iterationsreihenfolge normalerweise stabil, solange es nicht geändert wird. Das mag von der Python-Implementation abhängen, aber bei CPython ist das normalerweise so (und es würde mich sehr wundern, wenn es irgendwo anders wäre, aber es gibt so manches, das man nicht erwartet - also ich würde mich freuen, wenn jemand eine Python-Implementation nennt, wo das nicht so ist). Und man sieht es ja auch an der Ausgabe: `li_c` ist immer gleich (während eines Programmlaufs).

Deshalb erwarte ich eigentlich, dass `s` und `li_c` die Elemente in der gleichen (Iterations-)Reihenfolge haben.

@psharper
Ich vermute, dass das pretty-printing von icecream hier dazwischenfunkt und `s` in sortierter Reihenfolge ausgibt. Einfach mal mit `print` statt `ic` versuchen. Ohne die zusätzliche verschleiernde icecream-Schicht kannst du vielleicht besser erkennen, was los ist.

[Sirius3]

@bords0: es macht halt einen Unterschied, ob eine bestimmte Reihenfolge durch die Sprache garantiert wird, oder ob das komplett zufällig ist, was auch nicht garantiert wird. Von daher ist die Aussage, "die Elemente in einem `set` haben keine (garantierte) Reihenfolge.` schon richtig.

@psharper: Eine häufige Methode, wie Sets implementiert werden, ist, dass für jedes Element ein sogenannter Hash-Wert berechnet wird und anhand des Hash-Wertes Elemente im Set "sortiert" sind, um Elemente schnell wieder zu finden. Für kleine Zahlen ist der Hashwert gleich der Zahl selbst, so dass Zahlen sortiert erscheinen. Für alle anderen Hash-Werte wird eine pro Programmlauf konstante Zufallszahl eingewoben, um sogenanntes Hash-Poisoning zu unterbinden, eine Methode, bei der ein Angreifer einen Rechner verlangsamt, indem Werte erzeugt werden, die alle den selben Hash-Wert haben, und Zugriffe auf ein Set von ~ O(1) auf ~O(n^2) verlangsamt werden.

[noisefloor]

Hallo,

das sind letztendlich alles empirische Beobachtung.

Was die Python-Doku sagt ist, dass ein Set "unordered" ist. Oder anders: es gibt keine _garantierte_ Reihenfolge. Was halt nicht ausschließt, dass in 99,9% der Fälle die Reihenfolge unverändert ist oder das das erst ab einer bestimmte Länge eines Sets so ist oder so. Wenn dich die low-level Details interessieren -> Python Quellcode konsultieren.

Für dich als Programmierer heißt das aber auch: wenn du dich auf eine Reihenfolge verlässt hast du einen potentiellen Fehler in deinem Programm.

Gruß, noisefloor

[bords0]

@bords0: es macht halt einen Unterschied, ob eine bestimmte Reihenfolge durch die Sprache garantiert wird, oder ob das komplett zufällig ist, was auch nicht garantiert wird. Von daher ist die Aussage, "die Elemente in einem `set` haben keine (garantierte) Reihenfolge.` schon richtig.

Ja, natürlich. Nur hilft das nicht so viel, die gezeigte Ausgabe bzw. die Frage von @psharper zu erklären. Es gibt hier glaube ich einige Missverständnisse, die ich mal versuche aufzudröseln.

1. Keine garantierte Reihenfolge bei `set`: Ja, das ist richtig. Hat niemand bestritten.
2. Die Reihenfolge bei mehreren Programmläufen ist nicht stabil. Auch da sind sich alle einig, denke ich.
3. Die Ausgabe von @psharper zeigt die Elemente von `set` immer in der gleichen Reihenfolge, auch bei mehreren Programmläufen. Nach den obigen Punkten hätte ich das nicht erwartet. @narpfel hatte ich so verstanden, dass die stabile Ausgabe seinen Erwartungen entspricht, gerade wegen der nicht garantierten Reihenfolge. Das leuchtet mir nicht ein. Ich vermute, dass @narpfel etwas anderes meinte.
4. Python als Sprache gibt keine Garantie, aber die Implementation ist so, dass die Iteration eine stabile Reihenfolge hat (ohne Änderung des `set`). (Das sieht man auch daran, dass `li_c` während eines Programmlaufs immer gleich ist.) Ich glaube, dass wir uns auch hier einig sind. (Ob man sich darauf verlassen sollte, ist eine ganz andere Frage, die aber meistens deshalb irrelevant ist, weil .)

Wie ist also zu erklären, dass `s` und `li_c` verschiedene Reihenfolgen zu haben scheinen (innerhalb eines Programmlaufs)? Wohl nur dadurch, dass `s` nicht in Iterationsreihenfolge ausgegeben wird. Dafür dürfte icecream verantwortlich sein, dessen pretty-printing hier im Weg steht.

Mit `ic = print` sieht man den fraglichen Effekt jedenfalls nicht mehr, `s` wird in verschiedenen Reihenfolgen ausgegeben, aber in der gleichen wie `li_c`.

Damit wir hier nicht über verschiedene Dinge reden, der "fragliche Effekt" von @psharper ist:
Ein `set` und eine in Iterationsreihenfolge erzeugte Liste scheinen unterschiedliche Reihenfolgen der Elemente zu haben (Liste von Programmlauf zu Programmlauf verschieden, Set immer gleich).

[kbr]

Rein pragmatisch sehe ich das so wie @narpfel: ein Set garantiert keine bestimmte Reihenfolge der enthaltenen Elemente. Dies genügt, um in der Praxis mit Sets korrekt umgehen zu können.

Wenn man sich für das "warum" interessiert, kommen die Betrachtungen von @bords0 hinzu. Ich habe dies bislang als Implementationsdetail verstanden, so dass die Reihenfolge der Elemente in einem Set je nach Python Version, des genutzten OS und ggf. auch in unterschiedlichen Prozessen verschieden ausfallen kann. Überprüft hatte ich dies nie. Wenn ich dies nun in Python 3.11 nachstelle (und icecream durch print ersetze), erhalte ich zunächst eine klar definierte Reihenfolge der Elemente in der Liste. Im Set ändert sich diese, in jedem Durchlauf der Schleife aber in stets der gleichen Weise. Die Reihenfolge der Elemente der Liste in der Schleife spiegelt die Iterationsreihenfolge des Sets wider, was der Erwartung von @bords0 entspricht und meiner Erwartung auch. Starte ich den Prozess neu, so kann sich die Reihenfolge im Set ändern, bleibt innerhalb des Prozesses aber stabil. Dies entspricht der Erklärung von @Sirius3.

Die Ausgaben von @psharper kann ich nicht nachvollziehen – jedenfalls nicht mit Python 3.11. Vielleicht verhalten sich frühere Python Versionen anders. Im Sinne der Dokumentation, dass die Elemente in einem Set ungeordnet vorliegen, ist dies aber unerheblich.

[psharper]

War mein eigener Fehler. Ich dachte, wenn ein set iterierbar ist, muss es auch sortierbar sein.

Danke für die rege Beteiligung.

[psharper]

... icecream sortiert die sets bei Ausgabe nicht aber die Listen, so dass ich
zum falschen Umkehrschluss kam, das set würde die Sortierung beibehalten
und die list comprehension wäre instabil.

[DeaD_EyE]

War mein eigener Fehler. Ich dachte, wenn ein set iterierbar ist, muss es auch sortierbar sein.

Danke für die rege Beteiligung.

Es ist sortierbar, aber das Resultat von sorted ist dann wieder eine Liste.

Code: Alles auswählen

import datetime

dates = [datetime.datetime(year, 1, 1) for year in range(2020, 2025)]
dates_set = set(dates)
# Ungeordnet
print("Set")
print("\n".join(map(str, dates_set)))
# Sortierte Liste
print()
print("Sortierte Liste aus set")
dates_list = list(sorted(dates_set))
print("\n".join(map(str, dates_list)))

Code: Alles auswählen

Set
2023-01-01 00:00:00
2022-01-01 00:00:00
2020-01-01 00:00:00
2024-01-01 00:00:00
2021-01-01 00:00:00

Sortierte Liste aus set
2020-01-01 00:00:00
2021-01-01 00:00:00
2022-01-01 00:00:00
2023-01-01 00:00:00
2024-01-01 00:00:00