[Python] Quale tra dict, tuple e oggetti collections risulta essere il più performante?

[Enrico Franchi]

On 12/13/10 5:16 PM, "lex mlist" <lexmlist a gmail.com> wrote:

> Io non ho detto che Python non permette di ottimizzare la ricerca, ho per
> l'appunto chiesto se esistono magari altri tipi di dati (anche del modulo
> collections) che sono pensati appositamente per situazioni analoghe alla mia,
> qualcosa di più opportuno di un dizionario (sia per la gestione che per la
> ricerca), visto che non ho visto cosa fornisce il modulo collections.

Quello che volevo fosse chiaro e' che per un problema di tipo "ricerca per
chiave su un grosso numero di elementi" e' il tipico problema che si risolve
con una tabella di hash[0]. E "dizionario" e' il modo in cui la trovi in
Python.

Ovvero, o il problema non e' come lo hai descritto (per esempio perche' ci
sono ipotesi piu' forti che ti permettono di strutturare meglio il problema
-- esempio... Se le chiavi fossero numeri consecutivi, beh... un array
sarebbe meglio di un dict ;) ) oppure una tabella di hash e' strutturalmente
il meglio che puoi fare.

E i dict di python sono fra le migliori implementazioni di sempre.


----
[0] se poi sono *veramente* tanti forse non vuoi tenerli in memoria e
appoggiarti ad un db, ma e' appunto un problema diverso da quello descritto.

> Visto che in Python per ricercare l'elemento mi limito a "x in container" mi
> chiedevo su quali elementi tale ricerca potrebbe essere più veloce (che ne sò
> io come python gestisce la cosa, per questo chiedo).

Ohibo', non e' esattamente un segreto di stato! ;)

> Per la tupla ok, il ragionamento ci stà, per il dizionario O(1) è quello che
> avevo trovato anche io e quindi da subito ho adottato tale soluzione, ma poi
> mi sono imbattuto nel modulo collections che definisce "Tipi di dato
> contenitore ad alte prestazioni" (cit.) e quindi mi sono chiesto se magari ci
> sono altri contenitori che dovrei valutare.

Si ma non e' che ci sia proprio una valanga di roba in quel modulo. :)
Comunque l'importante e' che hai trovato dict e sei partito con quello:
prosegui e vai bene. ;)

> Riguardo l'ottimizzazione dell'algoritmo di ricerca intendo proprio quello, in
> altri linguaggi, ad esempio in C, prima di pensare ad una struttura dati
> migliore penserei ad ottimizzare l'algoritmo di ricerca nella struttura che ho
> creato per l'occasione.

Sbaglieresti: faresti una micro-ottimizzazione contro una
macro-ottimizzazione. Quando hai un problema di ricerca il *modo* in cui fai
la ricerca e' terribilmente legato a come hai rappresentato i dati.
Ottimizzare la ricerca senza ottimizzare la strategia (che a sua volta
implica modificare il supporto in memoria) non e' essenzialmente possibile.

> Comunque non importa, per ora vado avanti coi dizionari, quando ho tempo mi
> guardo il modulo collections.

Non guardarlo. Non trovi nulla di meglio di un dizionario per fare il
mestiere di un dizionario.