Topic: List comprehension vs map e filter  (Letto 95 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline Trizio

  • python unicellularis
  • *
  • Post: 40
  • Punti reputazione: 1
    • Mostra profilo
List comprehension vs map e filter
« il: Dicembre 06, 2018, 12:44 »
Una normale list comprehension:

>>> foo = [i * 10 for i in (1, 2, 3)]


Map:

>>> foo = map(lambda i: i * 10, (1, 2, 3))


List comprehension con if test:

>>> foo = [i for i in range(1, 11) if i % 2 == 0]


Filter:

>>> foo = filter(lambda i: i % 2 == 0, range(1, 11))


In Python 3, map e filter ritornano sequenze virtuali. Ora, se ho bisogno di una lista, il problema non si pone: mi conviene usare una list comprehension.

Supponiamo invece che io abbia bisogno solo di un iterable, non mi importa se una sequenza fisica o virtuale; in questo caso, quale approccio conviene? Il Lutz non è particolarmente chiaro. La list comprehension è veloce, perché ogni iterazione è eseguita alla velocità del linguaggio C (parole del Lutz, eh). map e filter, d’altro canto, creano sequenze virtuali che occupano la memoria poco alla volta. Se io ho una sequenza di oggetti particolarmente massiccia, suppongo che map e filter siano più convenienti.

Offline bebo

  • python erectus
  • ***
  • Post: 173
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re:List comprehension vs map e filter
« Risposta #1 il: Dicembre 06, 2018, 15:26 »
Non ho mai letto il Lutz, davvero chiama/traduce i generatori con il termine "sequenza virtuale"? Perche' e' la prima volta che lo sento, e non mi pare una traduzione felice. Anche "sequenza fisica" mi sa di nuovo.

Inoltre, sai che se anziche' usare delle parentesi quadre nella list-comprehension, metti delle parentesi tonde, diventa un generator comprehension?

Per quanto riguarda il cosa usare: dipende dall'idioma che usi nel tuo lavoro/azienda, e da come sei abituato a lavorare in altri linguaggi (ultimamente sta tornando di moda la functional programming --> map/filter/etc).
In generale in python si preferisce usare delle list comprehension perche' sono piu' "pulite" e piu' chiare per il pythonista medio.
Qui c'e' un bel thread su SO, con risposte interessanti e anche dei benchmarks: https://stackoverflow.com/a/1247490/

L'idea e' che se sull'oggetto che ti viene tornato devi fare delle operazioni (inserimento, manipolazioni varie), probabilmente conviene usare delle list-comprehension;
se devi solo iterarci, vai sempre di generatori/map/filter: sono molto piu' veloci (non devi mettere in memoria nulla -- e la memoria e' generalmente piu' lenta della cpu/cores). Inoltre non sempre puoi mettere tutta una lista in memoria (es. [a for a in range(10000000000)] probabilmente verra' killato dal tuo OS).

Offline Trizio

  • python unicellularis
  • *
  • Post: 40
  • Punti reputazione: 1
    • Mostra profilo
Re:List comprehension vs map e filter
« Risposta #2 il: Dicembre 06, 2018, 16:57 »
Non ho mai letto il Lutz, davvero chiama/traduce i generatori con il termine "sequenza virtuale"? Perche' e' la prima volta che lo sento, e non mi pare una traduzione felice. Anche "sequenza fisica" mi sa di nuovo.

Nel capitolo "Iterations and Comprehensions" introduce il concetto di oggetti iterabili:

Citazione
The concept of "iterable objects" [...] has come to permeate the language's design. It's essentially a generalization of the notion of sequences—an object is considered iterable if it is either a phisically stored sequence, or an object that produces one result at a time in the context of an iteration tool like a for loop. In a sense, iterable objects include both physical sequences and virtual sequences computed on demand.

Qui e solo qui fa riferimento a map, zip e filter come sequenze virtuali.

Inoltre, sai che se anziche' usare delle parentesi quadre nella list-comprehension, metti delle parentesi tonde, diventa un generator comprehension?

Sì. Nel senso che ho intravisto la cosa nel pocket reference (i generatori sono affrontati più avanti). Ma... in effetti, mi hai messo una pulce nell'orecchio. Dal punto di vista delle performance, che differenza c'è tra generator expressions e map/filter?

