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

[Federico Figus]

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

Tra l'altro, append non fa "varie riallocazioni". E' fatto per darti linear
> amortized time su tante append, quindi complessivamente non funziona male.
> In pratica append e' fatto in modo da richiedere "un po' piu' memoria" di
> quella
> necessaria, per cui, di fatto, non riallochi ad ogni append.
>

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)?

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?

Dopo alcune valutazioni i dict sono la soluzione perfetta per quello che
> devo fare, sopratutto in prospettiva, quando l'elaborazione sarà parallela
> con più processi.


In questo caso allora il discorso cambia e il dizionario diventa una buona
scelta per una lista "molto molto sparsa"

A questo punto ho un po' di domande.
>  - La complessità non dipende dall'implementazione piuttosto che
> dall'interfaccia?
>
Se l'interfaccia indica anche quale complessità dovrebbe fornire allora
diventa parse del "contratto" tra chi usa l'implementazione e chi la
fornisce.
Un esempio stupido, se fornisco un'interfaccia Array, allora mi aspetto che
le implementazioni forniscano un inserimento in O(1).

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

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


2013/6/22 Nadir Sampaoli <nadirsampaoli a gmail.com>

> Il giorno 22 giugno 2013 11:06, enrico franchi ha scritto:
>
>> Senti, hanno chiamato list qualcosa che si comporta come un array
>> estensibile (o vector, per dirla con C++) e che delle liste non e'
>> manco parente, visto che ha tutte le complessita' computazionali
>> 'sbagliate'.
>>
>> Nota bene, hash-map e' un modo di implementare la struttura dati
>> astratta nota come array associativo (o map o dictionary).
>> Quindi dictionary e' solo uno dei nomi con cui quel tipo di struttura
>> e' chiamata. Hash Map e' una possibile famiglia di implementazioni.
>
>
> A questo punto ho un po' di domande.
>  - La complessità non dipende dall'implementazione piuttosto che
> dall'interfaccia?
>  - Il concetto di lista di per sè non è limitato ad una struttura che
> espone una sequenza ordinata di elementi?
>  - 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?
>
> --
> Nadir
>
> _______________________________________________
> Python mailing list
> Python a lists.python.it
> http://lists.python.it/mailman/listinfo/python
>
>


-- 
*Federico Figus*
-------------- parte successiva --------------
Un allegato HTML è stato rimosso...
URL: <http://lists.python.it/pipermail/python/attachments/20130622/97a75aaa/attachment.html>