В Python, найти элемент в списке dicts, используя Bisect

Question

У меня есть список dicts, что-то вроде этого:

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

Элементы Dict отсортированы в списке по данным 'offset'. Реальные данные могут быть намного длиннее.

То, что я хочу сделать, это найти элемент в списке с заданным значением смещения, то есть не точно одно из этих значений, но в этом диапазоне. Итак, двоичный поиск - это то, что я хочу сделать.

Теперь я знаю о модуле Python bisect, который является готовым бинарным поиском, но не может использоваться непосредственно для этого случая. Мне просто интересно, какой самый простой способ адаптировать bisect к моим потребностям. Вот что я придумал:

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) 

Он печатает:

2 

Мой вопрос, является ли это лучший способ сделать то, что я хочу, или есть какой-то другой проще, лучше?

Answer 1

Обычный шаблон здесь похож на сортировку по атрибуту, украшать, работать и декомпозировать. Поэтому в этом случае вам просто нужно украсить, а затем позвонить. Однако вы бы хотели избежать этого, так как украшение будет O (n), тогда как вы хотите, чтобы это было O (logn). Поэтому я бы лучше рассмотрел ваш метод.

Answer 2

Когда вы говорите, что реальные данные могут быть намного дольше, это мешает вам хранить список значений смещения под рукой?

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

Ваш метод кажется мне хорошим.

Answer 3

Что вы можете сделать это

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 

Это позволит вам создавать простые list из OffsetWithAttributes экземпляров. Алгоритм bisect должен быть полностью счастлив использовать определенные операторы.

Вы можете использовать свой someOWA.attributes['data'].

Или

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

Это должно сделать более OffsetWithAttributes как dict.

Answer 4

Вы также можете использовать одну из многих реализаций SortedDict на Python для управления вашими test_data. Сортированный dict сортирует элементы по ключевым словам и поддерживает сопоставление с значением. Некоторые варианты реализации также поддерживают операцию bisect на клавишах. Например, Python sortedcontainers module имеет SortedDict, который соответствует вашим требованиям.

В вашем случае это будет выглядеть примерно так:

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 

Тип SortedDict имеет функцию Bisect которая возвращает надвое индекс нужного ключа. С помощью этого индекса вы можете найти фактический ключ. И с помощью этого ключа вы можете получить значение.

Все эти операции очень быстрые в сортированных контейнерах, которые также удобно реализованы в чистом Python. Также есть performance comparison, который обсуждает другие варианты и имеет контрольные данные.