0

在 Python 中，在根据属性排序的列表中搜索的最有效方法是什么？有关更精确的问题，请参见下文。

例子：

class Any (object):
    def __init__(self, attr_a, attr_b):
        self.attr_a = attr_a
        self.attr_b = attr_b

L = [Any(-3, 4), Any(-2, 1), Any(0, 2), Any(2, 1), Any(5, 6), Any(6, 3), Any(8, 2), Any(10, 1), Any(13, 5), Any(14, 3)]

L是根据属性排序的attr_a。列表的所有Any实例L都有不同的attr_a值。搜索等于attr_b的对象的值的最有效方法是什么？attr_ax

4

2 回答 2

3

您将采用二进制搜索来找到Any适合您attr_a价值的对象。该bisect模块提供了一个起点：

def bisect_left(a, x, lo=0, hi=None, key=None):
    if key is None: key = lambda v: v
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if key(a[mid]) < x: lo = mid+1
        else: hi = mid
    return lo

我唯一做的就是key在此处的签名中添加一个函数。key接受一个可调用的，它返回我们正在二分的值。

现在您可以使用二分法找到您的Any索引：

from operator import attrgetter

index = bisect_left(L, x, key=attrgetter('attr_a'))

这将返回匹配Any的索引或值高于的下一个 Any对象的索引。您可能需要针对这些情况测试和/或调整算法。例如，您可以验证确实匹配所需的值：attr_axattr_a

def find_by_x(L, x, key):
    index = bisect_left(L, x, key=key)
    if key(L[index]) != x:
        raise IndexError('{} not found'.format(x))
    return L[index]

演示：

>>> from operator import attrgetter
>>> L = [Any(-3, 4), Any(-2, 1), Any(0, 2), Any(2, 1), Any(5, 6), Any(6, 3), Any(8, 2), Any(10, 1), Any(13, 5), Any(14, 3)]
>>> x = 6
>>> bisect_left(L, x, key=attrgetter('attr_a'))
5
>>> L[bisect_left(L, x, key=attrgetter('attr_a'))].attr_b
3
>>> find_by_x(L, x, key=attrgetter('attr_a')).attr_b
3
>>> x = 12
>>> find_by_x(L, x, key=attrgetter('attr_a')).attr_b
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in find_by_x
IndexError: 12 not found
于 2013-08-01T17:11:54.900 回答
0

您想使用模块bisect及其bisect_left功能。在您的情况下，您需要在使用之前提取键列表，请参阅其他示例部分以获取详细说明。如果这是不可接受的，那么您可以实现自己的二进制搜索版本，这是一个简单的算法。

于 2013-08-01T17:11:02.343 回答