Koszt funkcji len ()

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 seti 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

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

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

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

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.