Per quanto riguarda il cosa usare: dipende dall'idioma che usi nel tuo lavoro/azienda, e da come sei abituato a lavorare in altri linguaggi (ultimamente sta tornando di moda la functional programming --> map/filter/etc).
In generale in python si preferisce usare delle list comprehension perche' sono piu' "pulite" e piu' chiare per il pythonista medio.
Qui c'e' un bel thread su SO, con risposte interessanti e anche dei benchmarks: https://stackoverflow.com/a/1247490/

L'idea e' che se sull'oggetto che ti viene tornato devi fare delle operazioni (inserimento, manipolazioni varie), probabilmente conviene usare delle list-comprehension;
se devi solo iterarci, vai sempre di generatori/map/filter: sono molto piu' veloci (non devi mettere in memoria nulla -- e la memoria e' generalmente piu' lenta della cpu/cores). Inoltre non sempre puoi mettere tutta una lista in memoria (es. [a for a in range(10000000000)] probabilmente verra' killato dal tuo OS).

Dunque il vantaggio di map/filter è dato dal non sovraccaricare la RAM. Ma lo stesso si può ottenere in modo pythonico con una generator expression. O no?

Offline bebo

  • python erectus
  • ***
  • Post: 173
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re:List comprehension vs map e filter
« Risposta #3 il: Dicembre 06, 2018, 23:59 »
Citazione
Nel capitolo "Iterations and Comprehensions" introduce il concetto di oggetti iterabili:

Citazione
The concept of "iterable objects" [...] has come to permeate the language's design. It's essentially a generalization of the notion of sequences—an object is considered iterable if it is either a phisically stored sequence, or an object that produces one result at a time in the context of an iteration tool like a for loop. In a sense, iterable objects include both physical sequences and virtual sequences computed on demand.

Okay, quindi con "physical sequence" intende "salvato in memoria", e con "virtual sequence" intende un qualcosa non salvato.. Mah, forse l'avrei spiegato piu' esplicitamente. In ogni caso, fatti un favore, e chiamali iteratori, non sequenze virtuali: penso che potrebbe generare confusione come successo a me.

