Python: conta il numero di elementi nell'elenco per la condizione

Question

Dato un elenco di numeri interi, qual è il modo più Python/migliore per contare quanti elementi si trovano in un determinato intervallo?

ho ricercato e trovato 2 modi di farlo:

>>> x = [10, 60, 20, 66, 79, 5] 
>>> len([i for i in x if 60 < i < 70]) 
1 

o:

>>> x = [10, 60, 20, 66, 79, 5] 
>>> sum(1 for i in x if 60 < i < 70) 
1 

Quale metodo utilizza meno tempo/memoria (per le liste più grandi) e perché? O forse un altro modo è meglio ...

Answer 1

Il generatore di espressione è più memoria efficiente, perché non c'è bisogno di creare una lista supplementare.

Creare una lista e ottenere la sua lunghezza (quest'ultima è un'operazione O (1) molto veloce) sembra essere più veloce che creare un generatore e fare n aggiunte per elenchi relativamente piccoli.

In [13]: x = [1] 
In [14]: timeit len([i for i in x if 60 < i < 70]) 
10000000 loops, best of 3: 141 ns per loop 
In [15]: timeit sum(1 for i in x if 60 < i < 70) 
1000000 loops, best of 3: 355 ns per loop 
In [16]: x = range(10) 
In [17]: timeit len([i for i in x if 60 < i < 70]) 
1000000 loops, best of 3: 564 ns per loop 
In [18]: timeit sum(1 for i in x if 60 < i < 70) 
1000000 loops, best of 3: 781 ns per loop 
In [19]: x = range(50) 
In [20]: timeit len([i for i in x if 60 < i < 70]) 
100000 loops, best of 3: 2.4 µs per loop 
In [21]: timeit sum(1 for i in x if 60 < i < 70) 
100000 loops, best of 3: 2.62 µs per loop 
In [22]: x = range(1000) 
In [23]: timeit len([i for i in x if 60 < i < 70]) 
10000 loops, best of 3: 50.9 µs per loop 
In [24]: timeit sum(1 for i in x if 60 < i < 70) 
10000 loops, best of 3: 51.7 µs per loop 

ho provato con varie liste, ad esempio [65]*n e la tendenza non cambia. Per esempio:

In [1]: x = [65]*1000 
In [2]: timeit len([i for i in x if 60 < i < 70]) 
10000 loops, best of 3: 67.3 µs per loop 
In [3]: timeit sum(1 for i in x if 60 < i < 70) 
10000 loops, best of 3: 82.3 µs per loop 

Answer 2

Nei casi specifici hai presentato

[i for i in x if 60 < i < 70] 

in realtà genera una lista nuova di zecca, poi prende la sua len. Al contrario,

(1 for i in x if 60 < i < 70) 

è un generator expression su cui si prende una sum.

Per articoli rilevanti di dimensioni sufficienti, la seconda versione sarà più efficiente (in particolare in termini di memoria).

---

Tempi

x = [65] * 9999999 

%%time 

len([i for i in x if 60 < i < 70]) 

CPU times: user 724 ms, sys: 44 ms, total: 768 ms 
Wall time: 768 ms 
Out[7]: 
9999999 

%%time 

sum(1 for i in x if 60 < i < 70) 
CPU times: user 592 ms, sys: 0 ns, total: 592 ms 
Wall time: 593 ms 

Answer 3

si può facilmente verificare questo utilizzando il modulo timeit. Per il vostro esempio particolare, la prima soluzione basata su len sembra essere più veloce:

$ python --version 
Python 2.7.10 
$ python -m timeit -s "x = [10,60,20,66,79,5]" "len([i for i in x if 60 < i < 70])" 
1000000 loops, best of 3: 0.514 usec per loop 
$ python -m timeit -s "x = [10,60,20,66,79,5]" "sum(i for i in x if 60 < i < 70)" 
1000000 loops, best of 3: 0.693 usec per loop 

Anche per le liste più grandi - ma con la maggior parte degli elementi che non corrisponde alla predicato - appare la versione len di non essere più lenta:

$ python -m timeit -s "x = [66] + [8] * 10000" "len([i for i in x if 60 < i < 70])" 
1000 loops, best of 3: 504 usec per loop 
$ python -m timeit -s "x = [66] + [8] * 10000" "sum(1 for i in x if 60 < i < 70)" 
1000 loops, best of 3: 501 usec per loop 

infatti, anche se la maggior parte degli elementi della data partita lista (quindi un grande elenco dei risultati è costruito da passare al len), le vittorie len versione:

$ python -m timeit -s "x = [66] + [65] * 10000" "len([i for i in x if 60 < i < 70])" 
1000 loops, best of 3: 762 usec per loop 
$ python -m timeit -s "x = [66] + [65] * 10000" "sum(1 for i in x if 60 < i < 70)" 
1000 loops, best of 3: 935 usec per loop 

Tuttavia, ciò che sembra essere molto più veloce è non avere una lista in primo luogo, se possibile, ma piuttosto contenere per es. a collections.Counter. Per esempio.per 100000 elementi, ottengo:

$ python -m timeit -s "import collections; x = [66] + [65] * 100000" "len([i for i in x if 60 < i < 70])" 
100 loops, best of 3: 8.11 msec per loop 
$ python -m timeit -s "import collections; x = [66] + [65] * 100000; d = collections.Counter(x)" "sum(v for k,v in d.items() if 60 < k < 70)" 
1000000 loops, best of 3: 0.761 usec per loop