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

[Federico Figus]

>
> 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.federico a 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 <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*
>



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