Complessità di len() per quanto riguarda i set e gli elenchi

Question

La complessità di len() per quanto riguarda i set e gli elenchi è ugualmente O (1). Come mai ci vuole più tempo per elaborare i set?

~$ python -m timeit "a=[1,2,3,4,5,6,7,8,9,10];len(a)" 
10000000 loops, best of 3: 0.168 usec per loop 
~$ python -m timeit "a={1,2,3,4,5,6,7,8,9,10};len(a)" 
1000000 loops, best of 3: 0.375 usec per loop 

E 'relativo al particolare punto di riferimento, come in, ci vuole più tempo per costruire i set di liste e il punto di riferimento prende in considerazione che pure?

Se la creazione di un oggetto impostato richiede più tempo rispetto alla creazione di un elenco, quale sarebbe la ragione sottostante?

Answer 1

In primo luogo, non si è misurata la velocità di len(), voi hanno misurato la velocità di creazione di un elenco/set insieme la velocità di len().

Utilizzare la --setup argomento timeit:

$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "len(a)" 
10000000 loops, best of 3: 0.0369 usec per loop 
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "len(a)" 
10000000 loops, best of 3: 0.0372 usec per loop 

Le dichiarazioni si passa a --setup è gestita prima di misurare la velocità di len().

In secondo luogo, si dovrebbe notare che len(a) è un'affermazione piuttosto veloce. Il processo di misurazione della sua velocità può essere soggetto a "rumore". Si consideri che the code executed (and measured) by timeit è equivalente alla seguente:

for i in itertools.repeat(None, number): 
    len(a) 

Poiché sia ​​len(a) e itertools.repeat(...).__next__() sono operazioni rapide e loro velocità possono essere simili, la velocità di itertools.repeat(...).__next__() può influenzare i tempi.

Per questo motivo, è meglio che misura len(a); len(a); ...; len(a) (ripetuto 100 volte o giù di lì) in modo che il corpo del ciclo for prende una considerevolmente maggiore quantità di tempo rispetto alla iteratore:

$ python -m timeit --setup "a=[1,2,3,4,5,6,7,8,9,10]" "$(for i in {0..1000}; do echo "len(a)"; done)" 
10000 loops, best of 3: 29.2 usec per loop 
$ python -m timeit --setup "a={1,2,3,4,5,6,7,8,9,10}" "$(for i in {0..1000}; do echo "len(a)"; done)" 
10000 loops, best of 3: 29.3 usec per loop 

(I risultati ancora dice che len() ha le stesse prestazioni su liste e gruppi, ma ora si è certi che il risultato è corretto.)

in terzo luogo, è vero che "complessità" e "velocità" sono correlati, ma ti credo stanno facendo un po 'di confusione Il fatto che len() abbia la complessità O (1) per elenchi e insiemi non implica che debba essere eseguito con la stessa velocità su elenchi e insiemi.

Significa che, in media, indipendentemente dalla lunghezza dell'elenco a, len(a) esegue lo stesso numero asintotico di passaggi. E non importa quanto sia lungo il set b, len(b) esegue lo stesso numero asintotico di passaggi. Ma l'algoritmo per calcolare la dimensione di liste e insiemi può essere diverso, con conseguenti prestazioni diverse (timeit indica che non è questo il caso, tuttavia questa potrebbe essere una possibilità).

Infine,

Se la creazione di un oggetto di serie richiede più tempo rispetto alla creazione di un elenco, quale sarebbe la ragione di fondo?

