在Python中，使用bisect在dicts列表中查找项目
在Python中，使用bisect在dicts列表中查找项目
提问于 2018-09-12 07:38:33
我有一个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
我的问题是，这是做我想要的最好的方式，还是有其他更简单，更好的方法？
回答 2
Stack Overflow用户
发布于 2018-09-12 15:59:43
这里通常的模式类似于按属性排序，装饰，操作和未装饰。所以在这种情况下你只需要装饰然后再打电话。但是你要避免这样做，因为decorate将是O（n），而你希望它是O（logn）。因此，我认为你的方法最好。
Stack Overflow用户
发布于 2018-09-12 16:54:28
你能做的就是这个
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。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/-100002620
复制相关文章
相似问题