python - Python の効率化/最適化プロジェクト Euler #5 の例

Question

このソリューションをProject Euler #5に書きました。

import time
start_time = time.time()

def ProjectEulerFive (m = 20):

    a = m
    start = 2
    while (m % start) == 0:
        start += 1

    b = start
    while b < m:
        if ( a % b) != 0:
           a += m
           b = start
           continue
        else:
            b += 1
    return a

import sys

if (len(sys.argv)) > 2:
    print "error: this function takes a max of 1 argument"
elif (len(sys.argv)) == 2:
    print ProjectEulerFive(int(sys.argv[1]))
else:                          
    print ProjectEulerFive();

print "took " + str(time.time() - start_time ) + " seconds"

私のシステムでは約 8.5 秒かかります。

次に、他の人々のソリューションと比較することにしました。この Project Euler 5 in Python を見つけました - ソリューションを最適化するにはどうすればよいですか? .

一意素因数分解は考えていませんでした。

とにかく、そこに投稿された最適化された非素因数分解ベースのソリューションの1つ：

import time
start_time = time.time()

check_list = [11, 13, 14, 16, 17, 18, 19, 20]

def find_solution(step):
    for num in xrange(step, 999999999, step):
        if all(num % n == 0 for n in check_list):
            return num
    return None

if __name__ == '__main__':
    solution = find_solution(20)
    if solution is None:
        print "No answer found"
    else:
        print "found an answer:", solution

    print "took " + str(time.time() - start_time ) + " seconds"

私のシステムには約 37 秒かかります

3、4、5、6、7、8、9、10、および 12 の割り切れる可能性を不必要にチェックしているにもかかわらず、私のコードは約 4 倍高速です。

私はPythonを初めて使用し、非効率性がどこから来ているのかを理解するのに苦労しています。

編集：

私は別のテストをしました。

import time
start_time = time.time()

def ProjectEulerFive (m = 20):
    ls = [11, 13, 14, 15, 16, 17, 18, 19]
    a = m
    i = 0
    while i < len(ls):
        if ( a % ls[i]) != 0:
            a += m
            i = 0
            continue
        else:
            i += 1
    return a

print ProjectEulerFive();                           
print "took " + str(time.time() - start_time ) + " seconds"

私のシステムは6秒かかりますが、これは：

import time
start_time = time.time()

def ProjectEulerFive (m = 20):

    a = m
    start = 11

    b = start
    while b < m:
        if ( a % b) != 0:
           a += m
           b = start
           continue
        else:
            b += 1
    return a

print ProjectEulerFive()
print "took " + str(time.time() - start_time ) + " seconds"

約3.7秒

Answer 1

より迅速な解決策が投稿されていますが、実際に質問に答えた人はいません。実際、答えるのはかなり難しい問題です。基本的な説明は、関数呼び出しが比較的高価であるということです。ただし、この結論を説得力のあるものにするためには、Python の内部構造をかなり深く掘り下げる必要があります。覚悟を決める！

まず第一に、(あなたの 3 番目のバージョンの) を分解ProjectEulerFiveしfind_solution、dis.dis. ここにはたくさんありますが、コードが関数をまったく呼び出していないことを確認するために必要なのは、簡単なスキャンだけです。

>>> dis.dis(ProjectEulerFive)
  2           0 LOAD_FAST                0 (m)
              3 STORE_FAST               1 (a)

  3           6 LOAD_CONST               1 (11)
              9 STORE_FAST               2 (start)

  4          12 LOAD_FAST                2 (start)
             15 STORE_FAST               3 (b)

  5          18 SETUP_LOOP              64 (to 85)
        >>   21 LOAD_FAST                3 (b)
             24 LOAD_FAST                0 (m)
             27 COMPARE_OP               0 (<)
             30 POP_JUMP_IF_FALSE       84

  6          33 LOAD_FAST                1 (a)
             36 LOAD_FAST                3 (b)
             39 BINARY_MODULO       
             40 LOAD_CONST               2 (0)
             43 COMPARE_OP               3 (!=)
             46 POP_JUMP_IF_FALSE       71

  7          49 LOAD_FAST                1 (a)
             52 LOAD_FAST                0 (m)
             55 INPLACE_ADD         
             56 STORE_FAST               1 (a)

  8          59 LOAD_FAST                2 (start)
             62 STORE_FAST               3 (b)

  9          65 JUMP_ABSOLUTE           21
             68 JUMP_ABSOLUTE           21

 11     >>   71 LOAD_FAST                3 (b)
             74 LOAD_CONST               3 (1)
             77 INPLACE_ADD         
             78 STORE_FAST               3 (b)
             81 JUMP_ABSOLUTE           21
        >>   84 POP_BLOCK           

 12     >>   85 LOAD_FAST                1 (a)
             88 RETURN_VALUE        

find_solutionでは、次を見てみましょう。