Forse ti manca un dettaglio: come dice anche la doc (https://docs.python.org/3/library/functions.html#filter o help(filter) in un terminale) map/filter/zip/range (da python3) sono degli iteratori, che sono degli oggetti diverse da una lista.


>>> foo = [i * 10 for i in (1, 2, 3)]
>>> foo.__next__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AttributeError: 'list' object has no attribute '__next__'

>>> foo2 = filter(lambda i: i % 2 == 0, range(1, 11))
>>> foo2
<filter object at 0x7f20c3a7a940>
>>> foo2.__next__
<method-wrapper '__next__' of filter object at 0x7f20c3a7a940>
>>> foo2.__next__()
2
>>> foo2.__next__()
4
...
>>> foo2.__next__()
10
>>> foo2.__next__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>> foo2.__next__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration

>>> foo3 = (i for i in range(1, 11) if i % 2 == 0)
>>> foo3.__next__()
2
>>> foo3.__next__()
4
>>> foo3.__next__()
6
>>> foo3.__next__()
8
>>> foo3.__next__()
10
>>> foo3.__next__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration
>>> foo3.__next__()
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
StopIteration


Come vedi, foo2, che e' un iteratore, ogni volta che chiami il suo metodo speciale __next__(), ti ritorna il prossimo elemento che contiene, fino a che non e' esaurito, e poi nient'altro; quello che hai visto passare non c'e' piu' (a meno di non ricreare l'iteratore ovviamente).
Questo e' il motivo per cui se si usano iteratori si va davvero veloci anche in python.
foo3 invece e' un generatore, che non e' altro che un iteratore: se hai capito gli iteratori hai gia' probabilmente capito i generatori: dai un occhio a questi thread molto interessanti: https://stackoverflow.com/a/1756156/ e https://stackoverflow.com/questions/2776829/difference-between-pythons-generators-and-iterators.
In pratica i generatori sono un modo molto piu' pratico di implementare/istanziare un iteratore. Anziche' scrivere un oggetto con i metodi __iter__ e __next__, butti uno yield dentro ad una funzione, e quella diventa un generatore, cioe' un oggetto il cui "stato di esecuzione" viene messo in pausa e ripreso ad ogni richiesta di __next__.

Tornando al tuo thread iniziale: una list-comprehension ti genera una lista, che devi mettere in memoria (e i tempi di scrittura in ram sono alti); map/filter/range/zip sono degli iteratori, che quindi dinamicamente ti ritornano l'elemento seguente, senza memorizzare tutta la lista; i generatori sono anch'essi degli iteratori, quindi come prestazione vale il discorso fatto per map/filter; i generator-comprehension (o generator expression) sono un modo spesso piu' elegante per fare lo stesso lavoro di map/filter (come prestazioni vedi il link che ho messo sopra), e molti sviluppatori python li apprezzano.

Ah, ultima cosa: puoi trasformare un generator-comprehension in una list-comprehension mettendoci attorno una chiamata a list().

PS: non sbatterci troppo la testa all'inizio su cosa usare tra list e generator; questa e' una citazione di Donald Knuth: https://en.wikipedia.org/wiki/Program_optimization#When_to_optimize
Citazione
"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%"

Offline GlennHK

  • python sapiens sapiens
  • ******
  • Post: 1.637
  • Punti reputazione: 1
    • Mostra profilo
    • La Tana di GlennHK
Re:List comprehension vs map e filter
« Risposta #4 il: Dicembre 07, 2018, 09:02 »
Sono abbastanza sicuro che fino a qualche tempo fa map e filter a livello di performance battessero le comprehension perché l'iterazione è fatta in C anziché in python, ora non so se è cambiato qualcosa.


C'è anche da dire però che è sia più scomodo che meno leggibile usare map e filter, a meno di casi semplici come



" ".join(map(str, ints))

Offline bebo

  • python erectus
  • ***
  • Post: 173
  • Punti reputazione: 0
    • Mostra profilo
    • bebo_sudo's personal homepage
Re:List comprehension vs map e filter
« Risposta #5 il: Dicembre 07, 2018, 10:55 »
Dipende dal tipo di funzione usata, se usi una lambda e' meglio la list-comp, se usi una funzione definita e' meglio map.

Questo e' un thread interessante che ho gia' citato sopra: https://stackoverflow.com/a/1247490/
Qui Alex Martelli fa un semplice benchmark (immagino sia python2, dato che era il 2009, ormai 10 anni fa).
Ho provato a rifarli sul mio pc, usando python2.7.15:

[bebo@albtop]$ python -mtimeit -s'xs=range(10)' 'map(hex, xs)'
1000000 loops, best of 3: 1.18 usec per loop
[bebo@albtop]$ python -mtimeit -s'xs=range(10)' '[hex(x) for x in xs]'
1000000 loops, best of 3: 1.27 usec per loop

[bebo@albtop]$ python -mtimeit -s'xs=range(10)' 'map(lambda x: x+2, xs)'
1000000 loops, best of 3: 1.48 usec per loop
[bebo@albtop]$ python -mtimeit -s'xs=range(10)' '[x+2 for x in xs]'
1000000 loops, best of 3: 0.64 usec per loop

Che conferma i tempi trovati da Alex 10 anni fa.

Con python3 il confronto non sarebbe fair, in quanto map ora torna un iterabile, mentre la list-comp sempre una lista, e la prima non sarebbe mai valutata, mentre la seconda si.
Ho modificato i test trasformando il risultato in una lista, e usando non piu' una list-comp ma un generator-comp/generator expression, in modo da confrontare sempre degli iteratori:

[bebo@albtop]$ python3 -mtimeit -s'xs=range(10)' 'list(map(hex, xs))'
200000 loops, best of 5: 1.14 usec per loop
[bebo@albtop]$ python3 -mtimeit -s'xs=range(10)' 'list(hex(x) for x in xs)'
100000 loops, best of 5: 2.05 usec per loop

[bebo@albtop]$ python3 -mtimeit -s'xs=range(10)' 'list(map(lambda x: x+2, xs))'
200000 loops, best of 5: 1.44 usec per loop
[bebo@albtop]$ python3 -mtimeit -s'xs=range(10)' 'list(x+2 for x in xs)'
200000 loops, best of 5: 1.23 usec per loop


Convertendo in una tuple, si guadagna davvero poco:

[bebo@albtop]$ python3 -mtimeit -s'xs=range(10)' 'tuple(map(hex, xs))'
200000 loops, best of 5: 1.09 usec per loop
[bebo@albtop]$ python3 -mtimeit -s'xs=range(10)' 'tuple(hex(x) for x in xs)'
200000 loops, best of 5: 1.97 usec per loop

[bebo@albtop]$ python3 -mtimeit -s'xs=range(10)' 'tuple(map(lambda x: x+2, xs))'
200000 loops, best of 5: 1.41 usec per loop
[bebo@albtop]$ python3 -mtimeit -s'xs=range(10)' 'tuple(x+2 for x in xs)'
200000 loops, best of 5: 1.24 usec per loop