Zeitkomplexität von Operationen auf eingebauten Typen
*****************************************************

Diese Seite dokumentiert die Zeitkomplexität verschiedener Operationen
auf eingebauten Typen in CPython. Andere Python-Implementierungen
können ein anderes Laufzeitverhalten haben. Außerdem setzen die
angegebenen Kosten genau diese eingebauten Typen voraus, denn
Instanzen von Unterklassen können andere Kosten haben.

Wir verwenden die Big *O* notation, um zu beschreiben, wie die
Laufzeit einer Operation mit der Größe ihrer Eingaben wächst. Sofern
nicht anders angegeben, bezeichnet *n* die Anzahl der Elemente, die
der Container gerade enthält, und *k* ist der Wert eines numerischen
Parameters, etwa eines Index oder einer Wiederholungszahl.


"list"
======

Listen sind veränderbare Sequenzen. Mehr zur Umsetzung findest du
unter How are lists implemented in CPython?. Die größten Kosten
entstehen, wenn eine Liste über die aktuell belegte Größe hinauswächst
(weil dann alles umziehen muss), oder wenn irgendwo nahe am Anfang
eingefügt oder gelöscht wird (weil dann alles dahinter umziehen muss).
Musst du an beiden Enden hinzufügen oder entfernen, nimm stattdessen
eine "collections.deque" in Erwägung.

+----------------------------------------------------+----------------------------------------------------+
| Operation                                          | Komplexität                                        |
|====================================================|====================================================|
| Kopieren ("l.copy()")                              | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Anhängen ("l.append(x)") [1]                       | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Entnehmen ("l.pop(k)") [1] [2]                     | *O*(*n* - *k*)                                     |
+----------------------------------------------------+----------------------------------------------------+
| Einfügen ("l.insert(k, x)") [1] [2]                | *O*(*n* - *k*)                                     |
+----------------------------------------------------+----------------------------------------------------+
| Element lesen ("l[k]")                             | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Element setzen ("l[k] = x")                        | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Element löschen ("del l[k]") [2]                   | *O*(*n* - *k*)                                     |
+----------------------------------------------------+----------------------------------------------------+
| Iteration                                          | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Slice lesen ("l[i:j]")                             | *O*(*j* - *i*)                                     |
+----------------------------------------------------+----------------------------------------------------+
| Slice setzen ("l[i:j] = t") [1]                    | *O*(*j* - *i*), falls len(*t*) == *j* - *i*, sonst |
|                                                    | *O*(*n* - *i* + len(*t*))                          |
+----------------------------------------------------+----------------------------------------------------+
| Slice löschen ("del l[i:j]")                       | *O*(*n* - *i*)                                     |
+----------------------------------------------------+----------------------------------------------------+
| Erweitern ("l.extend(t)") [1] [3]                  | *O*(len(*t*))                                      |
+----------------------------------------------------+----------------------------------------------------+
| Sortieren ("l.sort()") [4]                         | *O*(*n* log *n*)                                   |
+----------------------------------------------------+----------------------------------------------------+
| Verketten ("l1 + l2")                              | *O*(len(*l1*) + len(*l2*))                         |
+----------------------------------------------------+----------------------------------------------------+
| Vervielfachen ("l * k")                            | *O*(*nk*)                                          |
+----------------------------------------------------+----------------------------------------------------+
| "x in l"                                           | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| "min(l)", "max(l)"                                 | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Länge ermitteln ("len(l)") [5]                     | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+


"tuple"
=======

Ein "tuple" ist eine *unveränderliche* Sequenz. Weil sich ein Tupel
niemals ändern kann, entstehen keine Kosten für Einfügen oder Löschen,
und eine Kopie gibt einfach dasselbe Objekt zurück, braucht also
konstante Zeit (*O*(1)).

