W Pythonie znaleźć pozycję w liście dicts korzystając Przepoławiana

Question

Mam listę dicts, coś takiego:

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

Pozycje dict są klasyfikowane w wykazie zgodnie z danymi 'offset'. Prawdziwe dane mogą być znacznie dłuższe.

Co chcę zrobić, to wyszukać pozycję na liście, podając konkretną wartość przesunięcia, która jest , a nie dokładnie jedną z tych wartości, ale w tym zakresie. Zatem binarne wyszukiwanie jest tym, co chcę zrobić.

Jestem już świadomy modułu Python bisect, który jest gotowym wyszukiwaniem binarnym - świetnym, ale nie do bezpośredniego wykorzystania w tym przypadku. Zastanawiam się, jaki jest najłatwiejszy sposób dostosowania się do moich potrzeb. Oto co wymyśliłem:

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) 

Drukuje:

2 

Moje pytanie brzmi, czy jest to najlepszy sposób, żeby zrobić to, co chcę, czy istnieje jakiś inny prostszy, lepszy sposób?

Answer 1

Zwykły wzór jest tutaj podobny do sortowania według atrybutu, dekorowania, obsługi i dekoruacji. W takim przypadku wystarczy udekorować, a następnie zadzwonić. Jednak nie chcesz tego robić, ponieważ dekoracją będzie O (n), podczas gdy chcesz, aby było to O (logn). Dlatego uważam twoją metodę najlepiej.

Answer 2

Kiedy mówisz, że prawdziwe dane mogą być znacznie dłuższe, czy to uniemożliwia zachowanie listy wartości przesunięcia pod ręką?

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

Twoja metoda wydaje mi się jednak w porządku.

Answer 3

Co można zrobić to

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 

To powinno pozwolić na stworzenie prostych list z OffsetWithAttributes instancji. Algorytm bisect powinien być całkowicie zadowolony z używania zdefiniowanych operatorów.

Możesz użyć swojej someOWA.attributes['data'].

Albo

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

To powinno sprawić, że bardziej jak dictOffsetWithAttributes.

Answer 4

Możesz także użyć jednej z wielu implementacji SortedDict Pythona do zarządzania swoimi danymi test_data. Posortowany dykt sortuje elementy według klucza i zachowuje odwzorowanie na wartość. Niektóre implementacje obsługują również operację dwudzielną na kluczach. Na przykład model Python sortedcontainers module ma SortedDict, który spełnia Twoje wymagania.

W twoim przypadku to będzie wyglądać mniej więcej tak:

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 

Typ SortedDict posiada funkcję przepoławiać która zwraca przecięty indeks żądanego klucza. Dzięki temu indeksowi możesz wyszukać właściwy klucz. Za pomocą tego klucza można uzyskać wartość.

Wszystkie te operacje są bardzo szybkie w sortowanych kontenerach, które są również wygodnie implementowane w czystym Pythonie. Jest też performance comparison, który omawia inne opcje i ma dane porównawcze.