목록에서 f (x)가 바이 섹션 (파이썬에서)으로 변경되는 부분

Question

추론 : 나는 파이썬에서 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

당신은 단순히 이진 검색를 사용할 수 있습니다. 물론

이 기능은 list에 f의지도의 형식이라고 가정 그렇지 않은 경우

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

, 그것은 일반적으로 스왑를 찾을 수 있지만, 어느 쪽이 오히려입니다 정의되지 않았습니다.

말 f 그렇게 lambda v:v >= '2', 다음이 반환됩니다 "버전은 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 

(I 여기서 물론 아주 싼 버전 확인을했지만 좀 더 정교한 술어 물론 작동). 이 이진 검색이기 때문에

그것은 N 선형 검색 반면,리스트 내의 항목의 수와 O (로그 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) 

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을 갖고 싶어합니다.

이

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 

그것은 bool(f(list[i]))이 True입니다 i하는의 최초의 인덱스를 반환합니다

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