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

Question

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

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

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

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

Теперь я знаю о питоне 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

Вы также можете использовать одну из многочисленных реализаций Python SortedDict для управления вашей test_data. Сортированные DICT сортируют элементы по ключам и поддерживают сопоставление с значением. Некоторые реализации также поддерживают операцию бисета на ключах. Например, 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, которая возвращает разделенный индекс желаемого ключа. С помощью этого индекса вы можете найти фактический ключ. И с этим ключом вы можете получить значение.

Все эти операции очень быстры в SortedContainers, что также удобно реализовано в Pure Python. Есть Сравнение производительности тоже, что обсуждает другие варианты и имеет контрольные данные.

Answer 3

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

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

Ваш метод кажется мне в порядке.

Answer 4

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

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 5

Крутки работают с бисетом, если вы в порядке, используя их вместо этого ...

import bisect

offset = 0
data = 1
test_data = [
    (0, 1500),
    (1270, 120),
    (2117, 30),
    (4055, 30000),
]

i = bisect.bisect(test_data, (1900,0))
test_data.insert(i, (1900,0))
print(test_data[i][data])

Хотя, поскольку кортежи сравниваются «лексикографически» (слева направо) до тех пор, пока элемент не будет равен другим - вам придется рассмотреть, если это желаемое поведение

>>> bisect.insort(test_data, (2117,29))
>>> print(test_data)
[(0, 1500), (1270, 120), (2117, 29), (2117, 30), (4055, 30000)]