+----------------------------------------------------+----------------------------------------------------+
| Operation                                          | Komplexität                                        |
|====================================================|====================================================|
| Kopieren ("tuple(t)")                              | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Element lesen ("t[k]")                             | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Slice lesen ("t[i:j]")                             | *O*(*j* - *i*)                                     |
+----------------------------------------------------+----------------------------------------------------+
| Verketten ("t1 + t2")                              | *O*(len(*t1*) + len(*t2*))                         |
+----------------------------------------------------+----------------------------------------------------+
| Vervielfachen ("t * k")                            | *O*(*nk*)                                          |
+----------------------------------------------------+----------------------------------------------------+
| Iteration                                          | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| "x in t"                                           | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| "min(t)", "max(t)"                                 | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Länge ermitteln ("len(t)") [5]                     | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+


"dict", "frozendict"
====================

Die für dict-Objekte angegebenen Zeiten sind Zeiten für den
durchschnittlichen Fall, denn sie setzen voraus, dass die Hashfunktion
der Objekte robust genug ist, um Kollisionen selten zu machen. Sie
setzen außerdem voraus, dass die Schlüssel gut über die Menge der
möglichen Schlüssel verteilt sind. Im schlechtesten Fall, wenn jeder
Schlüssel auf denselben Wert hasht, braucht jede der unten mit *O*(1)
angegebenen Operationen stattdessen *O*(*n*) Zeit. Sie setzen ferner
voraus, dass Hashen und Vergleichen eines Schlüssels *O*(1) ist. Mehr
zur Umsetzung findest du unter How are dictionaries implemented in
CPython?.

Ein "frozendict" ist unveränderlich, unterstützt also kein Setzen,
Löschen oder Aktualisieren von Elementen. Die übrigen Operationen
unten gelten für es mit denselben Kosten.

+----------------------------------------------------+----------------------------------------------------+
| Operation                                          | Komplexität                                        |
|====================================================|====================================================|
| "key in d"                                         | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Kopieren ("d.copy()") [6] [7]                      | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Element lesen ("d[key]", "d.get(key)")             | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Element setzen ("d[key] = value") [1]              | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Element löschen ("del d[key]", "d.pop(key)")       | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Aktualisieren ("d.update(t)", "d |= t") [1] [3]    | *O*(len(*t*))                                      |
| [7]                                                |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Iteration [7]                                      | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Länge ermitteln ("len(d)") [5]                     | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+


"set", "frozenset"
==================

Siehe "dict", denn die Umsetzungen von "set" und "frozenset" sind
ähnlich, und es gelten dieselben Einschränkungen. Im schlechtesten
Fall brauchen die mit *O*(1) angegebenen Operationen stattdessen
*O*(*n*) Zeit, und Operationen, die jedes Element nachschlagen,
verschlechtern sich entsprechend.

Ein "frozenset" ist *unveränderlich*, unterstützt also weder
Hinzufügen und Verwerfen noch die Operationen, die an Ort und Stelle
aktualisieren. Die übrigen unten gelten für es mit denselben Kosten.

+----------------------------------------------------+----------------------------------------------------+
| Operation                                          | Komplexität                                        |
|====================================================|====================================================|
| "x in s"                                           | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Kopieren ("s.copy()") [6] [7]                      | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Hinzufügen ("s.add(x)") [1]                        | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Verwerfen ("s.discard(x)", "s.remove(x)")          | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Vereinigung ("s1 | s2", "s1.union(s2)") [7]        | *O*(len(*s1*) + len(*s2*))                         |
+----------------------------------------------------+----------------------------------------------------+
| Aktualisieren ("s1 |= s2", "s1.update(s2)") [1]    | *O*(len(*s2*))                                     |
| [7]                                                |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Schnittmenge ("s1 & s2", "s1.intersection(s2)")    | *O*(min(len(*s1*), len(*s2*)))                     |
| [7] [8]                                            |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Schnittmenge aktualisieren ("s1 &= s2",            | *O*(min(len(*s1*), len(*s2*)))                     |
| "s1.intersection_update(s2)") [1] [7] [8]          |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Differenz ("s1 - s2", "s1.difference(s2)") [7] [9] | *O*(len(*s1*))                                     |
+----------------------------------------------------+----------------------------------------------------+
| Differenz aktualisieren ("s1 -= s2",               | *O*(min(len(*s1*), len(*s2*)))                     |
| "s1.difference_update(s2)") [1] [7] [8]            |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Symmetrische Differenz ("s1 ^ s2",                 | *O*(len(*s1*) + len(*s2*))                         |
| "s1.symmetric_difference(s2)") [7]                 |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Symmetrische Differenz aktualisieren ("s1 ^= s2",  | *O*(len(*s2*))                                     |
| "s1.symmetric_difference_update(s2)") [1] [7]      |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Länge ermitteln ("len(s)") [5]                     | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+


