Найти, где f (x) изменяется в списке с помощью bisection (в 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.

Конечно функция предполагает, что карта f на list имеет вид:

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

Если это не так, то это, как правило, найти своп но один довольно не определено.

Say 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 (журнал N) с п число элементов в списке, тогда как линейный поиск может результат O (N) проверок (который обычно дороже).

EDIT: в случае, если список содержит два значения, и вы хотите, чтобы найти своп, вы можете просто первым вычислить значение индекса 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 2

То есть 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, если у него есть время.

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