Jaki jest koszt len()
funkcji wbudowanych w Python? (lista / krotka / ciąg / słownik)
290
Jaki jest koszt len()
funkcji wbudowanych w Python? (lista / krotka / ciąg / słownik)
Jest to O (1) (stały czas, niezależny od rzeczywistej długości elementu - bardzo szybko) na każdym typie, o którym wspomniałeś, plus set
i inne takie jak array.array
.
Wywołanie len () na tych typach danych to O (1) w CPython , najczęstszej implementacji języka Python. Oto link do tabeli, która zapewnia złożoność algorytmiczną wielu różnych funkcji w CPython:
TimeComplexity Python Wiki Wiki
źródło
Wszystkie te obiekty śledzą własną długość. Czas na wyodrębnienie długości jest niewielki (O (1) w notacji wielkiej-O) i składa się głównie z [przybliżonego opisu, napisanego w języku Python, a nie w języku C]: wyszukaj „len” w słowniku i wyślij go do wbudowana funkcja len, która wyszukuje
__len__
metodę obiektu i wywołuje to ... wszystko, co musi zrobić, toreturn self.length
źródło
length
pojawia się w słowniku wedługdir(list)
?list.lenght
zmienna jest zaimplementowana w języku C, a nie w języku Python.Poniższe pomiary dostarczają dowodów, że
len()
O (1) dla często używanych struktur danych.Uwaga dotycząca
timeit
: Gdy-s
flaga jest używana i dwa łańcuchy są przekazywane dotimeit
pierwszego łańcucha, jest wykonywana tylko raz i nie jest mierzona w czasie.Lista:
Krotka:
Strunowy:
Słownik (rozumienie słownika dostępne w wersji 2.7+):
Szyk:
Zestaw (kompletny opis dostępny w wersji 2.7+):
Deque:
źródło
len()
, a także naprawiłem pomiary, aby poprawnie używać-s
flagi.python -m timeit -s "l = range(10000);" "len(l); len(l); len(l)"
223 ns na pętlępython -m timeit -s "l = range(100);" "len(l)"
66,2 ns na pętlęlen to O (1), ponieważ w pamięci RAM listy są przechowywane jako tabele (serie ciągłych adresów). Aby wiedzieć, kiedy stół się zatrzymuje, komputer potrzebuje dwóch rzeczy: długości i punktu początkowego. Dlatego len () to O (1), komputer przechowuje wartość, więc musi ją tylko sprawdzić.
źródło
Myślałem o len () w Python zależy od wielkości listy, więc zawsze przechowuję długość w zmiennej, jeśli używam wiele razy. Ale dzisiaj podczas debugowania zauważyłem atrybut __len__ w obiekcie listy, więc len () musi go tylko pobierać, co komplikuje O (1). Właśnie google, jeśli ktoś już o to zapytał i natknął się na ten post.
źródło
__len__
jest funkcją, a nie zmienną reprezentującą długość listy.list.__len__
funkcja działa w stałym czasie? Tak, ale nie tylko dlatego, że jest funkcją. Ponieważ tak to zaimplementowano.