"str", "bytes", "bytearray"
===========================

"str"- und "bytes"-Objekte sind unveränderliche Sequenzen von Zeichen
beziehungsweise Bytes. Wie bei Tupeln gibt eine Kopie das
ursprüngliche Objekt zurück. Ein "bytearray" ist veränderbar und
unterstützt zusätzlich die verändernden Operationen von "list" (außer
"sort()"), mit denselben Kosten. Allerdings rückt das Löschen am
Anfang mit "del" ("del b[0]", "del b[:k]") nur den Anfang des Puffers
vor, statt die übrigen Bytes zu verschieben, und ist amortisiert
*O*(1).

+----------------------------------------------------+----------------------------------------------------+
| Operation                                          | Komplexität                                        |
|====================================================|====================================================|
| Element lesen ("s[k]")                             | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Slice lesen ("s[i:j]")                             | *O*(*j* - *i*)                                     |
+----------------------------------------------------+----------------------------------------------------+
| Verketten ("s + t") [10]                           | *O*(len(*s*) + len(*t*))                           |
+----------------------------------------------------+----------------------------------------------------+
| Vervielfachen ("s * k")                            | *O*(*nk*)                                          |
+----------------------------------------------------+----------------------------------------------------+
| Teilzeichenkette suchen ("x in s", "s.find(x)",    | *O*(*n*)                                           |
| "s.index(x)") [11]                                 |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Teilzeichenkette rückwärts suchen ("s.rfind(x)",   | *O*(*n* × len(*x*))                                |
| "s.rindex(x)") [11] [12]                           |                                                    |
+----------------------------------------------------+----------------------------------------------------+
| Kodieren oder Dekodieren [13]                      | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Iteration                                          | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Länge ermitteln ("len(s)") [5]                     | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+


"memoryview"
============

"memoryview"-Objekte erlauben Python-Code, auf die internen Daten
eines Objekts zuzugreifen, das das Puffer-Protokoll unterstützt, ohne
zu kopieren. Insbesondere gibt das Slicing einer Speicheransicht eine
neue Ansicht auf denselben Puffer zurück.

+----------------------------------------------------+----------------------------------------------------+
| Operation                                          | Komplexität                                        |
|====================================================|====================================================|
| Erzeugen ("memoryview(obj)")                       | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Element lesen ("v[k]")                             | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Slice lesen ("v[i:j]")                             | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Index ("v.index(x)") [11] [14]                     | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Zählen ("v.count(x)") [14]                         | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| In Bytes umwandeln ("v.tobytes()", "bytes(v)")     | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Länge ermitteln ("len(v)") [5]                     | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+


"range"
=======

Ein "range"-Objekt berechnet seine Elemente bei Bedarf aus seinen
Werten *start*, *stop* und *step*. Die meisten Operationen hängen
daher nicht von der Länge des Bereichs ab.

