Das deutsche Python-Forum

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.