Per cosa può essere utilizzato un 'TreeDict' (o Treemap) in pratica?

Question

Sto sviluppando una classe 'TreeDict' in Python. Questo è fondamentalmente un dict che ti consente di recuperare le sue coppie chiave-valore in ordine ordinato, proprio come la classe di raccolta Treemap in Java.

Ho implementato alcune funzionalità in base al modo in cui è possibile utilizzare indici univoci nei database relazionali, ad es. funzioni che consentono di recuperare valori corrispondenti a un intervallo di chiavi, chiavi maggiori di, inferiori o uguali a un determinato valore nell'ordine ordinato, stringhe o tuple che hanno un prefisso specifico nell'ordine ordinato, ecc.

Sfortunatamente, non riesco a pensare a nessun problema di vita reale che richiederà una lezione come questa. Ho il sospetto che la ragione per cui non abbiamo ordinato i dadi in Python è che in pratica non sono richiesti abbastanza spesso per valerne la pena, ma voglio essere smentito.

Riesci a pensare a qualche applicazione specifica di un 'TreeDict'? Qualche problema di vita reale che sarebbe meglio risolto da questa struttura di dati? Voglio solo sapere con certezza se ne valga la pena.

Answer 1

È utile quando è necessario passare attraverso un dizionario in ordine di chiavi; che si presenta occasionalmente. In realtà ho trovato il suo infinitamente più comune in alcuni concorsi di programmazione rispetto a qualsiasi altra cosa (pensa ACM, ecc.)

La caratteristica più utile di una TreeMap è quando vuoi trovare rapidamente la chiave min o max; usando un dizionario ordinato questa è spesso una singola chiamata di metodo; e algoritmicamente può essere fatto in O (log (n)) tempo, invece di iterare su ogni tasto alla ricerca di un min / max se la raccolta non è ordinata. Fondamentalmente, un'interfaccia molto più amichevole.

Una delle volte più comuni in cui mi imbatto è quando gli oggetti vengono identificati da un nome specifico e si desidera stampare gli oggetti ordinati in base al nome; dire una mappatura dal nome della directory al numero di file in una directory.

Un altro posto che ho usato è in un wrapper di fogli di calcolo Excel; mappatura dal numero di riga all'oggetto riga. Ciò ti consente di trovare rapidamente l'indice dell'ultima riga, senza scorrere ciclicamente ogni riga.

Inoltre, è utile quando è possibile definire facilmente una relazione di confronto sui tasti, ma non necessariamente una funzione di hashing, come necessario per HashMaps. L'esempio migliore (anche se debole) che mi viene in mente è la distinzione tra maiuscole e minuscole.

Answer 2

Ho visto diverse risposte che puntano alla " cammina nella sequenza ordinata " caratteristica, che è davvero importante, ma nessuna che evidenzia l'altra grande caratteristica, che è " trova la prima voce con un tasto > = this " ;. Questo ha molti usi anche quando non c'è davvero bisogno di & Quot; walk & Quot; da lì.

Ad esempio (questo è emerso in una recente risposta SO), supponiamo che tu voglia generare valori pseudo-casuali con determinate frequenze relative - cioè, ti viene dato, diciamo, un dict d:

{'wolf': 42, 'sheep': 15, 'dog': 23, 'goat': 15, 'cat': 5}

e necessita di un modo per generare "lupo" con una probabilità di 42 su 100 (poiché 100 è il totale delle frequenze relative fornite), "pecora" 15 su 100 e così via; e il numero di valori distinti può essere abbastanza grande, così come le frequenze relative.

Quindi, memorizza i valori dati (in qualunque ordine) come valori in una mappa ad albero, con le chiavi corrispondenti essendo la " frequenza cumulativa totale " fino a quel punto. Cioè:.

def preprocess(d):
    tot = 0
    for v in d:
        tot += d[v]
        treemap.insert(key=tot, value=v)
    return tot, treemap

Ora, generare un valore può essere piuttosto veloce (O(log(len(d)))), come segue:

def generate(tot, treemap, r=random):
    n = r.randrange(tot)
    return treemap.firstGTkey(n).value

dove firstGTKey è un metodo che restituisce la prima voce (con .key e .value attributi, in questo ipotetico esempio) con una chiave > l'argomento dato. Ho usato questo approccio con file di grandi dimensioni archiviati come alberi B, ad esempio (usando ad esempio bsddb.bt_open e il metodo set_location).

Answer 3

Il motivo per mantenere gli elementi in ordine ordinato è per un recupero più rapido. Supponiamo che volessi tutti i valori nel dizionario in un intervallo ordinato. Questo è molto più veloce con un TreeDict che con la normale hashmap. Fondamentalmente ti consente di mantenere tutto nel dizionario in ordine. So che nell'applicazione su cui sto attualmente lavorando utilizza una classe come questa per interrogare sostanzialmente la struttura dei dati.

Answer 4

Uso spesso Dict<DateTime, someClassOrValue> quando lavoro con dati di processo industriali-- Apertura / chiusura della valvola, avvio / arresto della macchina, ecc.

L'ordinamento delle chiavi è particolarmente utile quando devo confrontare gli intervalli di tempo tra avvio / arresto o eventi di apertura / chiusura in un discreto periodo di tempo.

Tuttavia, dato che sono stato in grado di usare linq in C # ho scoperto che spesso è più semplice lavorare con IEnumerables e usare i metodi di estensione IQueryable per ottenere le informazioni di cui ho bisogno.

Answer 5

Quasi tutti " GROUP BY " i rapporti richiedono un dizionario ordinato.

summary = sortedDefaultDict()
for row in somePileOfData:
    summary[row.group_by] += row.balance
for k in sorted(summary.keys()):
    print k, summary[k]

Questo viene fatto così spesso nelle applicazioni di data warehousing, che è difficile esprimere quanto sia centrale.

Se la funzione sorted non funziona, risparmia un sacco di tempo a lungo termine.

Answer 6

Hai visto che: http://code.activestate.com/recipes/576998/ ?

Zuo

Answer 7

Possono semplificare l'implementazione di vari algoritmi.