Koszt funkcji len ()

Odpowiedzi:

341

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 seti inne takie jak array.array.

Alex Martelli
źródło
17
Dziękuję za pomocną odpowiedź! Czy są jakieś rodzime typy, dla których tak nie jest?
mvanveen
141

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

James Thompson
źródło
84

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

John Machin
źródło
3
Myślę, że jest to najbardziej odpowiednia odpowiedź, ponieważ daje wgląd w szczegóły implementacji.
AK
dlaczego nie lengthpojawia się w słowniku według dir(list)?
ViFI
tego właśnie szukałem
Visakh Vijayan
@ViFI Ponieważ to tylko przykład. Zilustrowana list.lenghtzmienna jest zaimplementowana w języku C, a nie w języku Python.
Kowalski
73

Poniższe pomiary dostarczają dowodów, że len()O (1) dla często używanych struktur danych.

Uwaga dotycząca timeit: Gdy -sflaga jest używana i dwa łańcuchy są przekazywane do timeitpierwszego łańcucha, jest wykonywana tylko raz i nie jest mierzona w czasie.

Lista:

$ python -m timeit -s "l = range(10);" "len(l)"
10000000 loops, best of 3: 0.0677 usec per loop

$ python -m timeit -s "l = range(1000000);" "len(l)"
10000000 loops, best of 3: 0.0688 usec per loop

Krotka:

$ python -m timeit -s "t = (1,)*10;" "len(t)"
10000000 loops, best of 3: 0.0712 usec per loop

$ python -m timeit -s "t = (1,)*1000000;" "len(t)"
10000000 loops, best of 3: 0.0699 usec per loop

Strunowy:

$ python -m timeit -s "s = '1'*10;" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

$ python -m timeit -s "s = '1'*1000000;" "len(s)"
10000000 loops, best of 3: 0.0686 usec per loop

Słownik (rozumienie słownika dostępne w wersji 2.7+):

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(10))};" "len(d)"
10000000 loops, best of 3: 0.0711 usec per loop

$ python -mtimeit -s"d = {i:j for i,j in enumerate(range(1000000))};" "len(d)"
10000000 loops, best of 3: 0.0727 usec per loop

Szyk:

$ python -mtimeit -s"import array;a=array.array('i',range(10));" "len(a)"
10000000 loops, best of 3: 0.0682 usec per loop

$ python -mtimeit -s"import array;a=array.array('i',range(1000000));" "len(a)"
10000000 loops, best of 3: 0.0753 usec per loop

Zestaw (kompletny opis dostępny w wersji 2.7+):

$ python -mtimeit -s"s = {i for i in range(10)};" "len(s)"
10000000 loops, best of 3: 0.0754 usec per loop

$ python -mtimeit -s"s = {i for i in range(1000000)};" "len(s)"
10000000 loops, best of 3: 0.0713 usec per loop

Deque:

$ python -mtimeit -s"from collections import deque;d=deque(range(10));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop

$ python -mtimeit -s"from collections import deque;d=deque(range(1000000));" "len(d)"
100000000 loops, best of 3: 0.0163 usec per loop
mięso_mechaniczne
źródło
1
Nie jest to tak dobry poziom odniesienia, mimo że pokazuje to, co już wiemy. Wynika to z faktu, że zakres (10) i zakres (1000000) nie powinien być O (1).
Nieznany
3
To zdecydowanie najlepsza odpowiedź. Powinieneś po prostu dodać wniosek na wypadek, gdyby ktoś nie zdawał sobie sprawy z ciągłego czasu.
Santiagobasulto
4
Dziękuję za komentarz. Dodałem notatkę o złożoności O (1) len(), a także naprawiłem pomiary, aby poprawnie używać -sflagi.
Mechanical_meat
Należy zauważyć, że zapisanie długości w zmiennej może zaoszczędzić znaczną ilość czasu obliczeniowego: 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ę
Radostin Stoyanov
16

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ć.

RAHUL KUMAR
źródło
3

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.

AYUSH SENAPATI
źródło
Ale __len__jest funkcją, a nie zmienną reprezentującą długość listy.
Kowalski
@Kowalski tak len jest funkcją, ale wszystko, co robi, to zwraca self.length
AYUSH SENAPATI
Ale twój post nic o tym nie mówi. A skąd wiesz, że ta list.__len__funkcja działa w stałym czasie? Tak, ale nie tylko dlatego, że jest funkcją. Ponieważ tak to zaimplementowano.
Kowalski