8

推理：我试图在 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()非常昂贵。

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

4

3 回答 3

9

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

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

它将返回is的第一个索引i。bool(f(list[i]))True

当然，该函数假定fon 的地图具有list以下形式：

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对象，它将 **return 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)检查（这通常更昂贵）。

编辑：如果列表包含两个值并且您想要找到交换，您可以简单地首先计算 index 的值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)
于 2017-02-08T17:28:21.757 回答
0

所以你基本上想要实现二进制搜索算法......这很简单，算法的粗略草案如下。我还没有测试过，但是当你的版本列表长度为 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
于 2017-02-08T17:33:31.593 回答
-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跟踪索引。timeit如果他\她有时间，我很想找人。

于 2017-02-08T17:25:11.027 回答