파이썬 : 찾는 제수 이러한 기능을 벤치마킹

Question

의 성능 :

def divisors_optimized(number): 
    square_root = int(math.sqrt(number)) 

    for divisor in range(1, square_root): 
     if number % divisor == 0: 
      yield divisor 
      yield number/divisor 

    if square_root ** 2 == number: 
     yield square_root 

def number_of_divisors_optimized(number): 
    count = 0 
    square_root = int(math.sqrt(number)) 

    for divisor in range(1, square_root): 
     if number % divisor == 0: 
      count += 2 

    if square_root ** 2 == number: 
     count += 1 

    return count 

당신은 기본 구조가 모두 동일하다고 볼 수 있습니다.

벤치 마크 코드 :

number = 9999999 
for i in range(10): 
    print(f"iteration {i}:") 
    start = time.time() 
    result = list(utils.divisors_optimized(number)) 
    end = time.time() 
    print(f'len(divisors_optimized) took {end - start} seconds and found {len(result)} divisors.') 

    start = time.time() 
    result = utils.number_of_divisors_optimized(number) 
    end = time.time() 
    print(f'number_of_divisors_optimized took {end - start} seconds and found {result} divisors.') 

    print() 

출력 :

iteration 0: 
len(divisors_optimized) took 0.00019598007202148438 seconds and found 12 divisors. 
number_of_divisors_optimized took 0.0001919269561767578 seconds and found 12 divisors. 

iteration 1: 
len(divisors_optimized) took 0.00019121170043945312 seconds and found 12 divisors. 
number_of_divisors_optimized took 0.00020599365234375 seconds and found 12 divisors. 

iteration 2: 
len(divisors_optimized) took 0.000179290771484375 seconds and found 12 divisors. 
number_of_divisors_optimized took 0.00019049644470214844 seconds and found 12 divisors. 

iteration 3: 
len(divisors_optimized) took 0.00019025802612304688 seconds and found 12 divisors. 
number_of_divisors_optimized took 0.00020170211791992188 seconds and found 12 divisors. 

iteration 4: 
len(divisors_optimized) took 0.0001785755157470703 seconds and found 12 divisors. 
number_of_divisors_optimized took 0.00017905235290527344 seconds and found 12 divisors. 

iteration 5: 
len(divisors_optimized) took 0.00022721290588378906 seconds and found 12 divisors. 
number_of_divisors_optimized took 0.00020170211791992188 seconds and found 12 divisors. 

iteration 6: 
len(divisors_optimized) took 0.0001919269561767578 seconds and found 12 divisors. 
number_of_divisors_optimized took 0.00018930435180664062 seconds and found 12 divisors. 

iteration 7: 
len(divisors_optimized) took 0.00017881393432617188 seconds and found 12 divisors. 
number_of_divisors_optimized took 0.00017905235290527344 seconds and found 12 divisors. 

iteration 8: 
len(divisors_optimized) took 0.00017976760864257812 seconds and found 12 divisors. 
number_of_divisors_optimized took 0.0001785755157470703 seconds and found 12 divisors. 

iteration 9: 
len(divisors_optimized) took 0.00024819374084472656 seconds and found 12 divisors. 
number_of_divisors_optimized took 0.00020766258239746094 seconds and found 12 divisors. 

당신은 실행 시간이 매우 가까운 것을 볼 수 있습니다 때마다 어느 선호.

누군가 제너레이터에서 목록을 만들고 그 길이를 검색하는 방법이 반복하는 동안 계산하는 것과 똑같은 방법을 설명 할 수 있습니까? 내 말은, 메모리 할당 (list())이 할당보다 훨씬 비쌉니까?

저는 파이썬 3.6.3을 사용하고 있습니다.

Answer 1

멀리 테스트 중입니다.보다 많은 것들이 생성되고 있습니다. "발견 된 요인"의 경우 발전기 조작 대 int의 비용은 전체적으로 수행 된 작업량과 비교하여 계산됩니다. 3000 건의 재판 부문을 수행하고 있습니다.대 12 개의 추가 사항은 그러한 종류의 작업에 대한 차질 (chump) 변경입니다. pass (아무것도하지)과 추가/yield의 교체, 당신은 여전히가에 달려 찾을 수 (약) 같은 시간 :

def ignore_divisors_optimized(number): 
    square_root = int(math.sqrt(number)) 

    for divisor in range(1, square_root): 
     if number % divisor == 0: 
      pass 

    if square_root ** 2 == number: 
     pass 

와 함께 microbenchmarking ipython의 %timeit 마법 :

>>> %timeit -r5 number_of_divisors_optimized(9999999) 
266 µs ± 1.85 µs per loop (mean ± std. dev. of 5 runs, 1000 loops each) 
>>> %timeit -r5 list(divisors_optimized(9999999)) 
267 µs ± 1.29 µs per loop (mean ± std. dev. of 5 runs, 1000 loops each) 
>>> %timeit -r5 ignore_divisors_optimized(9999999) 
267 µs ± 1.43 µs per loop (mean ± std. dev. of 5 runs, 1000 loops each) 

사실 number_of_divisors이 더 빠른 마이크로 초였던 사실은 관련이 없습니다 (반복 테스트의 지터는 마이크로 초보다 높음). 작업의 99 % 이상이 루프 및 테스트이기 때문에 기본적으로 동일한 속도입니다. 테스트가 통과 할 때 수행되는 작업이 아니라 루프입니다.

이것은 90/10 최적화 규칙의 예입니다. 대략 90 %의 시간이 코드의 10 % (이 경우 평가판 본부)에 소요됩니다. 나머지 90 %는 10 %를 소비합니다. 대부분의 시간이 if number % divisor == 0: 라인에 소요되므로 시간의 10 %를 실행하는 코드의 90 %에서 작은 부분을 최적화하면 도움이되지 않습니다. 이 테스트를 제거하여 아무 것도하지 않고 range 루핑 만하면 로컬 마이크로 벤치 마크에서 런타임이 ~ 78 μs로 떨어지며 테스트에서 런타임의 거의 200 μs를 차지하고 나머지 코드는 두 배가됩니다 함께 필요합니다.

이것을 최적화하려면 시험 구분 라인 자체의 속도를 높이거나 (기본적으로 다른 Python 인터프리터를 의미하거나 Cython을 사용하여 C로 컴파일) 접근 방식을 실행하거나 (예 : 특정 경계까지 미리 계산 가능한 가능한 소수 요소를 미리 계산하십시오. 따라서 임의의 주어진 입력에 대해 비 프라임 제수를 테스트하지 않은 다음 알려진 소수 요소와 그 다양성으로부터 비 소수 요소 수를 생성/계산할 수 있습니다) .