Find where f (x) changes in a list, dividing in half (in Python)

Question

Reasoning: I'm trying to implement in Python something similar to git bisect , but basically a list of directories.

I have a (long) list of version numbers: ['1.0', '1.14', '2.3', '3.1', '4']

I have a works() function that takes a version number and returns a value.

[works(x) for x in my_list] will look like this: ['foo', 'foo', 'foo', 'bar', 'bar'] ... but works() very expensive.

I would like to make some kind of bisector that will find the boundary of change.

Answer 1

You can simply use binary search :

 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 

It will return the first index i for which bool(f(list[i])) is True .

Of course, the function assumes that the mapping f to list has the form:

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

If this is not the case, it will usually find a swap, but which is more like undefined.

Say f just “version 2 or higher,” so lambda v:v >= '2' , then it will return:

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

So index 2 . If the whole list returns with False objects, it will return len(list) . Since it "accepts", an item located outside the list will be evaluated as True :

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

Of course, in your example f there are works .

Experiments

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

(I, of course, did a very cheap version check here, but, of course, this works for more complex predicates).

Since this is a binary search, it will work in O (log n) with n number of items in the list, while a linear search can result in O (n) checking (which is usually more expensive).

EDIT : if the list contains two values ​​and you want to find swap, you can simply calculate the value for index 0 :

 val0 = f(list[0]) 

and then specify binary_f :

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

Or add it to a nice function:

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

Answer 2

So, you basically want to implement a binary search algorithm ... it's pretty straight forward, the draft algorithm is below. I have not tested it, but you should get an idea and take care of extreme cases when your version list is 1 or 2 long:

 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 

Answer 3

This is what next() .

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

A faster way, but more complicated:

 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 

This is a halving method. It shortens the list recursively in half, checks the element in the middle and moves the slice to the left if it is 1 or to the right if it is 0. tracking tracks the index. I would like someone to have timeit if he has time.