+----------------------------------------------------+----------------------------------------------------+
| Operation                                          | Komplexität                                        |
|====================================================|====================================================|
| Element lesen ("r[k]")                             | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Slice lesen ("r[i:j]")                             | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| "x in r" [15]                                      | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Index und Anzahl ("r.index(x)", "r.count(x)") [15] | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+
| Iteration                                          | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| "min(r)", "max(r)"                                 | *O*(*n*)                                           |
+----------------------------------------------------+----------------------------------------------------+
| Länge ermitteln ("len(r)") [5]                     | *O*(1)                                             |
+----------------------------------------------------+----------------------------------------------------+


Anmerkungen
===========

[1] Amortisiert. Eine einzelne Operation kann gelegentlich *O*(*n*)
    sein, wenn der zugrunde liegende Speicher vergrößert wird, aber
    diese Kosten verteilen sich je nach Vorgeschichte des Containers
    auf viele Operationen.

[2] Entnimmt oder löscht man das Element am Index *k* einer Liste der
    Größe *n*, rücken alle Elemente nach *k* um einen Platz nach
    links, es ziehen also *n* - *k* - 1 Elemente um. Fügt man am Index
    *k* ein, rücken die Elemente von *k* an um einen Platz nach
    rechts, es ziehen also *n* - *k* Elemente um. Der schlechteste
    Fall ist Index 0, wo der ganze Rest der Liste umziehen muss. Der
    durchschnittliche Fall, ein Index in der Mitte der Liste, braucht
    *O*(*n*/2) = *O*(*n*) Operationen, und am Ende der Liste zieht
    nichts um, das ist *O*(1).

[3] Zuzüglich der Kosten für das Iterieren über *t*, das bei einem
    beliebigen Iterable teuer sein kann.

[4] Das ist der schlechteste Fall. Das Sortieren passt sich an, und
    bei bereits sortierter oder umgekehrt sortierter Eingabe braucht
    es nur *O*(*n*) Vergleiche. Mehr dazu in Objects/listsort.txt.

[5] Die Anzahl der Elemente ist im Objekt gespeichert, "len()" muss
    sie also nicht zählen.

[6] Ein "frozendict" oder ein "frozenset" zu kopieren ist *O*(1), denn
    dabei wird das ursprüngliche Objekt zurückgegeben.

[7] Diese Operationen durchlaufen die interne Hash-Tabelle des
    Containers, die beim Entfernen von Elementen nicht verkleinert
    wird. Nachdem die meisten Elemente entfernt wurden, brauchen sie
    weiterhin Zeit proportional zur früheren Größe des Containers, bis
    eine späteres Einfügen eine Größenänderung auslöst.

[8] *O*(len(*t*)), wenn *t* keine Menge ist.

[9] *O*(len(*s*) + len(*t*)), wenn *t* keine Menge ist.

[10] Jede Verkettung baut ein neues Objekt, eine Zeichenkette aus
     vielen Teilen in einer Schleife zusammenzusetzen ist daher
     quadratisch in der Gesamtlänge. Alternativen findest du in der
     Anmerkung zum Verketten unveränderlicher Sequenzen.

[11] Mit den Argumenten *start* und *end* ist *n* die Länge des
     durchsuchten Bereichs und nicht die von *s*, und anders als beim
     Slicing wird nichts kopiert.

[12] Das ist der schlechteste Fall. Rückwärtssuchen sind bei typischer
     Eingabe *O*(*n*). Vorwärtssuchen verwenden stattdessen einen
     ausgefeilteren Algorithmus mit linearem schlechtesten Fall,
     beschrieben in
     Objects/stringlib/stringlib_find_two_way_notes.txt.

[13] Das setzt einen Codec voraus, der je Zeichen einen konstanten
     Aufwand hat.

[14] Diese entpacken und vergleichen jedes Element einzeln und sind
     daher viel langsamer als die entsprechenden Methoden von "bytes".

[15] Das setzt Argumente vom Typ "int" oder "bool" voraus. Für andere
     Typen wird der Bereich wie jede andere Sequenz in *O*(*n*) Zeit
     durchsucht.
