Das deutsche Python-Forum

@Birkenfeld: Kannst du denn mal kurz und knapp (mit C-Kenntnissen als Voraussetzung) erlaeutern, wie sich Tupel und Lists noch so im Speicher unterscheiden, außer eben das die Liste veraenderbar ist und das Tupel nicht?

Also ich stelle mir das ungefaehr so vor:
Ein Tuple entsteht, indem einfach die zusammenaddierte Bytegroesse des Tuple-Inhalts alloziiert und das entstandene Objekt nicht mehr angefasst wird. Eine Liste brauch unmengen an Zusatzfunktionen. Sie muss sich staendig neualloziieren und ihren Inhalt veraendern koennen. Das muss ein Tuple nicht.

Aber aendert das etwas an der Geschwindigkeit? Schließlich ist der Abruf eines einzelnen Objektes innerhalb eines Tuples oder einer Liste doch das gleiche. Mache ich also mit einer Liste das gleiche wie mit einem Tuple, sollte es doch speicher- und geschwindigkeitstechnisch keinen Unterschied machen (außer eben bei der erwaehnten Sache mit der Ueberalloziierung, bei großen Listen)... liege ich da richtig?

@Goswin: Ich glaube nicht das es effizienter ist, ein zusaetzliches Dictionary zu bemuehen. Ein einfaches durchlaufen durch eine Liste um ein Objekt darin zu finden, sollte recht schnell gehen... auch bei hunderttausenden Objekten.
Das Dictionary hingegen wuerde riesengroß werden. Ein unnoetiger Klotz den ein bisschen mehr Prozessorlast ohne weiteres ueberfluessig macht.


Gruß
NKoehring

nkoehring hat geschrieben: Ein einfaches durchlaufen durch eine Liste um ein Objekt darin zu finden, sollte recht schnell gehen... auch bei hunderttausenden Objekten.
Das Dictionary hingegen wuerde riesengroß werden. Ein unnoetiger Klotz den ein bisschen mehr Prozessorlast ohne weiteres ueberfluessig macht.

Da liegst du aber vollkommen daneben Das Finden eines Elements in einer Liste liegt in O(n), da Suchen in einem Dictionary bei vernünftigen Hashwerten in O(log n) und das macht sich bei vielen (hundert)tausend Anfragen deutlich in der Laufzeit bemerkbar.

nkoehring hat geschrieben:Ich glaube nicht das es effizienter ist, ein zusaetzliches Dictionary zu bemuehen.

Hallo NKoehring!

Innerhalb eines Dictionaries kann **unglaublich schnell** nach einem Schlüssel gesucht werden. Wenn ich den Index eines Eintrags einer Liste nicht weiß, dann muss diese Liste von oben nach unten durchlaufen werden. Das ist im Gegensatz zur Verwendung eines Dictionaries **unglaublich langsam**.

mfg
Gerold

Ja da habt ihr natuerlich beide recht... Irgendwie hab ich da wohl bloedsinnig gedacht, als ich das schrieb.

Aber dann sollte er das Tuple wegwerfen und ganz auf ein Dict umstellen... ich kann mir jedenfalls nicht vorstellen, warum es sinnvoll sein sollte *beides* mit sich zu fuehren.

nkoehring hat geschrieben:@Birkenfeld: Kannst du denn mal kurz und knapp (mit C-Kenntnissen als Voraussetzung) erlaeutern, wie sich Tupel und Lists noch so im Speicher unterscheiden, außer eben das die Liste veraenderbar ist und das Tupel nicht?

Wie gesagt, nur durch die Überallozierung.

Also ich stelle mir das ungefaehr so vor:
Ein Tuple entsteht, indem einfach die zusammenaddierte Bytegroesse des Tuple-Inhalts alloziiert

Pro Objekt ist das ein Pointer.

und das entstandene Objekt nicht mehr angefasst wird. Eine Liste brauch unmengen an Zusatzfunktionen. Sie muss sich staendig neualloziieren und ihren Inhalt veraendern koennen. Das muss ein Tuple nicht.

Diese neu allozierenden Funktionen rufst du ja nicht auf, wenn du eine nichtveränderliche Liste hast. Die Funktionen an sich belegen ja keinen Platz pro Liste.

