2010/12/10 lex mlist <lexml...@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- _______________________________________________ Python mailing list Python@lists.python.it http://lists.python.it/mailman/listinfo/python
