在Python中,使用bisect在dicts列表中查找项目

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

您还可以使用Python的许多SortedDict实现之一来管理您的test_data.已排序的dict按键对元素进行排序,并维护到值的映射.某些实现还支持对键进行二等分操作.例如,Python sortedcontainers模块有一个符合您要求的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中都非常快,也可以用纯Python实现.还有性能比较,讨论其他选择并具有基准数据.

Answer 2

当您说实际数据可能更长时，这是否会阻止您保留手头的偏移值列表？

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

不过你的方法对我来说似乎不错。

Answer 3

这里通常的模式类似于按属性排序、装饰、操作和取消装饰。所以在这种情况下你只需要装饰然后调用。但是，您希望避免这样做，因为装饰将是 O(n)，而您希望它是 O(logn)。因此我认为你的方法是最好的。