在属性排序列表中搜索属性

2024-03-29 05:37:15 发布

您现在位置:Python中文网/ 问答频道 /正文

在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排序。列表L的所有Any实例都有不同的attr_a值。搜索attr_a等于x的对象的attr_b值的最有效方法是什么?你知道吗


Tags: 对象实例方法self示例列表属性object
2条回答

您希望使用模块bisect及其bisect_left函数。在您的情况下,您需要在使用之前提取密钥列表,请参阅Other examples部分以获取详细解释。如果这是不可接受的,那么您可以实现自己版本的二进制搜索,这是一个简单的算法。你知道吗

您应该采用二进制搜索来为您的attr_a值找到正确的Any对象。^{} module提供了一个起点:

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接受一个callable,该callable返回与我们正在平分的值相对应的值。你知道吗

现在可以使用二分法来查找Any索引:

from operator import attrgetter

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

它返回匹配的Any的索引,或attr_a值大于x下一个Any对象的索引。您可能需要针对这些情况测试和/或调整算法。例如,您可以验证attr_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

相关问题 更多 >