我有一个字典列表,像这样:
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
我的问题是,这是做我想做的事情的最佳方式,还是有其他更简单、更好的方式?
最佳答案
您还可以使用 Python 的众多 SortedDict 实现之一来管理您的 test_data。已排序的字典按键对元素进行排序,并维护到值的映射。一些实现还支持对键进行平分操作。例如,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 函数,它返回所需键的二等分索引。使用该索引,您可以查找实际的 key 。使用该键,您可以获得值。
所有这些操作在 sortedcontainer 中都非常快,而 sortedcontainer 也可以在纯 Python 中方便地实现。有一个 performance comparison也讨论了其他选择并具有基准数据。
关于python - 在 Python 中,使用二分法在字典列表中查找项目,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1344308/