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

[enrico franchi]

2010/12/10 lex mlist <lexmlist a gmail.com>:


> Potrei organizzare una tupla assumendo alcune convenzioni (per esempio, sui
> numeri dispari ci sono le chiavi, su quelli pari ci sono i valori, cosi da
> ricavare la posizione della chiave, aggiungere uno e ricavare il valore).

Scusa ma ragioniamo: una tupla e' una struttura *lineare*. Quindi il
meglio che puoi fare (mantenendola ordinata) e' O(log n).
E questo e' vagamente sensato se e solo se non devi *mai* e poi *mai*
aggiungere un elemento alla tupla (che ti costa O(n log n) con
l'aggravante che devi necessariamente sfasciare e ricostruire la
tupla).

Poi c'e' *una* struttura dati che e' fatta e ottimizzata per fare
quello che devi fare: ovvero la tabella di hash. Che e' *esattamente*
l'implementazione dei dizionari di Python (che sono pure *eccellenti*
tabelle di hash, decisamente sopra la media delle implementazioni che
si trovano in giro).

Quindi non capisco la tua posizione: dici che "ottimizzeresti
l'algoritmo di ricerca", mentre dovresti "scegliere la struttura dati
opportuna" [ meglio dell'O(1) average delle tabelle di hash non fai ].
Ottimizzare le tabelle di hash non si fa ottimizzando l'algoritmo di
ricerca (che e' *sempre* banale) ma migliorando l'hashing ed
evenutalmente la gestione della struttura dati. Ma in Python entrambi
sono eccellenti.

Visto i tuoi dubbi e le tue soluzioni mi viene il sensato dubbio che
non ho capito quello che vuoi fare. Perche' se il punto e' "cercare
ripetutamente chiavi in una struttura dati con un sacco di elementi"
la cosa talmente ovvia da essere praticamente l'unica sensata e' avere
una tabella di hash, ovvero un dizionario. Di conseguenza, non capisco
la domanda.



-- 
.
..: -enrico-