python - 使用二分法查找列表中 f(x) 变化的位置(在 Python 中)

Question

推理:我试图在 Python 中实现类似于 git bisect 的东西，但基本上是一个目录列表。

我有一个(长)版本号列表，如下所示:['1.0', '1.14', '2.3', '3.1', '4']

我有一个函数 works()，它接受一个版本号，并返回一个值。

[works(x) for x in my_list] 看起来像:['foo', 'foo', 'foo', 'bar', 'bar']...但是运行 works() 非常昂贵。

我想进行某种平分，以找到变化边界。

Answer 1

您可以简单地使用二进制搜索:

def binary_f(f,list):
    frm = 0
    to = len(list)
    while frm < to:
        mid = (frm+to)>>1
        if f(list[mid]):
            to = mid
        else:
            frm = mid+1
    return frm

它将返回 第一个索引 i bool(f(list[i])) 为 True.

当然，该函数假定 list 上 f 的映射具有以下形式:

f(list) == [False,False,...,False,True,True,...,True]

如果不是这种情况，它通常会找到一个 swap 但哪个是未定义的。

假设 f 只是“版本为 2 或更高”，所以 lambda v:v >= '2'，那么它将返回:

>>> binary_f(lambda v:v >= '2',['1.0', '1.14', '2.3', '3.1', '4'])
2

所以索引2。如果整个列表返回 False 对象，它将**返回 len(list)。因为它“假定”列表之外的元素将被评估为 True:

>>> binary_f(lambda v:v >= '4.2',['1.0', '1.14', '2.3', '3.1', '4'])
5

当然在您的示例中 f 是 works。

实验:

>>> binary_f(lambda v:v >= '2',['1.0', '1.14', '2.3', '3.1', '4'])
2
>>> binary_f(lambda v:v >= '0',['1.0', '1.14', '2.3', '3.1', '4'])
0
>>> binary_f(lambda v:v >= '1',['1.0', '1.14', '2.3', '3.1', '4'])
0
>>> binary_f(lambda v:v >= '1.13',['1.0', '1.14', '2.3', '3.1', '4'])
1
>>> binary_f(lambda v:v >= '2.4',['1.0', '1.14', '2.3', '3.1', '4'])
3
>>> binary_f(lambda v:v >= '3',['1.0', '1.14', '2.3', '3.1', '4'])
3
>>> binary_f(lambda v:v >= '3.2',['1.0', '1.14', '2.3', '3.1', '4'])
4
>>> binary_f(lambda v:v >= '4.2',['1.0', '1.14', '2.3', '3.1', '4'])
5

(我在这里当然做了一个非常便宜的版本检查，但它当然适用于更复杂的谓词)。

由于这是二分搜索，它将在 O(log n) 中运行，n 是列表中的项目数，而线性搜索可以 结果 O(n) 检查(通常更昂贵)。

编辑:如果列表包含两个值并且您想找到交换，您可以简单地先计算索引0:

val0 = f(list[0])

然后提供binary_f:

binary_f(lambda v:works(v) != val0,list)

或者把它放到一个很好的函数中:

def binary_f_val(f,list):
    val0 = f(list[0])
    return binary_f(lambda x:f(x) != val0,list)