Vinzent Hoefler, 19.11.2011 21:59:
Thomas 'PointedEars' Lahn wrote:
erwartet vom Anfang zum Ende (v. l. n. r.) iteriert wird. Ein Set wird in der Dokumentation als eine ungeordnete Sammlung von einzigartigen Elementen ("an unordered collection of unique elements") definiert, bloss liegt dieser anscheinend doch ein Ordnungsprinzip zugrunde. Welches?
Die O(1)-Komplexität
Vorsicht mit "O(1)". Bei Hashing ist es nur im "Normalfall" ein O(1). Im Falle der Auffüllung muss i.A. etwas wesentlich aufwändigeres getan werden, z.B. die Hash-Tabelle vergrößert. Das führt in einzelnen Fällen zu O(N) Verhalten, sei es beim Einfügen oder beim Heraussuchen, je nach Implementierung.
läßt eine hashbasierte Implementation vermuten.
Richtig. Um den Zusammenhang klarer zu machen: Beim Hashing werden die Werte an berechneten (und damit vorhersagbaren) Positionen in ein Array gesteckt. Das Iterieren darüber, das z.B. list() verwendet um die Elemente nacheinander auszulesen, folgt dem Array und liefert damit die Ergebnisse immer in der selben (ebenfalls vorhersagbaren) Reihenfolge. Mit der natürlichen Ordnung der Elemente (z.B. Zeichenketten) hat die meistens wenig zu tun. Ausnahme sind lustigerweise Zahlen in CPython, so dass z.B. list(set(range(1000))) eine sortierte Liste ergibt. Spricht dafür, dass die Hash-Funktion für ganze Zahlen eher einfach gehalten ist... Die genaue Hash-Funktion für einen Datentyp ist aber natürlich implementierungsspezifisch, also nicht drauf verlassen. Stefan