Aber aendert das etwas an der Geschwindigkeit? Schließlich ist der Abruf eines einzelnen Objektes innerhalb eines Tuples oder einer Liste doch das gleiche. Mache ich also mit einer Liste das gleiche wie mit einem Tuple, sollte es doch speicher- und geschwindigkeitstechnisch keinen Unterschied machen (außer eben bei der erwaehnten Sache mit der Ueberalloziierung, bei großen Listen)... liege ich da richtig?

Ganz genau.

Ansonsten haben Tuples noch einen festen Hash und einige Optimierungen. Wenn ich mich nicht täusche sind alle leeren Tuples das gleiche Objekt und für Tuples unter einer bestimmten Größe wird glaub ich auch das letzte befreite Tuple nicht dealloct damit das nächste malloc wegfällt. Und dann sind noch ein paar Bytes Unterschied im struct.

Die folgende Tabelle zeigt meine Vorstellungen vom (bei Datenstrukturen mit n>>1 Items asymtotischen) Zeitaufwand für einige Operationen an den wichtigsten Python-Datenstrukturen. Bei List und Tuple sind key und place natürlich dasselbe. Strings stelle ich mir genauso wie Tuples vor. Anscheinend ist List fast nur für die append(val)-Operation interessant.

Ich programmiere unter Berücksichtigung dieser Annahmen, und freue mich natürlich darüber, wenn falsche Annahmen berichtigt werden. Ohne zu wissen, wie diese Datenstrukturen und deren Methoden implementiert sind, kann natürlich niemand sichere Aussagen über ihren Zeitaufwand machen.
(Einige Operationen wie change() sind nicht unbedingt in die Sprache eingebaut, ich meine damit umgangssprachlich, was geschehen soll)

Besonders aussagekräftig finde ich die Laufzeiten von Tupeln bei ``insert(key,val)``, ``insert(place,val)``, ``change(key,val)``, ``change(place,val)`` und ``append(val)``.

Goswin hat geschrieben:Ohne zu wissen, wie diese Datenstrukturen und deren Methoden implementiert sind, kann natürlich niemand sichere Aussagen über ihren Zeitaufwand machen.

Ausprobieren?

@Goswin: Könntest Du vielleicht nochmal angeben was Du da genau in der Tabelle zeigst!? Jeweils `n` Operationen? Oder eine Operation bei der die Datenstruktur schon `n` Elemente enthält? Etwas völlig anderes!?

Und Erklärungen zu einigen Operationen wären nicht schlecht. Vielleicht versteht man umgangssprachlich ja etwas anderes unter den Namen als Du damit jetzt gerade meinst. Zum Beispiel haben weder `dict` noch `tuple` eine `append()`-Methode, für was sind denn da die Angaben in der Tabelle!?

Zugriff in Dictionaries über Schlüssel ist (beim Hinzufügen amortisiert) O(1), da eine Hashtabelle als Implementierung zu Grunde liegt. Test auf "enthalten sein" (``in``-Operator) ist auch O(1).

Zugriff auf Listen und Tupel über Index ist O(1). Suchen/Test auf "enthalten sein" eines Elements ist O(n). `append()` auf Listen ist entweder O(1) oder O(n) mit `n` der Anzahl der Elemente in der Liste. Bei vielen `append()`-Operationen ist die Zeit amortisiert O(1) pro Operation, wegen der "Über-Allokation" wenn der Platz im alten Array nicht mehr ausreicht.

@ Blackjack:
Mit n meine ich eine Datenstruktur, die bereits n Elemente enthält. Aufgrund deiner Bemerkung sehe ich nun, daß man auch den asymptotischen Aufwand bezüglich der Anzahl m von ausgeführten Operationen betrachten kann, was sicher interessant ist.

Um alle Operationen, auch die nicht eingebauten, miteinander vergleichen zu können, setze ich folgendes voraus:

• (1) Meine "Keys" sollen implizit geordnet werden können, so dass es also auch in einem Dictionary sinnvoll ist, Keys miteinander zu vergleichen. Unter place verstehe ich die Ordnungszahl der implizit oder tatsächlich geordneten Keys.
  (2) Bei Lists und Tuples sollen die "Keys" nicht nur implizit sondern auch tatsächlich nach Speicherplatz geordnet sein. In diesen Fällen erhalten sie einen Zahlenwert und werden dann üblicherweise nicht mehr Keys, sondern Indices genannt.

