在Python中，使用bisect查找字典列表中的项

Question

我有一个字典的列表，大概是这样的：

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

这些字典里的项目是根据 '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

当你说真实的数据可能会更长时，这是不是意味着你不能随时保存一些偏移值的列表呢？

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

不过我觉得你的方法没问题。

Answer 2

你也可以使用Python中很多现成的SortedDict实现来管理你的测试数据。SortedDict是一种排序字典，它会根据键的顺序来排列元素，并且保持键与值之间的对应关系。有些实现还支持对键进行二分查找操作。比如，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类型有一个二分查找函数，可以返回你想要的键的索引。通过这个索引，你可以找到实际的键，然后用这个键去获取对应的值。

在sortedcontainers中，这些操作都非常快，而且它是用纯Python实现的。还有一个性能对比，讨论了其他选择，并提供了基准数据。

Answer 3

这里的常见做法就像是按照某个属性进行排序，先装饰，再操作，最后去掉装饰。所以在这种情况下，你只需要先装饰，然后再调用。不过你要避免这样做，因为装饰的时间复杂度是O(n)，而你希望这个过程的时间复杂度是O(logn)。因此，我认为你现在的方法是最好的。