>>> dis.dis(find_solution)
  2           0 SETUP_LOOP              58 (to 61)
              3 LOAD_GLOBAL              0 (xrange)
              6 LOAD_FAST                0 (step)
              9 LOAD_CONST               1 (999999999)
             12 LOAD_FAST                0 (step)
             15 CALL_FUNCTION            3
             18 GET_ITER            
        >>   19 FOR_ITER                38 (to 60)
             22 STORE_DEREF              0 (num)

  3          25 LOAD_GLOBAL              1 (all)
             28 LOAD_CLOSURE             0 (num)
             31 BUILD_TUPLE              1
             34 LOAD_CONST               2 (<code object <genexpr> at 
                                            0x10027eeb0, file "<stdin>", 
                                            line 3>)
             37 MAKE_CLOSURE             0
             40 LOAD_GLOBAL              2 (check_list)
             43 GET_ITER            
             44 CALL_FUNCTION            1
             47 CALL_FUNCTION            1
             50 POP_JUMP_IF_FALSE       19

  4          53 LOAD_DEREF               0 (num)
             56 RETURN_VALUE        
             57 JUMP_ABSOLUTE           19
        >>   60 POP_BLOCK           

  5     >>   61 LOAD_CONST               0 (None)
             64 RETURN_VALUE        

(a) このコードはそれほど複雑ではありませんが、(b) 3 つの異なる関数も呼び出していることがすぐにわかります。最初の呼び出しは単純に への 1 回の呼び出しxrangeですが、他の 2 つの呼び出しは最も外側の for ループ内に表示されます。最初の呼び出しはall;への呼び出しです。2 つ目は、ジェネレーター式のnextメソッドが呼び出されていることだと思います。しかし、関数が何であるかは問題ではありません。重要なのは、それらがループ内で呼び出されることです。

さて、「何が大変なの？」と思うかもしれません。ここ。これは単なる関数呼び出しです。あちこちで数ナノ秒ですよね？しかし実際には、それらのナノ秒が加算されます。最も外側のループは合計ループを通過するため、232792560 / 20 == 11639628オーバーヘッドは1,100 万倍以上になります。%timeitのコマンドを使用した簡単なタイミングipythonは、関数呼び出し (すべてそれ自体) が私のマシンで約 120 ナノ秒かかることを示しています。

>>> def no_call():
...     pass
... 
>>> def calling():
...     no_call()
...     
>>> %timeit no_call()
10000000 loops, best of 3: 107 ns per loop
>>> %timeit calling()
1000000 loops, best of 3: 235 ns per loop

そのため、while ループ内に現れる関数呼び出しごとに、120 nanoseconds * 11000000 = 1.32 secondsより多くの時間が費やされます。そして、2 番目の関数呼び出しがジェネレーター式のnextメソッドの呼び出しであることが正しければ、その関数は、genex を介した反復ごとに 1 回、さらに何度も呼び出されます。おそらく、平均してループごとに 3 ～ 4 回です。

次に、この仮説をテストします。関数呼び出しが問題である場合は、関数呼び出しを排除することが解決策です。どれどれ...

def find_solution(step):
    for num in xrange(step, 999999999, step):
        for n in check_list:
            if num % n != 0:
                break
        else:
            return num
    return None

これは、構文を使用して元のバージョンとfind_solutionほぼ同じことを行うバージョンです。for/else唯一の関数呼び出しは外側の toxrangeであり、これは問題を引き起こさないはずです。さて、元のバージョンの時間を計測すると、11 秒かかりました。

found an answer: 232792560
took 11.2349967957 seconds

この新しく改善されたバージョンが管理するものを見てみましょう。

found an answer: 232792560
took 2.12648200989 seconds

ProjectEulerFiveこれは、私のマシンでの最速バージョンのパフォーマンスよりも高速です。

232792560
took 2.40848493576 seconds

そして、すべてが再び理にかなっています。

Answer 2

これにはほとんど時間がかかりません。

def gcd(a, b):
    if (b == 0): return a
    else: return gcd(b, a%b)

def lcm(a, b):
    return abs(a*b) / gcd(a, b)

def euler5(n):
    if (n == 1): return 1
    else: return lcm(n, euler5(n-1))

print euler5(20)

Answer 3

あなたの質問への回答ではありません (したがって、コミュニティ wiki) が、タイミング関数の便利なデコレータを次に示します。

from functools import wraps
import time

def print_time(f):
    @wraps(f)
    def wrapper(*args, **kwargs):
        t0 = time.time()
        result = f(*args, **kwargs)
        print "{0} took {1}s".format(f.__name__, time.time() - t0)
        return result
    return wrapper

使用方法は次のとおりです。

@print_time
def foo(x, y):
    time.sleep(1)
    return x + y

そして実際には：

>>> foo(1, 2)
foo took 1.0s
3