Bei jedem Softwarebau muss ich ja von den Operationen ausgehen, die ich mit meinen vorhandenen Daten machen möchte. Erst danach entscheide ich mich für eine Python-Datenstruktur, und wenn diese Struktur eine der Operationen nicht eingebaut hat, muss ich sie halt hinzuprogrammieren.

Zusatz:

Einige der Zeitaufwände, die ich als O(log n) beschreibe könnte man auch als O(1) beschreiben, je nachdem, wie "locker" oder "puristisch" man eingestellt ist (das heißt, je nachdem, ob man als Indices nur Integers oder auch Arbitrary_Long_Integers nehmen darf).

Absolut erstaunlich für mich ist, dass ein Zugriff auf eine Python-list, die ich mir als Verlinkung von Objekten vorstelle, laut Blackjack einen Aufwand von nur O(log n) oder weniger haben soll. Ich kann auf die Schnelle gar nicht sehen, wie so etwas implementiert wird.

Auf den Schlüsseln muss aber keine Ordnung bestehen um sie in Dictionaries zu verwenden. Als Folge von der Implementierung als Hash-Tabelle sind Dictionaries ungeordnet, ein Zugriff auf das `place`\te Element macht keinen Sinn.

Mit Deiner Tabelle kann ich immer noch nichts anfangen. Da kommt nicht einmal O(1) vor, was bedeuten würde in Python gibt's gar keine effizienten Datenstrukturen, und recht häufig O(log n) was auf Baumstrukturen schliessen lässt, die es bei den Standardtypen nicht gibt, und die insbesondere bei Tupeln ziemlich unsinnig wären.

Du solltest Dich mit Leereinträgen in so einer Tabelle anfreunden. Auch das nicht-vorhanden-sein einer Operation ist ein Auswahlkriterium für oder gegen eine Datenstruktur.

Zum Zusatz: Listen sind als Arrays + "Füllstand" implementiert. Immer wenn bei `append()` nicht mehr genügend Platz ist, wird ein grösseres Array angefordert, wobei die Grösse relativ von der Grösse des alten Arrays abhängt. Deshalb ist `append()` oft O(1), manchmal aber auch O(n). Durch diese "Über-Allokation" hat man bei unendlich vielen `append()`\s eine mittlere Laufzeit von O(1) pro Operation. Das Zugriffe per Index O(1) Zeit kosten, sollte bei Arrays einleuchten. Und ja: man kann nur Zahlen im `int`-Bereich als Index verwenden. Da das schon den Adressraum eines Prozesses sprengt, macht mehr auch keinen Sinn.

In Java heisst so etwas `java.util.ArrayList`.

@Blackjack: Vielen Dank für deine Information über die Implementation von Listen . Ich halte es für sehr wichtig, so etwas bei der Programmierung in Betracht zu ziehen, habe es aber in meinem Pythonbüchern bisher nicht gefunden.

Goswin hat geschrieben:Ich halte es für sehr wichtig, so etwas bei der Programmierung in Betracht zu ziehen, habe es aber in meinem Pythonbüchern bisher nicht gefunden.

Es ist eben ein Implementierungsdetail von CPython. Ich kann mich nicht erinnern, dass irgendwo spezifiziert wäre, was für Laufzeiten einzelne Operationen auf den Basisdatentypen haben müssen. Von daher kann das in Jython oder IronPython ganz anders aussehen.

Aber man kann schon davon ausgehen, das Listen sich nicht wie verkettete Listen sondern eher wie Arrays verhalten.

Mich wuerde so eine Tabelle schon interessieren - aber dann bitte eine, deren Werte auch mit Sicherheit stimmen

Uebrigens koennte man in der Tabelle trotzdem ein "append" bei zB Tuples anfuehren. Dieser Eintrag muesste dann den Aufwand zeigen, den es braucht um ein komplett neues Tuple zu erstellen (was man ja tun muesste), welches nun ein neues Element enthaelt.