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

Question

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

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

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

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

我想做某种平分法来找到变化边界。

Answer 1

这就是 next() 的目的。

result = next(x for x in my_list if works(x))

一种更快但更复杂的方法是：

alist = [0,0,0,0,0,0,1]

def check(my_list, tracking=0):

    def criterion(i):
        return bool(i)

    if len(my_list) == 1:
        if my_list[0] == 1:
            return tracking
        else:
            return tracking + 1

    start = len(my_list) // 2

    if criterion(my_list[start]):
        return check(my_list[:start], tracking=tracking)
    else:
        tracking += start + 1
        return check(my_list[start+1:], tracking=tracking)

print(check(alist))  # returns 6

这是二分法。将列表递归地切成两半，检查中间的元素，如果它是 1 则将切片移动到左侧，如果是 0 则移动到右侧。 tracking 跟踪索引。如果 he\she 有时间，我很想请人 timeit。

Answer 2

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

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

它将 return 第一个索引 i 其中 bool(f(list[i])) 是 True。

当然函数假设 f 在 list 上的映射是以下形式：

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

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

说 f 只是“版本是 2 或更高 ” 所以 lambda v:v >= '2'，那么它将 return:

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

所以索引2。如果整个列表 return 有 False 个对象，它将 **return len(list)。因为它 "assumes" 列表之外的元素将被评估为 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

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

由于这是二分查找，它会运行 in O(log n) with n items number在列表中，而线性搜索 can 导致 O(n) 检查（通常更昂贵）。

EDIT：如果列表包含两个值并且您想找到 swap，您可以简单地先计算值索引 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)

Answer 3

所以你基本上想要实现二进制搜索算法...这很简单，算法的草稿如下。我还没有测试过，但是当你的版本列表长度为 1 或 2 时，你应该了解并处理边缘情况：

def whereWorks(versions, works):

   middle = len(versions)/2

   good = works(versions[middle])

   if middle < 2:
       return good ? 0 : 1

   if works(middle):
         return whereWorks(versions[0:middle])
   else
         return whereWorks(versions[middle:])+middle

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

Find where f(x) changes in a list, with bisection (in Python)

python

git-bisect

bisection

bisect