In Python, trovano voce nella lista delle dicts, utilizzando bisect

Question

ho una lista di dicts, qualcosa di simile:

test_data = [ 
    { 'offset':0, 'data':1500 }, 
    { 'offset':1270, 'data':120 }, 
    { 'offset':2117, 'data':30 }, 
    { 'offset':4055, 'data':30000 }, 
] 

Le voci dict sono ordinati nella lista in base ai dati 'offset'. I dati reali potrebbero essere molto più lunghi.

Quello che voglio fare è cercare un articolo nell'elenco dato un particolare valore di offset, che è non esattamente uno di quei valori, ma in quell'intervallo. Quindi, una ricerca binaria è ciò che voglio fare.

Sono al corrente del modulo Python bisect, che è una ricerca binaria già pronta, ma non direttamente utilizzabile per questo caso. Mi sto solo chiedendo quale sia il modo più semplice per adattare bisect alle mie esigenze. Ecco quello che mi si avvicinò con:

import bisect 

class dict_list_index_get_member(object): 
    def __init__(self, dict_list, member): 
     self.dict_list = dict_list 
     self.member = member 
    def __getitem__(self, index): 
     return self.dict_list[index][self.member] 
    def __len__(self): 
     return self.dict_list.__len__() 

test_data_index_get_offset = dict_list_index_get_member(test_data, 'offset') 
print bisect.bisect(test_data_index_get_offset, 1900) 

Esso stampa:

2 

La mia domanda è, è questo il modo migliore per fare quello che voglio, o c'è qualche altro modo più semplice, migliore?

Answer 1

Il solito schema qui è simile all'ordinamento per attributo, decorazione, funzionamento e non decorato. Quindi in questo caso avresti solo bisogno di decorare e poi chiamare. Comunque vorrai evitare di farlo poiché decorerebbe O (n) mentre vuoi che questo sia O (logn). Quindi considererei il tuo metodo migliore.

Answer 2

Quando dici che i dati reali potrebbero essere molto più lunghi, non ti impedisce di tenere a portata di mano un elenco di valori di offset?

offset_values = [i['offset'] for i in test_data] 
bisect.bisect(offset_values, 1900) 

Tuttavia, il metodo mi sembra soddisfacente.

Answer 3

Che cosa si può fare è questo

class OffsetWithAttributes(object): 
    def __init__(self, offset, **kw): 
     self.offset= offset 
     self.attributes= kw 
    def __eq__(self, other): 
     return self.offset == other.offset 
    def __lt__(self, other): 
     return self.offset < other.offset 
    def __le__(self, other): 
     return self.offset <= other.offset 
    def __gt__(self, other): 
     return self.offset > other.offset 
    def __ge__(self, other): 
     return self.offset >= other.offset 
    def __ne__(self, other): 
     return self.offset != other.offset 

Ciò dovrebbe consentire di creare un semplice list di OffsetWithAttributes istanze. L'algoritmo bisect dovrebbe essere perfettamente felice di utilizzare gli operatori definiti.

È possibile utilizzare il someOWA.attributes['data'].

O

def __getattr__(self, key): 
     return self.attributes[key] 

che dovrebbe rendere più OffsetWithAttributes come un dict.

Answer 4

È anche possibile utilizzare una delle numerose implementazioni SortedDict di Python per gestire i dati di test. Un dict ordinato ordina gli elementi per chiave e mantiene una mappatura su un valore. Alcune implementazioni supportano anche un'operazione di bisettrice sui tasti. Ad esempio, lo Python sortedcontainers module ha uno SortedDict che soddisfa i requisiti dell'utente.

Nel tuo caso sarebbe simile:

from sortedcontainers import SortedDict 
offset_map = SortedDict((item['offset'], item['data']) for item in test_data) 
index = offset_map.bisect(1275) 
key = offset_map.iloc[index] 
print offset_map[key] 
# 120 

Il tipo SortedDict ha una funzione bisect che restituisce l'indice Diviso in due parti del tasto desiderato. Con questo indice, puoi cercare la chiave effettiva. E con quella chiave puoi ottenere il valore.

Tutte queste operazioni sono molto veloci in contenitori ordinati che sono anche opportunamente implementati in pure-Python. C'è anche uno performance comparison che discute altre scelte e ha dati di riferimento.