Re: [Python-de] Liste uniquify
Mike Müller wrote:
Die Lösung mit einem Set ist aber wesentlich performanter und meiner Meinung nach auch leichter zu verstehen. In Python sind die eleganten Lösungen auch bei der Performance oft (nicht immer) die besseren. Ich denke die Set-Lösung ist der bevorzugte Weg in Python für dieses Problem.
Sehe ich auch so. Weshalb aber reproduzierbar $ python Python 2.6.7 (r267:88850, Jul 10 2011, 09:55:27) [GCC 4.6.1] on linux2 Type "help", "copyright", "credits" or "license" for more information.
list(set(["a", "a", "b", "e", "c", "g", "d", "g"])) ['a', 'c', 'b', 'e', 'd', 'g']
und _nicht_ wie vom OP gewünscht (und erwartet) ['a', 'b', 'e', 'c', 'g', 'd']? Auch mit li = ["a", "a", "b", "e", "c", "g", "d", "g"] s = set() for item in li: s.add(item) print s print list(s) erhalte ich reproduzierbar das erste Ergebnis, obwohl über die Liste wie 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? -- PointedEars Please do not Cc: me. / Bitte keine Kopien per E-Mail.
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 läßt eine hashbasierte Implementation vermuten. Vinzent. -- f u cn rd ths, u cn gt a gd jb n cmptr prgrmmng.
Am 19.11.2011 21:36, schrieb Thomas 'PointedEars' Lahn:
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?
Das Ordnungsprinzip: "ungeordnet". Sprich: Selbst wenn Du ein "Ordungsprinzip" ausgemacht zu haben meinst, darfst Du Dich nicht darauf verlassen. Es ist implementationsabhängig und kann sich jederzeit ändern. -- Schönen Gruß - Regards Hartmut Goebel Dipl.-Informatiker (univ.), CISSP, CSSLP Goebel Consult Spezialist für IT-Sicherheit in komplexen Umgebungen http://www.goebel-consult.de Monatliche Kolumne: http://www.cissp-gefluester.de/ Goebel Consult ist Mitglied bei http://www.7-it.de
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
erhalte ich reproduzierbar das erste Ergebnis, obwohl über die Liste wie 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?
Wie Vinzent vermutet: Sets basieren auf einer Hashtabelle. Bei der gegebenen Zahl von Elementen wird die Hashtabelle 16 Einträge erlauben; damit ergibt sich als Reihenfolge py> sorted((hash(x)%16,x) for x in ["a", "b", "e", "c", "g", "d"]) [(0, 'a'), (2, 'c'), (3, 'b'), (4, 'e'), (5, 'd'), (6, 'g')] Ciao, Martin
participants (5)
-
Hartmut Goebel -
Martin v. Loewis -
Stefan Behnel -
Thomas 'PointedEars' Lahn -
Vinzent Hoefler