<div dir="ltr"><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">in python 2.7+ c'e' il modulo collections che contiene OrderedDict: la versione ordinata di un dizionario.<br>
per versioni di python (2.6, 2.5 etc.) Nicola Larosa ha creato un backport (da qualche parte nella rete).</blockquote><div><br></div><div>In questo caso non servono perchè:<br><br><blockquote style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex" class="gmail_quote">
An <em>OrderedDict</em> is a dict that remembers the order that keys
were first inserted. If a new entry overwrites an existing entry, the
original insertion position is left unchanged. Deleting an entry and
reinserting it will move it to the end. </blockquote><div><a href="http://docs.python.org/2/library/collections.html#collections.OrderedDict">http://docs.python.org/2/library/collections.html#collections.OrderedDict</a> <br>
<br></div><div>Però sarebbe un'idea (ed un'ottmo esercizio) implementare qualcosa di simile a quello che intendevi, cioè avere un ordine interno delle chiavi basato su __cmp__.<br></div></div></div><div class="gmail_extra">
<br><br><div class="gmail_quote">2013/6/22 Federico Figus <span dir="ltr"><<a href="mailto:figus.federico@gmail.com" target="_blank">figus.federico@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"><div class="im"><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><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><div class="im">
<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><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)?<div class="im">
<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><div>In questo caso come fai a costruire una lista con il list-comprehension visto che non hai l'ordine degli elementi? <br><div class="im"><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><div>In questo caso allora il discorso cambia e il dizionario diventa una buona scelta per una lista "molto molto sparsa"<div class="im"><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><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><div class="im"><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><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><div class="im"><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><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><div class="h5"><div dir="ltr">Il giorno 22 giugno 2013 11:06, enrico franchi ha scritto:<div class="gmail_extra">
<div class="gmail_quote">
<div><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></div></div><div class="im">_______________________________________________<br>
Python mailing list<br>
<a href="mailto:Python@lists.python.it" target="_blank">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></div></blockquote></div><span class="HOEnZb"><font color="#888888"><br><br clear="all"><br>-- <br><div dir="ltr"><div style="text-align:right"><font face="trebuchet ms, sans-serif" color="#333333"><i><b>Federico Figus</b></i></font></div>
</div>
</font></span></div>
</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>