14

それで、私は再帰をアイドル状態でいじっていました.再帰を使用したループが通常のwhileループよりもはるかに遅いことに気付きました.誰かがその理由を知っているかどうか疑問に思っていました. 以下に行ったテストを含めました。

>>> import timeit
>>> setu="""def test(x):
    x=x-1
    if x==0:
        return x
    else:
        test(x)
    """
>>> setu2="""
x=10
while x>0:
    x=x-1
"""
>>> timeit.timeit(stmt="test(10)",setup=setu,number=100)
0.0006629826315997432
>>> timeit.timeit(stmt=setu2,number=100)
0.0002488750590750044
>>> setu="""def test(x):
    x=x-1
    if x==0:
        return x
    test(x)
    """
>>> timeit.timeit(stmt="test(10)",setup=setu,number=100)
0.0006419437090698921

しかし、前回のテストで、elseステートメントを取り出すとわずかに速度が向上していることに気付いたので、このループ速度の違いは if ステートメントが原因でしょうか?

4

2 に答える 2

24

関数を末尾再帰的に記述しました。多くの命令型および関数型言語では、これにより末尾再帰の排除がトリガーされます。コンパイラは命令の CALL/RETURN シーケンスを単純な JUMP に置き換え、プロセスを通常のスタック フレーム割り当てとは対照的に、反復とほぼ同じものにします。再帰関数呼び出しのオーバーヘッド。ただし、Python は、これらのリンクのいくつかで説明されているように、末尾再帰の削除を使用しません。

http://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

http://metapython.blogspot.com/2010/11/tail-recursion-elimination-in-python.html

リンクからわかるように、デフォルトでは存在しない理由があり、さまざまな方法でハッキングできますが、デフォルトでは、Python はジェネレーター関数などを使用して複雑な命令シーケンスを作成します。再帰。

于 2012-11-24T16:48:05.943 に答える
4

再帰は、新しいスタック フレームの割り当てが必要なため、(一般に) 反復に比べてかなりコストがかかります。

于 2012-11-24T16:20:45.000 に答える