ottenendo l'indice chiave in un OrderedDict Python?

Question

Ho un collections.OrderedDict con un elenco di coppie chiave, valore. Vorrei calcolare l'indice i in modo che la chiave i corrisponda a un determinato valore. Per esempio:

food = OrderedDict([('beans',33),('rice',44),('pineapple',55),('chicken',66)]) 

voglio andare dalla chiave chicken all'indice 3, o dal tasto rice all'indice 1. posso fare questo ora con

food.keys().index('rice') 

ma c'è un modo per sfruttare la capacità di OrderedDict di cercare rapidamente le cose per nome della chiave? Altrimenti sembra che la ricerca dell'indice sia O (N) piuttosto che O (log N), e ho molti articoli.

Suppongo che posso farlo manualmente facendo il mio proprio indice:

>>> foodIndex = {k:i for i,k in enumerate(food.keys())} 
>>> foodIndex 
{'chicken': 3, 'rice': 1, 'beans': 0, 'pineapple': 2} 

ma speravo ci potrebbe essere qualcosa di costruito in un OrderedDict.

Answer 1

Fondamentalmente, no. OrderedDict ha la capacità di guardare le cose velocemente per nome della chiave semplicemente usando un ditt regolare e non ordinato sotto il cofano. Le informazioni dell'ordine vengono memorizzate separatamente in una lista doppiamente collegata. Per questo motivo, non c'è modo di passare direttamente dalla chiave al suo indice. L'ordine in OrderedDict è principalmente destinato a essere disponibile per l'iterazione; una chiave non "sa" il proprio ordine.

Answer 2

OrderedDict è una sottoclasse di dict che ha la capacità di attraversare le sue chiavi in ​​ordine (e ordine inverso) per maintaining a doubly linked list. Quindi non conosce l'indice di una chiave. Può solo attraversare l'elenco collegato per trovare gli elementi nel tempo O (n).

Perusing the source code può essere il modo più soddisfacente per confermare che l'indice non è gestito da OrderedDict. Vedrai che non è mai stato usato o ottenuto un indice.

Answer 3

Come altri hanno sottolineato, OrderedDict è solo un dizionario che memorizza internamente a quale ordine sono state aggiunte voci. Tuttavia, puoi sfruttare la sua capacità di cercare rapidamente le cose memorizzando l'indice desiderato insieme al resto dei dati per ogni voce. Ecco cosa intendo:

from collections import OrderedDict 

foods = [('beans', 33), ('rice', 44), ('pineapple', 55), ('chicken', 66)] 
food = OrderedDict(((v[0], (v[1], i)) for i, v in enumerate(foods))) # saves i 

print(food['rice'][1]) # --> 1 
print(food['chicken'][1]) # --> 3