Reihenfolge bei Sets, List Comprehension

[anhu42]

Hallo zusammen,

ich bin gerade dabei ein Tutorial durch zuarbeiten und habe da eine Frage zu "List Comprehension" bzw. der Reihenfolge bei Sets:
Der Quellcode lautet:

print ( { i for i in range(0,10,1) } )
print ( { i*10 for i in range(0,10,1) } )
print ( { i**2 for i in range(0,10,1) } )

Es soll dabei die Zahlen von 0 bis 9 in ein Set ausgegeben werden, dann das 10-fache dieser Zahlen und die Quadrate dieser Zahlen.
Ich weiß genau, dass ich dafür Listen oder etwas anderes verwenden soll. Mir ist aber etwas komisches aufgefallen.
Die Ausgabe lautet:

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
{0, 70, 40, 10, 80, 50, 20, 90, 60, 30}
{0, 1, 64, 4, 36, 9, 16, 49, 81, 25}

Die Zahlen selbst werden "brav" in der Verarbeitungsreihenfolge dargestellt.
Bei dem Zehnfachen ist die Reihenfolge jetzt 0, 7, 4, 1, 8 ,5 2, 9, 6, 3
und bei den Quadratzahlen ist sie 0 ,1, 8, 2, 6, 3, 4, 7, 9, 5
Was auffällig ist, dass diese "Reihenfolge" bei den Quadratzahlen genauso auch im Tutorial gezeigt wird.
Und bei mir ist sowohl unter Linux als auch Windows genauso und zwar auf verschiedenen Rechnern (Intel i5 bzw. AMD-CPU). Bei den Quadratzahlen scheint es eine "universelle" Reihenfolge zu geben. Ich rätsele, was wohl dahintersteckt, habe aber noch keine Idee.
Komisch.
Ich habe jetzt die Frage, warum die Zahlen einfach so "durcheinandergewürfelt" werden. Das macht für mich keinen Sinn. Es irritiert mich, dass die Reihenfolge der Quadratzahlen immer gleich durcheinander ist und dass sich das auch von den "10er-Zahlen" unterscheidet.
Bei den Kubikzahlen ist die Reihenfolge 0, 1, 4, 8, 2, 7, 6, 9, 3, 5; also auch wieder "anders".

Vielleicht ist meine Frage total blöd, aber wenn ich ein Tutorial durcharbeite, möchte ich schon gerne verstehen, was der Rechner im Hintergrund so treibt.

Viele Grüße,
Andreas

[ThomasL]

Wenn man Fragen zu einem Python Datentyp hat, informiert man sich an der Quelle:
https://docs.python.org/3/library/stdty ... -frozenset

Die Antwort zu deinen Fragen sind die Kernaussagen

A set object is an unordered collection of distinct hashable objects.
Being an unordered collection, sets do not record element position or order of insertion.

Eventuell helfen dir diese Links zum besseren Verständnis.

https://www.codesansar.com/python-progr ... python.htm

https://softwareengineering.stackexchan ... python-set

[narpfel]

Der Datentyp `set` ist in Python ungeordnet. Das heißt, dass die Sprache gar keine Garantien für irgendeine Reihenfolge macht (außer dass sich die Reihenfolge nicht ändert, wenn man das `set` nicht verändert).

Alles weitere über die Reihenfolge kann man nicht mehr auf der Ebene der Sprache, sondern nur auf Ebene einer konkreten Implementierung diskutieren. Da muss man sich dann angucken, wie das implementiert ist. Verlassen kann man sich da aber nicht drauf, weil es ja auch andere Implementierungen geben kann, bei denen Sets anders implementiert sind und sich damit anders verhalten.

Generell kann man sagen, dass Sets meist als Hashtabellen implementiert sind. Du hast also (grob erklärt) für ein Set der Länge N eine Liste von M (mit M > N) Objekten, wobei der Index eines Objektes O in der Liste vom Hashwert des Objektes hash(O) abgeleitet wird, meist per Modulo: hash(O) % M. Damit kannst du per hash(O) % M effizient prüfen, ob das Objekt im Set enthalten ist. Wenn an einem Index kein Objekt stehen soll, schreibt man stattdessen einen speziellen Wert für „leer“ in die Liste.

Wenn du über alle Elemente des Sets iterierst (was bei der Ausgabe passiert), werden einfach die leeren Stellen übersprungen und du hast die quasizufällige Reihenfolge.

Unter CPython kommt die Besonderheit hinzu, dass der Hashwert einer natürlichen Zahl k wieder k ist. Damit macht die Modulooperation gar nichts (weil hash(k) % M == k % M == k für alle k < M) und die Reihenfolge bleibt erhalten, wenn man die ersten N natürlichen Zahlen einfügt.

Mit ein bisschen Experimentieren kann man sogar die Größe M der internen Liste für N = 2 herausfinden:

Code: Alles auswählen

>>> for i in range(10):
...     print({1, i})
...
{0, 1}
{1}
{1, 2}
{1, 3}
{1, 4}
{1, 5}
{1, 6}
{1, 7}
{8, 1}
{1, 9}

8 % M < 1, also muss M == 8 sein: Stimmt sogar

[DeaD_EyE]

Falls die Reihenfolge erhalten bleiben soll, aber doppelte Elemente nicht vorkommen dürfen, kann man ein dict verwenden.

Code: Alles auswählen

insertion_order = list(dict.fromkeys(i*10 for i in range(0,10,1)))

Gilt aber nur ab Python 3.6 (End of life: Dezember 2021) und seit 3.7 ist ein Teil der Sprachdefinition.
Davor war die Reihenfolge der keys bei dicts "zufällig".