Dit artikel documenteert de tijdscomplexiteit van diverse operaties op de ingebouwde typen van CPython, gebruikmakend van de Big O-notatie om de schaalbaarheid van uitvoeringstijden te beschrijven.
De belangrijkste bevindingen per datatype zijn:
- Lists: Mutable sequences waarbij
append geamortiseerd $O(1)$ is, maar operaties zoals insert en pop (behalve aan het einde) $O(n)$ kosten door het verschuiven van elementen.
- Tuples: Immutable sequences; omdat ze niet kunnen veranderen, is het kopiëren ervan $O(1)$.
- Dicts & Sets: Gebaseerd op hash-tabellen, wat gemiddeld $O(1)$ tijd kost voor opzoekingen, invoegingen en verwijderingen, mits er weinig hash-collisies zijn.
- Strings & Bytes: Immutable sequences waarbij het zoeken naar substrings over het algemeen $O(n)$ is.
- Memoryview: Biedt toegang tot interne data zonder kopieën te maken, waardoor operaties zoals slicen $O(1)$ kosten.
- Range: Berekent items on-demand, waardoor de meeste operaties (zoals
x in r) onafhankelijk zijn van de lengte en $O(1)$ kosten.
Het artikel bevat daarnaast technische toelichtingen over geamortiseerde kosten en de specifieke implementatiedetails van de CPython-buffer en hash-tabellen.
Tijdscomplexiteit van operaties op ingebouwde typen
We gebruiken de Big O-notatie om te beschrijven hoe de uitvoeringstijd van een operatie groeit met de grootte van de inputs. Tenzij anders vermeld, staat n voor het aantal elementen dat zich momenteel in de container bevindt, en k is de waarde van een numerieke parameter, zoals een index of een herhalingsaantal.
list
Lists zijn mutable sequences; voor meer details over de implementatie, zie How are lists implemented in CPython?. De grootste kosten ontstaan wanneer de lijst groeit voorbij de huidige allocatiegrootte (omdat alles verplaatst moet worden), of bij het invoegen of verwijderen van elementen nabij het begin (omdat alles daarna moet verschuiven).
Als je elementen aan beide uiteinden moet toevoegen of verwijderen, overweeg dan het gebruik van collections.deque.
| Operatie | Complexiteit |
|---|
Kopiëren (l.copy()) | $O(n)$ |
Append (l.append(x)) [1] | $O(1)$ |
Pop (l.pop(k)) [1] [2] | $O(n - k)$ |
Insert (l.insert(k, x)) [1] [2] | $O(n - k)$ |
Item ophalen (l[k]) | $O(1)$ |
Item instellen (l[k] = x) | $O(1)$ |
Item verwijderen (del l[k]) [2] | $O(n - k)$ |
| Iteratie | $O(n)$ |
Slice ophalen (l[i:j]) | $O(j - i)$ |
Slice instellen (l[i:j] = t) [1] | $O(j - i)$ als len(t) == j - i, anders $O(n - i + len(t))$ |
Slice verwijderen (del l[i:j]) | $O(n - i)$ |
Extend (l.extend(t)) [1] [3] | $O(len(t))$ |
Sorteren (l.sort()) [4] | $O(n \log n)$ |
Concateneren (l1 + l2) | $O(len(l1) + len(l2))$ |
Vermenigvuldigen (l * k) | $O(nk)$ |
x in l | $O(n)$ |
min(l), max(l) | $O(n)$ |
Lengte ophalen (len(l)) [5] | $O(1)$ |
tuple
Een tuple is een immutable sequence. Omdat een tuple nooit kan veranderen, zijn er geen kosten voor invoeging of verwijdering, en het maken van een kopie geeft simpelweg hetzelfde object terug, wat dus constante tijd kost ($O(1)$).
| Operatie | Complexiteit |
|---|
Kopiëren (tuple(t)) | $O(1)$ |
Item ophalen (t[k]) | $O(1)$ |
Slice ophalen (t[i:j]) | $O(j - i)$ |
Concateneren (t1 + t2) | $O(len(t1) + len(t2))$ |
Vermenigvuldigen (t * k) | $O(nk)$ |
| Iteratie | $O(n)$ |
x in t | $O(n)$ |
min(t), max(t) | $O(n)$ |
Lengte ophalen (len(t)) [5] | $O(1)$ |
dict, frozendict
De vermelde tijden voor dict-objecten zijn gemiddelde tijden, aangezien ze ervan uitgaan dat de hash-functie voor de objecten robuust genoeg is om collsies ongebruikelijk te maken. Er wordt ook aangenomen dat de sleutels goed verdeeld zijn over de verzameling van mogelijke sleutels. In het slechtste geval, wanneer elke sleutel naar dezelfde waarde hasht, kost elke onderstaande $O(1)$-operatie in plaats daarvan $O(n)$ tijd. Daarnaast wordt ervan uitgegaan dat het hashen en vergelijken van een sleutel $O(1)$ is. Voor meer details over de implementatie, zie How are dictionaries implemented in CPython?.
Een frozendict is immutable en ondersteunt daarom geen instellen, verwijderen of bijwerken van items. De overige onderstaande operaties zijn van toepassing met dezelfde kosten.
| Operatie | Complexiteit |
|---|
key in d | $O(1)$ |
Kopiëren (d.copy()) [6] [7] | $O(n)$ |
Item ophalen (d[key], d.get(key)) | $O(1)$ |
Item instellen (d[key] = value) [1] | $O(1)$ |
Item verwijderen (del d[key], d.pop(key)) | $O(1)$ |
Update (d.update(t), `d | = t`) [1] [3] [7] | $O(len(t))$ |
| Iteratie [7] | $O(n)$ |
Lengte ophalen (len(d)) [5] | $O(1)$ |
set, frozenset
Zie dict, aangezien de implementaties van set en frozenset vergelijkbaar zijn en dezelfde kanttekeningen van toepassing zijn.
In het slechtste geval kosten $O(1)$-operaties in plaats daarvan $O(n)$ tijd, en operaties die elk element opzoeken verslechteren dienovereenkomstig.
Een frozenset is immutable en ondersteunt daarom geen toevoegingen, het verwijderen van elementen of in-place update-operaties. De overige onderstaande operaties zijn van toepassing met dezelfde kosten.
| Operatie | Complexiteit |
|---|
x in s | $O(1)$ |
Kopiëren (s.copy()) [6] [7] | $O(n)$ |
Toevoegen (s.add(x)) [1] | $O(1)$ |
Verwijderen (s.discard(x), s.remove(x)) | $O(1)$ |
| Union (`s1 | s2, s1.union(s2)`) [7] | $O(len(s1) + len(s2))$ |
| Update (`s1 | = s2, s1.update(s2)`) [1] [7] | $O(len(s2))$ |
Intersection (s1 & s2, s1.intersection(s2)) [7] [8] | $O(min(len(s1), len(s2)))$ |
Intersection update (s1 &= s2, s1.intersection_update(s2)) [1] [7] [8] | $O(min(len(s1), len(s2)))$ |
Difference (s1 - s2, s1.difference(s2)) [7] [9] | $O(len(s1))$ |
Difference update (s1 -= s2, s1.difference_update(s2)) [1] [7] [8] | $O(min(len(s1), len(s2)))$ |
Symmetric difference (s1 ^ s2, s1.symmetric_difference(s2)) [7] | $O(len(s1) + len(s2))$ |
Symmetric difference update (s1 ^= s2, s1.symmetricdifferenceupdate(s2)) [1] [7] | $O(len(s2))$ |
Lengte ophalen (len(s)) [5] | $O(1)$ |
str, bytes, bytearray
str- en bytes-objecten zijn respectievelijk immutable sequences van tekens en bytes. Net als bij tuples geeft het kopiëren ervan het originele object terug.
Een bytearray is mutable en ondersteunt daarnaast de muterende operaties van list (behalve sort()), tegen dezelfde kosten. Echter, het verwijderen aan het begin met del (del b[0], del b[:k]) schuift alleen het begin van de buffer vooruit in plaats van de resterende bytes te verplaatsen, en is geamortiseerd $O(1)$.
| Operatie | Complexiteit |
|---|
Item ophalen (s[k]) | $O(1)$ |
Slice ophalen (s[i:j]) | $O(j - i)$ |
Concateneren (s + t) [10] | $O(len(s) + len(t))$ |
Vermenigvuldigen (s * k) | $O(nk)$ |
Substring zoeken (x in s, s.find(x), s.index(x)) [11] | $O(n)$ |
Reverse substring zoeken (s.rfind(x), s.rindex(x)) [11] [12] | $O(n \times len(x))$ |
| Encoderen of decoderen [13] | $O(n)$ |
| Iteratie | $O(n)$ |
Lengte ophalen (len(s)) [5] | $O(1)$ |
memoryview
memoryview-objecten stellen Python-code in staat om toegang te krijgen tot de interne data van een object dat het bufferprotocol ondersteunt, zonder dat er kopieën gemaakt hoeven te worden. In het bijzonder geeft het slicen van een memory view een nieuwe view op dezelfde buffer terug.
| Operatie | Complexiteit |
|---|
Aanmaken (memoryview(obj)) | $O(1)$ |
Item ophalen (v[k]) | $O(1)$ |
Slice ophalen (v[i:j]) | $O(1)$ |
Index (v.index(x)) [11] [14] | $O(n)$ |
Count (v.count(x)) [14] | $O(n)$ |
Converteren naar bytes (v.tobytes(), bytes(v)) | $O(n)$ |
Lengte ophalen (len(v)) [5] | $O(1)$ |
range
Een range-object berekent zijn items on-demand op basis van de start-, stop- en stapwaarden, waardoor de meeste operaties niet afhankelijk zijn van de lengte van de range.
| Operatie | Complexiteit |
|---|
Item ophalen (r[k]) | $O(1)$ |
Slice ophalen (r[i:j]) | $O(1)$ |
x in r [15] | $O(1)$ |
Index en count (r.index(x), r.count(x)) [15] | $O(1)$ |
| Iteratie | $O(n)$ |
min(r), max(r) | $O(n)$ |
Lengte ophalen (len(r)) [5] | $O(1)$ |
Notities
[1] Geamortiseerd. Een individuele operatie kan af en toe $O(n)$ zijn wanneer de onderliggende opslag wordt vergroot, maar deze kosten worden verspreid over vele operaties, afhankelijk van de geschiedenis van de container.
[2] Het verwijderen (pop) of deleten van het element op index k van een lijst van grootte n verschuift alle elementen na k één positie naar links, wat n - k - 1 elementen verplaatst; invoegen op index k verschuift de elementen vanaf k één positie naar rechts, wat n - k elementen verplaatst. Het slechtste geval is index 0, waarbij de rest van de lijst moet worden verplaatst; het gemiddelde geval, een index in het midden van de lijst, kost $O(n/2) = O(n)$ operaties; en een operatie aan het einde van de lijst verplaatst niets en is $O(1)$.
[3] Plus de kosten van het itereren over t, wat duur kan zijn voor een willekeurige iterable.
[4] Dit is het slechtste scenario. Sorteren is adaptief en input die al gesorteerd of omgekeerd gesorteerd is, kost slechts $O(n)$ vergelijkingen. Zie Objects/listsort.txt voor meer informatie.
[5] Het aantal elementen is opgeslagen in het object, dus len() hoeft ze niet te tellen.
[6] Het kopiëren van een frozendict of een frozenset is $O(1)$ aangezien het het originele object teruggeeft.
[7] Deze operaties scannen de interne hash-tabel van de container, die niet wordt verkleind wanneer elementen worden verwijderd. Na het verwijderen van de meeste elementen kosten ze nog steeds tijd proportioneel aan de voormalige grootte van de container, totdat een latere invoeging een resize triggert.
[8] $O(len(t))$ als t geen set is.
[9] $O(len(s) + len(t))$ als t geen set is.
[10] Elke concatenatie bouwt een nieuw object; het bouwen van een string door veel stukjes in een loop te concateneren is dus kwadratisch in de totale lengte. Zie de notitie over het concateneren van immutable sequences voor alternatieven.
[11] Met start- en eindargumenten is n de lengte van de gezochte regio in plaats van de lengte van s, en in tegenstelling tot slicing wordt er niets gekopieerd.
[12] Dit is het slechtste geval. Reverse searches zijn $O(n)$ bij typische input. Forward searches gebruiken daarentegen een complexer algoritme met een lineair slechtste geval, beschreven in Objects/stringlib/stringlibfindtwowaynotes.txt.
[13] Er wordt uitgegaan van een codec die een constante hoeveelheid werk per teken verricht.
[14] Deze pakken elk element individueel uit en vergelijken deze, waardoor ze veel langzamer zijn dan de equivalente bytes-methoden.
[15] Uitgaande van int of bool argumenten. Voor andere typen wordt de range gezocht als elke andere sequence in $O(n)$ tijd.
Tijdscomplexiteit van operaties op ingebouwde typen
We gebruiken de Big O-notatie om te beschrijven hoe de uitvoeringstijd van een operatie groeit met de grootte van de inputs. Tenzij anders vermeld, staat n voor het aantal elementen dat zich momenteel in de container bevindt, en k is de waarde van een numerieke parameter, zoals een index of een herhalingsaantal.
list
Lists zijn mutable sequences; voor meer details over de implementatie, zie How are lists implemented in CPython?. De grootste kosten ontstaan wanneer de lijst groeit voorbij de huidige allocatiegrootte (omdat alles verplaatst moet worden), of bij het invoegen of verwijderen van elementen nabij het begin (omdat alles daarna moet verschuiven).
Als je elementen aan beide uiteinden moet toevoegen of verwijderen, overweeg dan het gebruik van collections.deque.
| Operatie | Complexiteit |
|---|
Kopiëren (l.copy()) | $O(n)$ |
Append (l.append(x)) [1] | $O(1)$ |
Pop (l.pop(k)) [1] [2] | $O(n - k)$ |
Insert (l.insert(k, x)) [1] [2] | $O(n - k)$ |
Item ophalen (l[k]) | $O(1)$ |
Item instellen (l[k] = x) | $O(1)$ |
Item verwijderen (del l[k]) [2] | $O(n - k)$ |
| Iteratie | $O(n)$ |
Slice ophalen (l[i:j]) | $O(j - i)$ |
Slice instellen (l[i:j] = t) [1] | $O(j - i)$ als len(t) == j - i, anders $O(n - i + len(t))$ |
Slice verwijderen (del l[i:j]) | $O(n - i)$ |
Extend (l.extend(t)) [1] [3] | $O(len(t))$ |
Sorteren (l.sort()) [4] | $O(n \log n)$ |
Concateneren (l1 + l2) | $O(len(l1) + len(l2))$ |
Vermenigvuldigen (l * k) | $O(nk)$ |
x in l | $O(n)$ |
min(l), max(l) | $O(n)$ |
Lengte ophalen (len(l)) [5] | $O(1)$ |
tuple
Een tuple is een immutable sequence. Omdat een tuple nooit kan veranderen, zijn er geen kosten voor invoeging of verwijdering, en het maken van een kopie geeft simpelweg hetzelfde object terug, wat dus constante tijd kost ($O(1)$).
| Operatie | Complexiteit |
|---|
Kopiëren (tuple(t)) | $O(1)$ |
Item ophalen (t[k]) | $O(1)$ |
Slice ophalen (t[i:j]) | $O(j - i)$ |
Concateneren (t1 + t2) | $O(len(t1) + len(t2))$ |
Vermenigvuldigen (t * k) | $O(nk)$ |
| Iteratie | $O(n)$ |
x in t | $O(n)$ |
min(t), max(t) | $O(n)$ |
Lengte ophalen (len(t)) [5] | $O(1)$ |
dict, frozendict
De vermelde tijden voor dict-objecten zijn gemiddelde tijden, aangezien ze ervan uitgaan dat de hash-functie voor de objecten robuust genoeg is om collsies ongebruikelijk te maken. Er wordt ook aangenomen dat de sleutels goed verdeeld zijn over de verzameling van mogelijke sleutels. In het slechtste geval, wanneer elke sleutel naar dezelfde waarde hasht, kost elke onderstaande $O(1)$-operatie in plaats daarvan $O(n)$ tijd. Daarnaast wordt ervan uitgegaan dat het hashen en vergelijken van een sleutel $O(1)$ is. Voor meer details over de implementatie, zie How are dictionaries implemented in CPython?.
Een frozendict is immutable en ondersteunt daarom geen instellen, verwijderen of bijwerken van items. De overige onderstaande operaties zijn van toepassing met dezelfde kosten.
| Operatie | Complexiteit |
|---|
key in d | $O(1)$ |
Kopiëren (d.copy()) [6] [7] | $O(n)$ |
Item ophalen (d[key], d.get(key)) | $O(1)$ |
Item instellen (d[key] = value) [1] | $O(1)$ |
Item verwijderen (del d[key], d.pop(key)) | $O(1)$ |
Update (d.update(t), `d | = t`) [1] [3] [7] | $O(len(t))$ |
| Iteratie [7] | $O(n)$ |
Lengte ophalen (len(d)) [5] | $O(1)$ |
set, frozenset
Zie dict, aangezien de implementaties van set en frozenset vergelijkbaar zijn en dezelfde kanttekeningen van toepassing zijn.
In het slechtste geval kosten $O(1)$-operaties in plaats daarvan $O(n)$ tijd, en operaties die elk element opzoeken verslechteren dienovereenkomstig.
Een frozenset is immutable en ondersteunt daarom geen toevoegingen, het verwijderen van elementen of in-place update-operaties. De overige onderstaande operaties zijn van toepassing met dezelfde kosten.
| Operatie | Complexiteit |
|---|
x in s | $O(1)$ |
Kopiëren (s.copy()) [6] [7] | $O(n)$ |
Toevoegen (s.add(x)) [1] | $O(1)$ |
Verwijderen (s.discard(x), s.remove(x)) | $O(1)$ |
| Union (`s1 | s2, s1.union(s2)`) [7] | $O(len(s1) + len(s2))$ |
| Update (`s1 | = s2, s1.update(s2)`) [1] [7] | $O(len(s2))$ |
Intersection (s1 & s2, s1.intersection(s2)) [7] [8] | $O(min(len(s1), len(s2)))$ |
Intersection update (s1 &= s2, s1.intersection_update(s2)) [1] [7] [8] | $O(min(len(s1), len(s2)))$ |
Difference (s1 - s2, s1.difference(s2)) [7] [9] | $O(len(s1))$ |
Difference update (s1 -= s2, s1.difference_update(s2)) [1] [7] [8] | $O(min(len(s1), len(s2)))$ |
Symmetric difference (s1 ^ s2, s1.symmetric_difference(s2)) [7] | $O(len(s1) + len(s2))$ |
Symmetric difference update (s1 ^= s2, s1.symmetricdifferenceupdate(s2)) [1] [7] | $O(len(s2))$ |
Lengte ophalen (len(s)) [5] | $O(1)$ |
str, bytes, bytearray
str- en bytes-objecten zijn respectievelijk immutable sequences van tekens en bytes. Net als bij tuples geeft het kopiëren ervan het originele object terug.
Een bytearray is mutable en ondersteunt daarnaast de muterende operaties van list (behalve sort()), tegen dezelfde kosten. Echter, het verwijderen aan het begin met del (del b[0], del b[:k]) schuift alleen het begin van de buffer vooruit in plaats van de resterende bytes te verplaatsen, en is geamortiseerd $O(1)$.
| Operatie | Complexiteit |
|---|
Item ophalen (s[k]) | $O(1)$ |
Slice ophalen (s[i:j]) | $O(j - i)$ |
Concateneren (s + t) [10] | $O(len(s) + len(t))$ |
Vermenigvuldigen (s * k) | $O(nk)$ |
Substring zoeken (x in s, s.find(x), s.index(x)) [11] | $O(n)$ |
Reverse substring zoeken (s.rfind(x), s.rindex(x)) [11] [12] | $O(n \times len(x))$ |
| Encoderen of decoderen [13] | $O(n)$ |
| Iteratie | $O(n)$ |
Lengte ophalen (len(s)) [5] | $O(1)$ |
memoryview
memoryview-objecten stellen Python-code in staat om toegang te krijgen tot de interne data van een object dat het bufferprotocol ondersteunt, zonder dat er kopieën gemaakt hoeven te worden. In het bijzonder geeft het slicen van een memory view een nieuwe view op dezelfde buffer terug.
| Operatie | Complexiteit |
|---|
Aanmaken (memoryview(obj)) | $O(1)$ |
Item ophalen (v[k]) | $O(1)$ |
Slice ophalen (v[i:j]) | $O(1)$ |
Index (v.index(x)) [11] [14] | $O(n)$ |
Count (v.count(x)) [14] | $O(n)$ |
Converteren naar bytes (v.tobytes(), bytes(v)) | $O(n)$ |
Lengte ophalen (len(v)) [5] | $O(1)$ |
range
Een range-object berekent zijn items on-demand op basis van de start-, stop- en stapwaarden, waardoor de meeste operaties niet afhankelijk zijn van de lengte van de range.
| Operatie | Complexiteit |
|---|
Item ophalen (r[k]) | $O(1)$ |
Slice ophalen (r[i:j]) | $O(1)$ |
x in r [15] | $O(1)$ |
Index en count (r.index(x), r.count(x)) [15] | $O(1)$ |
| Iteratie | $O(n)$ |
min(r), max(r) | $O(n)$ |
Lengte ophalen (len(r)) [5] | $O(1)$ |
Notities
[1] Geamortiseerd. Een individuele operatie kan af en toe $O(n)$ zijn wanneer de onderliggende opslag wordt vergroot, maar deze kosten worden verspreid over vele operaties, afhankelijk van de geschiedenis van de container.
[2] Het verwijderen (pop) of deleten van het element op index k van een lijst van grootte n verschuift alle elementen na k één positie naar links, wat n - k - 1 elementen verplaatst; invoegen op index k verschuift de elementen vanaf k één positie naar rechts, wat n - k elementen verplaatst. Het slechtste geval is index 0, waarbij de rest van de lijst moet worden verplaatst; het gemiddelde geval, een index in het midden van de lijst, kost $O(n/2) = O(n)$ operaties; en een operatie aan het einde van de lijst verplaatst niets en is $O(1)$.
[3] Plus de kosten van het itereren over t, wat duur kan zijn voor een willekeurige iterable.
[4] Dit is het slechtste scenario. Sorteren is adaptief en input die al gesorteerd of omgekeerd gesorteerd is, kost slechts $O(n)$ vergelijkingen. Zie Objects/listsort.txt voor meer informatie.
[5] Het aantal elementen is opgeslagen in het object, dus len() hoeft ze niet te tellen.
[6] Het kopiëren van een frozendict of een frozenset is $O(1)$ aangezien het het originele object teruggeeft.
[7] Deze operaties scannen de interne hash-tabel van de container, die niet wordt verkleind wanneer elementen worden verwijderd. Na het verwijderen van de meeste elementen kosten ze nog steeds tijd proportioneel aan de voormalige grootte van de container, totdat een latere invoeging een resize triggert.
[8] $O(len(t))$ als t geen set is.
[9] $O(len(s) + len(t))$ als t geen set is.
[10] Elke concatenatie bouwt een nieuw object; het bouwen van een string door veel stukjes in een loop te concateneren is dus kwadratisch in de totale lengte. Zie de notitie over het concateneren van immutable sequences voor alternatieven.
[11] Met start- en eindargumenten is n de lengte van de gezochte regio in plaats van de lengte van s, en in tegenstelling tot slicing wordt er niets gekopieerd.
[12] Dit is het slechtste geval. Reverse searches zijn $O(n)$ bij typische input. Forward searches gebruiken daarentegen een complexer algoritme met een lineair slechtste geval, beschreven in Objects/stringlib/stringlibfindtwowaynotes.txt.
[13] Er wordt uitgegaan van een codec die een constante hoeveelheid werk per teken verricht.
[14] Deze pakken elk element individueel uit en vergelijken deze, waardoor ze veel langzamer zijn dan de equivalente bytes-methoden.
[15] Uitgaande van int of bool argumenten. Voor andere typen wordt de range gezocht als elke andere sequence in $O(n)$ tijd.
Groetjes,