[Python] Dubbio sull'uso delle liste...

[Enrico Franchi]

On Jun 22, 2013, at 12:10 PM, Federico Figus <figus.federico a gmail.com> wrote:

> 
> > se sei sicuro che la seconda lista avrà N elementi allora puoi già creare
> > una lista con dei None, così risparmi sia memoria (visto che None è un
> > singleton) e ti eviti l'append che fa vari reallocazioni di memoria.
> 
> Ma no, dai. Pre-allocare le liste in Python e' un anti-pattern.
> 
> Nel caso conoscessi a priori le dimensioni dell'array che andrò a riempire perchè avere già un array pronto sarebbe un anti-pattern? Quali sono secoondo te i difetti di questo approccio? Perchè in molto algoritmi con queste precondizioni si preferisce creare precedentemente la lista di destinazione.
> 

Distinguiamo due casi radicali. Quello in cui sto usando numpy e quello in cui non sto
usando numpy. Per una serie di ragioni quello che suggerisci con numpy *a volte* lo faccio.
Ma anche li non sempre.

In generale in Python non si fanno le pre-dichiarazioni.

Comunque io invece di:

foo = [None, ] * size
for i, x in enumerate(some_iterable):
    foo[i] = process(i, x)

o peggio ancora ad affari come

foo = [None, ] * size
for i in xrange(i):
   foo[i] = process(i, some_list[i])

o "peggierrimo"

foo = [None, ] * size
i = 0
while i < size:
    foo[i] = process(i, some_list[i])
    i += 1


consiglio

foo = [process(*t) for t in enumerate(some_iterable)]


Le list comprehension sono troppo comode e troppo belle per non usarle
per questo tipo di cose. Hanno meno rumore visivo, e' piu' chiaro il loro intento.

> 
> Si, conosco la tecnica utilizzata da python, se devi fari vari append e remove è buona e ti riduce le operazioni in memoria, ma se sai che avrai una lista di N elementi perchè passare per i vari passi intermedi e fargli fare sono un allocamento (che comporterà sempre l'utilizzo del linear-time amortized)?

1. Perche' non ti sto suggerendo di fare append
2. Perche' pre-allocare non e' particolarmente piu' efficiente

In [8]: %%timeit
l = [None, ] * 10000
for i in xrange(10000):
    l[i] = math.sin(i)
   ...:
100 loops, best of 3: 2.38 ms per loop

In [9]: %%timeit
   ...: l = []
   ...: for i in xrange(10000):
   ...:     l.append(math.sin(i))
   ...:
100 loops, best of 3: 2.92 ms per loop

In [10]: %%timeit
   ....: l = [math.sin(i) for i in xrange(10000)]
   ....:
100 loops, best of 3: 1.86 ms per loop


> La cosa ottimale e' comunque costruire direttamente la lista con una bella
> list comprehension.
> 
> In questo caso come fai a costruire una lista con il list-comprehension visto che non hai l'ordine degli elementi? 

Non mi e' chiaro che tipo di problema possa essere risolto (anche in maniera subottimale) pre-allocando
una lista di None e non con una list-comprehension salvo uno che "lasci" dei buchi nella lista.

Ora siccome trovo un incubo assoluto l'idea di avere una lista con dentro un po' di None e un po' di oggetti (altro anti-pattern,
almeno confrontare con NullObjectPattern se uno proprio vuole fare una cosa del genere), questo caso non mi
viene da considerarlo.

Questo caso, ovvero una lista con "buchi" e' strutturalmente meglio gestito da un dizionario (come sembra esserci
consenso). E ovviamente, dict-comprehensions!


> Un esempio stupido, se fornisco un'interfaccia Array, allora mi aspetto che le implementazioni forniscano un inserimento in O(1).

Non conosco nessun array che ti consenta questo. Quello che puoi fare e' una scrittura in O(1), ma l'inseriemento in un array (salvo che in coda) e' notoriamente costoso. Ci sono alcune operazioni che ti danno un O(log(n)) con una base del logaritmo piuttosto grossa, tuttavia. Ma e' robba un po' esotica.

> 
>  - Il concetto di lista di per sè non è limitato ad una struttura che espone una sequenza ordinata di elementi?
>  
> Si, è una struttura che ti permette di inserire, rimuovere e recuperare elementi in varie posizioni, solitamente i metodi forniti sono size o length, insert, remove, get.

Non direi. Cioe' Java ce li mette, ma di per se su una lista hai qualcosa per creare la vuota, testare se e' vuota, cons, tail, head, magari un qualche tipo di append.

> 
>  - Che (tanto per dire) rimuovere un elemento abbia complessità media O(N) invece che O(1) perchè incapsula un'array invece di una linked list non dovrebbe essere disgiunto dall'«interfaccia» lista?
> 
> In questo caso dipende anche da come la intendi e da come la documenti, diciamo che le interfacce arrivano ad un certo punto, poi sta al buon senso del programmatore agire coerentemente con l'interfaccia.

Diciamo che questa parte di informatica era ben studiata ben prima della moda della programmazione ad oggetti. Quando ancora si parlava solo di strutture dati astratti (che erano concetti nati appunto all'interno della comunita' di algoritmisti) qualche discorso sulla complessità delle operazioni fondamentali era proprio *parte* della definizione di tipo di dato astratto. 

Questo e' proprio uno dei casi in cui la semplice definizione dei tipi e' completamente insufficiente per una buona caratterizzazione del tutto. 
Per esempio, la sostituibilita' secondo Liskov non ha veramente un modo per dire che la complessita' computazionale rende due strutture non sostituibili. Ora *tecnicamente* nessun formalismo *concreto* consente questo. Ma vista la pretesa di universalita' della programmazione ad oggetti trovo piu' seccante la cosa. 

Pero' si, resta il fatto che puoi formalmente documentare la complessita' algoritmica nell'interfaccia. Ma e' qualcosa di drammaticamente ambiguo. Per esempio non hai veramente un modo di fare un unit test che controlli la proprieta'. E' in qualche modo una proprieta' che non e' realmente esprimibile nel mondo in cui ci si muove.


-enrico