Sisäänrakennettujen vaativuus
Kaikki mitä Python tarjoaa ilman importtia: sisäänrakennetut tyypit, sisäänrakennetut
funktiot, vakiot ja poikkeushierarkia. Jokainen alla oleva kohta linkittää sivulle,
jolla on täydellinen erittely; tämän sivun taulukot antavat päävaativuuden, jotta
löydät etsimäsi yhdellä silmäyksellä.
Sisäänrakennetut tyypit
| Tyyppi |
Käyttötarkoitus |
Haku (keskim.) |
Lisäys (keskim.) |
Poisto (keskim.) |
list |
Järjestetyt jonot |
O(1) |
O(n) |
O(n) |
tuple |
Muuttumaton jono |
O(1) |
- |
- |
range |
Lukujonot |
O(1) |
- |
- |
str |
Teksti |
O(1) |
- |
- |
bytes |
Binääridata |
O(1) |
- |
- |
dict |
Avain-arvo-kuvaus |
O(1) |
O(1) |
O(1) |
set |
Uniikit alkiot |
- |
O(1) |
O(1) |
frozenset |
Muuttumattomat uniikit alkiot |
- |
- |
- |
Jonotyypit
Kuvaus- ja joukkotyypit
- Sanakirja - Hajautukseen perustuva avain-arvo-säilö
- Joukko - Järjestämättömät uniikit alkiot
- Frozenset - Muuttumattomat uniikit alkiot
Luku- ja totuusarvotyypit
Sisäänrakennetut funktiot
Iterointi
Tämän ryhmän funktiot palauttavat iteraattorin. Sen luominen on halpaa; Huomiot-sarakkeessa
mainittu kustannus on se, minkä maksat iteraattorin läpikäynnistä.
| Funktio |
Aika |
Tila |
Huomiot |
iter() |
O(1) |
O(1) |
Kääri iteroitavan iteraattoriksi |
next() |
O(1)* |
O(1) |
* kustannus riippuu taustalla olevasta iteraattorista |
aiter() |
O(1) |
O(1) |
iter()-funktion asynkroninen vastine |
anext() |
O(1) |
O(1) |
Odottaminen maksaa sen, minkä asynkroninen generaattori maksaa |
enumerate() |
O(1) |
O(1) |
O(n) läpikäyntiin; tuottaa (indeksi, alkio) -monikoita |
zip() |
O(1) |
O(1) |
O(n) läpikäyntiin; pysähtyy lyhimpään iteroitavaan |
map() |
O(1) |
O(1) |
O(n*k) läpikäyntiin, k = funktion aika |
filter() |
O(1) |
O(1) |
O(n*k) läpikäyntiin, k = predikaatin aika |
reversed() |
O(1) |
O(1) |
O(n) läpikäyntiin; vaatii __reversed__ tai __getitem__ |
Koonti ja järjestäminen
| Funktio |
Aika |
Tila |
Huomiot |
len() |
O(1) |
O(1) |
Sisäänrakennetut säilöt tallettavat pituutensa |
sum() |
O(n) |
O(1) |
O(n²) jos sitä käytetään väärin merkkijonojen yhdistämiseen |
min() |
O(n) |
O(1) |
Vertailtava jokainen alkio |
max() |
O(n) |
O(1) |
Vertailtava jokainen alkio |
sorted() |
O(n log n) |
O(n) |
Timsort (≤3.10), Powersort (3.11+) |
all() |
O(n) |
O(1) |
Katkaisee ensimmäiseen epätoteen alkioon |
any() |
O(n) |
O(1) |
Katkaisee ensimmäiseen toteen alkioon |
Luvut ja lukujärjestelmät
| Funktio |
Aika |
Tila |
Huomiot |
abs() |
O(1) |
O(1) |
O(n) negatiiviselle n numeron int-arvolle; oma __abs__() määrää kustannuksensa itse |
divmod() |
O(1) |
O(1) |
O(n²) mielivaltaisen tarkkuuden kokonaisluvuille |
pow() |
O(r²) |
Θ(r) |
r = tuloksen bittimäärä; kolmen argumentin muoto O(log y * m²) tilassa Θ(m) |
round() |
O(1) |
O(1) |
Pankkiirin pyöristys tasan puolikkailla |
bin() |
O(log n) |
O(log n) |
Kustannus on tulosteen pituus |
hex() |
O(log n) |
O(log n) |
Kustannus on tulosteen pituus |
oct() |
O(log n) |
O(log n) |
Kustannus on tulosteen pituus |
Teksti ja merkit
| Funktio |
Aika |
Tila |
Huomiot |
chr() |
O(1) |
O(1) |
Koodipisteestä merkiksi |
ord() |
O(1) |
O(1) |
Merkistä koodipisteeksi |
format() |
O(n) |
O(n) |
n = tuloksen pituus |
repr() |
O(n) |
O(n) |
Etenee rekursiivisesti säilöihin |
ascii() |
O(n) |
O(n) |
Kuten repr(), mutta suojaa ei-ASCII-merkit |
hash() |
O(k) |
O(1) |
O(n) merkkijonoille, välimuistissa ensimmäisen kutsun jälkeen |
Oliot, attribuutit ja tyypit
| Funktio |
Aika |
Tila |
Huomiot |
type() |
O(1) |
O(1) |
O(n) kolmen argumentin luokan luovassa muodossa |
isinstance() |
O(d) |
O(1) |
d = MRO:n syvyys; käytännössä O(1) |
issubclass() |
O(d) |
O(1) |
d = MRO:n syvyys; käytännössä O(1) |
callable() |
O(1) |
O(1) |
Tarkistaa __call__-metodin |
id() |
O(1) |
O(1) |
is-operaattorin perusta |
getattr() |
O(d) |
O(1) |
Osuma ilmentymän sanakirjaan on keskimäärin O(1) |
setattr() |
O(1) |
O(1) |
Lisäys hajautustauluun |
hasattr() |
O(d) |
O(1) |
Sama haku kuin getattr(), poikkeus napataan kiinni |
delattr() |
O(1) |
O(1) |
Poisto hajautustaulusta |
dir() |
O(n log n) |
O(n) |
Tuloksen järjestäminen hallitsee kustannusta |
vars() |
O(1) |
O(1) |
Palauttaa viitteen __dict__-sanakirjaan, ei kopiota |
super() |
O(d) |
O(d) |
Kulkee MRO:n läpi, joka on välimuistissa |
property() |
O(1) |
O(1) |
Kuvaajan luonti ja käyttö |
classmethod() |
O(1) |
O(1) |
Kuvaajan luonti; haku on O(d) |
staticmethod() |
O(1) |
O(1) |
Kuvaajan luonti; haku on O(d) |
Tyyppien konstruktorit
| Konstruktori |
Aika |
Tila |
Huomiot |
bool() |
O(1) |
O(1) |
Säilöt vastaavat __len__()-metodilla, joka on O(1) |
int() |
O(1) |
O(1) |
O(n²) hyvin pitkän lukumerkkijonon jäsennyksessä |
float() |
O(1) |
O(1) |
O(n) merkkijonosta |
complex() |
O(1) |
O(1) |
O(n) merkkijonosta |
str() |
O(1) |
O(1) |
O(n) säilöille ja omalle __str__()-toteutukselle |
bytes() |
O(n) |
O(n) |
n = lähteen pituus |
bytearray() |
O(n) |
O(n) |
n = lähteen pituus |
memoryview() |
O(1) |
O(1) |
Näkymä puskuriin, ei koskaan kopio |
list() |
O(n) |
O(n) |
n = iteroitavan pituus |
tuple() |
O(n) |
O(n) |
O(1) kun argumentti on jo monikko |
dict() |
O(n) |
O(n) |
O(n²) pahimmassa tapauksessa hajautustörmäyksillä |
set() |
O(n) |
O(n) |
O(n²) pahimmassa tapauksessa hajautustörmäyksillä |
frozenset() |
O(n) |
O(n) |
O(1) kun argumentti on jo frozenset |
slice() |
O(1) |
O(1) |
Tallettaa vain indeksit; sen soveltaminen maksaa O(k) |
object() |
O(1) |
O(1) |
Jokaisen luokan perusta |
Koodin suoritus
| Funktio |
Aika |
Tila |
Huomiot |
eval() |
O(n + m) |
O(n + m) |
n = lähdekoodin pituus, m = evaluoinnin kustannus |
exec() |
O(n + m) |
O(n + m) |
n = lähdekoodin pituus, m = suorituksen kustannus |
compile() |
O(n) |
O(n) |
Jäsennys sekä tavukoodin generointi |
globals() |
O(1) |
O(1) |
Palauttaa olemassa olevan moduulin sanakirjan |
locals() |
O(1) |
O(1) |
O(m) optimoiduissa funktioiden näkyvyysalueissa |
Syöte, tuloste ja virheenjäljitys
| Funktio |
Aika |
Tila |
Huomiot |
print() |
O(n) |
O(n) |
n = tulosteen kokonaispituus; I/O hallitsee kustannusta |
input() |
O(k) |
O(k) |
k = luetun rivin pituus |
open() |
O(1)* |
O(1) |
* järjestelmäkutsu; luku ja kirjoitus maksavat sen minkä siirtävät |
help() |
O(n) |
O(n) |
n = tarkasteltavan rajapinnan koko |
breakpoint() |
O(1) |
O(1) |
Luovuttaa hallinnan virheenjäljittimelle |
Vakiot
| Vakio |
Aika |
Tila |
Huomiot |
None |
O(1) |
O(1) |
Singleton; vertaa is-operaattorilla |
True |
O(1) |
O(1) |
Singleton-bool |
False |
O(1) |
O(1) |
Singleton-bool |
NotImplemented |
O(1) |
O(1) |
Operaattorit palauttavat tämän kieltäytyessään |
Ellipsis |
O(1) |
O(1) |
...-singleton |
__debug__ |
O(1) |
O(1) |
Sijoitetaan käännösaikana; -O poistaa sen suojaaman koodin |
Poikkeukset ja tulkki
Keskeiset käsitteet
Tasoitettu vaativuus
Joillakin operaatioilla, kuten list.append(), on tasoitettu O(1) -vaativuus. Tämä tarkoittaa:
- Useimmat append-operaatiot ovat O(1)
- Ajoittain tapahtuu koon muuttaminen, joka vaatii O(n)
- Monen operaation yli keskiarvo on O(1)
Laiska vs. ahne
Useat sisäänrakennetut funktiot palauttavat iteraattorin tuloksen sijaan. Niiden kutsuminen
on O(1) riippumatta syötteen koosta; varsinainen työ tapahtuu iteraattoria läpi käytäessä,
eikä sitä tehdä lainkaan ohitetuille alkioille. Kutsun kääriminen list()-funktioon tekee
siitä jälleen ahneen ja palauttaa O(n)-tilavaativuuden.
Toteutuksen yksityiskohdat
CPython käyttää:
- Listat: Dynaamisia taulukoita ylivarauksella
- Sanakirjat: Hajautustauluja avoimella osoituksella
- Joukot: Hajautustauluja (samaan tapaan kuin sanakirjat)
Versiohuomiot
Eri Python-versioissa on omat optimointinsa:
- Python 3.7+: Sanakirjan lisäysjärjestys taataan (kielimäärittely)
- Python 3.9+: Parannuksia uuteen sanakirjatoteutukseen
- Python 3.10+: Lisäoptimointeja yleisiin operaatioihin
Katso Versiot julkaisukohtaista muutoslokia varten.
Katso myös