<div dir="ltr"><br><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">> se sei sicuro che la seconda lista avrà N elementi allora puoi già creare<br>

> una lista con dei None, così risparmi sia memoria (visto che None è un<br>
> singleton) e ti eviti l'append che fa vari reallocazioni di memoria.<br>
<br>
Ma no, dai. Pre-allocare le liste in Python e' un anti-pattern.<br></blockquote><div><br></div><div>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.<br>
</div>
<br><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">
Tra l'altro, append non fa "varie riallocazioni". E' fatto per darti linear<br>
amortized time su tante append, quindi complessivamente non funziona male.<br>
In pratica append e' fatto in modo da richiedere "un po' piu' memoria" di quella<br>
necessaria, per cui, di fatto, non riallochi ad ogni append.<br></blockquote><div><br></div><div>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)?<br>
<br><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">La cosa ottimale e' comunque costruire direttamente la lista con una bella<br>
list comprehension.</blockquote><div><br></div><div>In questo caso come fai a costruire una lista con il list-comprehension visto che non hai l'ordine degli elementi? <br><br><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">
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.</blockquote><div><br></div><div>In questo caso allora il discorso cambia e il dizionario diventa una buona scelta per una lista "molto molto sparsa"<br><br><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">
<div>A questo punto ho un po' di domande.</div><div> - La complessità non dipende dall'implementazione piuttosto che dall'interfaccia? <br></div></blockquote><div>Se l'interfaccia indica anche quale complessità dovrebbe fornire allora diventa parse del "contratto" tra chi usa l'implementazione e chi la fornisce.<br>
</div><div>Un esempio stupido, se fornisco un'interfaccia Array, allora mi aspetto che le implementazioni forniscano un inserimento in O(1).<br><br></div><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">


<div> - Il concetto di lista di per sè non è limitato ad una struttura che espone una sequenza ordinata di elementi?</div></blockquote><div> </div><div>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.<br>
<br></div><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote"><div> -
 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?</div></blockquote><br></div><div>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.<br>
</div></div></div></div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/6/22 Nadir Sampaoli <span dir="ltr"><<a href="mailto:nadirsampaoli@gmail.com" target="_blank">nadirsampaoli@gmail.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Il giorno 22 giugno 2013 11:06, enrico franchi ha scritto:<div class="gmail_extra"><div class="gmail_quote">
<div class="im"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">

Senti, hanno chiamato list qualcosa che si comporta come un array<br>
estensibile (o vector, per dirla con C++) e che delle liste non e'<br>
manco parente, visto che ha tutte le complessita' computazionali<br>
'sbagliate'.<br>
<br>
Nota bene, hash-map e' un modo di implementare la struttura dati<br>
astratta nota come array associativo (o map o dictionary).<br>
Quindi dictionary e' solo uno dei nomi con cui quel tipo di struttura<br>
e' chiamata. Hash Map e' una possibile famiglia di implementazioni.</blockquote><div><br></div></div><div>A questo punto ho un po' di domande.</div><div> - La complessità non dipende dall'implementazione piuttosto che dall'interfaccia?</div>


<div> - Il concetto di lista di per sè non è limitato ad una struttura che espone una sequenza ordinata di elementi?</div><div> - 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?</div>


<div><br></div><div>--</div><div>Nadir</div></div>
</div></div>
<br>_______________________________________________<br>
Python mailing list<br>
<a href="mailto:Python@lists.python.it">Python@lists.python.it</a><br>
<a href="http://lists.python.it/mailman/listinfo/python" target="_blank">http://lists.python.it/mailman/listinfo/python</a><br>
<br></blockquote></div><br><br clear="all"><br>-- <br><div dir="ltr"><div style="text-align:right"><font color="#333333" face="trebuchet ms, sans-serif"><i><b>Federico Figus</b></i></font></div></div>
</div>