> > in python 2.7+ c'e' il modulo collections che contiene OrderedDict: la > versione ordinata di un dizionario. > per versioni di python (2.6, 2.5 etc.) Nicola Larosa ha creato un backport > (da qualche parte nella rete).
In questo caso non servono perchè: An *OrderedDict* 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. http://docs.python.org/2/library/collections.html#collections.OrderedDict 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__. 2013/6/22 Federico Figus <figus.feder...@gmail.com> > > > 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 <nadirsampa...@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@lists.python.it >> http://lists.python.it/mailman/listinfo/python >> >> > > > -- > *Federico Figus* > -- *Federico Figus*
_______________________________________________ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
