使用二分(在Python中)查找列表中f(x)更改的位置

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.

当然,函数假定的地图f上的listIS的形式为:

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

如果不是这种情况,它通常会找到一个交换但是哪一个是未定义的.

说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)