Pythonの：これらの機能をベンチマーク約数

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()）は割り当てよりもはるかに高価なはずですか？

私はPython 3.6.3を使用しています。

Answer 1

farmoreあなたが生産しているものより多くのものをテストしています。 「発見された因子」のケースに対するジェネレータ操作の対listのコストは、合計で実行された作業の量と比較して異なります。あなたは3000を超える試験部門を遂行しています。 12の追加と12の追加は、そのような作業に対する不意の変化です。 ipythonの%timeit魔法と

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：

追加/ passと yield S（何もしない）を交換する、あなたはそれが はまだは（大体）で同じ時間を走った見つけることができます

>>> %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にコンパイルする）か、それを実行する方法（例えば、ある結合まで可能な素因数を事前に計算するため、任意の入力に対して、非素因数の除数のテストを避け、既知の素因数とその多重度から非素因数の数を生成/計算することができます） 。