Un set, come sapete, non consente elementi ripetuti. Gli insiemi in CPython sono implementati come tabelle hash (per garantire l'inserimento medio e la ricerca O (1)): la costruzione e il mantenimento di una tabella hash è molto più complessa dell'aggiunta di elementi a un elenco.

In particolare, quando si costruisce un set, è necessario calcolare gli hash, compilare la tabella hash, cercarlo per evitare di inserire eventi duplicati e così via. Al contrario, gli elenchi in CPython sono implementati come una semplice matrice di puntatori che è malloc() ed e realloc() ed, se necessario.

Answer 2

Sì, hai ragione, è più a causa del diverso tempo richiesto per creare gli oggetti set e list da python. Come un punto di riferimento più giusto è possibile utilizzare il modulo timeit e passare gli oggetti utilizzando setup argomento:

from timeit import timeit 

print '1st: ' ,timeit(stmt="len(a)", number=1000000,setup="a=set([1,2,3]*1000)") 
print '2nd : ',timeit(stmt="len(a)", number=1000000,setup="a=[1,2,3]*1000") 

risultato:

1st: 0.04927110672 
2nd : 0.0530669689178 

E se volete sapere che perché è in questo modo, lascia passare attraverso il pitone mondo. In realtà, l'oggetto impostato utilizza un hash table e una tabella hash utilizza una funzione di hash per creare i valori hash degli elementi e associarli ai valori e in questo deal chiamando la funzione e calcolando i valori hash e qualche altro compito richiederà molto tempo. Mentre per creare una lista python basta creare una sequenza di oggetti a cui puoi accedere con l'indicizzazione.

È possibile controllare ulteriori dettagli sulla funzione set_lookkey da Cpython source code.

Si noti inoltre che se due algoritmi hanno la stessa complessità, ciò non significa che entrambi gli algoritmi abbiano esattamente lo stesso tempo di esecuzione o la velocità di esecuzione.

---

_{perché big O notazione descrive la limiting behavior of a function e non mostra l'equazione esatta complessità. Ad esempio la complessità delle seguenti equazioni f(x)=100000x+1 e f(x)=4x+20 è O (1) e significa che entrambe sono equazioni lineari, come si può vedere la prima funzione ha una pendenza molto più grande, e per uno stesso input daranno risultati diversi .}

Answer 3

rimuovere l'istruzione len(a). Il risultato è praticamente lo stesso. Un set deve essere sottoposto a hash per conservare solo elementi distinti, quindi è più lento.

Answer 4

Le linee rilevanti sono http://svn.python.org/view/python/trunk/Objects/setobject.c?view=markup#l640

640  static Py_ssize_t 
641  set_len(PyObject *so) 
642  { 
643   return ((PySetObject *)so)->used; 
644  } 

e http://svn.python.org/view/python/trunk/Objects/listobject.c?view=markup#l431

431  static Py_ssize_t 
432  list_length(PyListObject *a) 
433  { 
434   return Py_SIZE(a); 
435  } 

Entrambi sono solo una ricerca statica.

Quindi qual è la differenza che potresti chiedere. Misurate anche la creazione degli oggetti. Ed è un po 'più dispendioso in termini di tempo per creare un set di un elenco.

Answer 5

Utilizzare questo con la bandiera -s a timeit senza tenendo conto della prima stringa:

~$ python -mtimeit -s "a=range(1000);" "len(a)" 
10000000 loops, best of 3: 0.0424 usec per loop 
          ↑ 

---

~$ python -mtimeit -s "a={i for i in range(1000)};" "len(a)" 
10000000 loops, best of 3: 0.0423 usec per loop 
          ↑ 

Ora è solo considerando solo la funzione len, ed i risultati sono più o meno lo stesso dato che non abbiamo tenuto conto del tempo di creazione dell'insieme/lista.

Answer 6

Consentitemi di aggiungere le risposte eccellenti qui: O(1) parla solo dello order of growth in relazione alla dimensione dell'input.

O(1) in particolare significa solo costante di temporispetto alla dimensione di ingresso. Procedimento può sempre prendere 0.1s, per qualsiasi ingresso, e un altro può prendere 1000 anni per qualsiasi ingresso, e avevano entrambi essere O(1)

In questo caso, mentre la documentazione ha un certo grado di ambiguità, essa significa che il metodo impiega all'incirca lo per elaborare un elenco di dimensioni 1 come necessario per elaborare l'elenco delle dimensioni 1000; allo stesso modo, impiega lo stesso tempo per elaborare un dizionario di dimensioni 1 come necessario per elaborare un dizionario di dimensioni 1000.

Nessuna garanzia viene fornita in relazione a diversi tipi di dati.

Ciò non è sorprendente poiché l'implementazione di len() a un certo punto nello stack di chiamate può variare in base al tipo di dati.

Incidentalmente, questa ambiguità viene eliminata in lingue staticamente tipizzati dove ClassA.size() e ClassB.size() sono a tutti gli effetti e purpouses due metodi differenti.

Answer 7

Molti hanno notato che O (1) non si tratta di prestazioni su diversi tipi di dati , ma sulle prestazioni in funzione della diversa ingresso dimensioni.

Se stai cercando di testare O (1) -ness, devi essere alla ricerca di qualcosa di più simile

~$python -m timeit --setup "a=list(range(1000000))" "len(a)" 
10000000 loops, best of 3: 0.198 usec per loop 

~$python -m timeit --setup "a=list(range(1))" "len(a)" 
10000000 loops, best of 3: 0.156 usec per loop 

Grandi dati o pochi dati, il tempo impiegato è abbastanza simile. Per gli altri post, questo separa i tempi di configurazione dal tempo di test, ma non arriva a ridurre il rumore di len-time rispetto al tempo di ciclo.