質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Q&A

解決済

2回答

2656閲覧

再帰関数のリスト内表記について

simasima

総合スコア49

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

0グッド

0クリップ

投稿2017/11/25 10:22

以下のような再帰関数のリスト内表記に関する簡単なプログラムの実行時間を削減したいと考えています。

python

1def double(x): 2 y = 2*x 3 return y 4 5def func_repeat(I): 6 x = 1 7 for i in range(0, I): 8 x = double(x) 9 return x 10 11arr = [func_repeat(j) for j in range(0,11)]

実行結果は以下のようになりますが、
[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]

毎回func_repeatを呼びだし、x=1から計算しているのが無駄だと思われます。
どのようにすればさらに高速化ができますでしょうか。

ご教授お願いします。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

0

ベストアンサー

こんな感じでしょうか。最後一回無駄な計算はしていますが。

Python

1>>> def func_repeat(I): 2... x = 1 3... for i in range(0, I): 4... yield x 5... x *= 2 6... 7>>> list(func_repeat(11)) 8[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]

そういえば、そもそもご提示のコードは再帰関数じゃないですね。
再帰を使って書くなら、こんな感じです。

Python

1>>> def recursive_func_repeat(I, ret): 2... if not I: 3... return ret 4... ret.append(2 * ret[-1]) 5... return recursive_func_repeat(I-1, ret) 6... 7>>> recursive_func_repeat(10, [1]) 8[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]

最終的にリストにするなら、ジェネレータとあまり性能差はないかと思います。
(追記:append呼び出しのオーバーヘッドに留意する必要はあります。)
再帰が深くなりすぎるとスタックから溢れますが...

Python

1>>> recursive_func_repeat(10000, [1]) 2Traceback (most recent call last): 3 File "<stdin>", line 1, in <module> 4 File "<stdin>", line 5, in recursive_func_repeat 5 File "<stdin>", line 5, in recursive_func_repeat 6 File "<stdin>", line 5, in recursive_func_repeat 7 [Previous line repeated 995 more times] 8RecursionError: maximum recursion depth exceeded

可読性に大きな差がないのであれば、再帰を積極的に採用する理由はないです。

投稿2017/11/25 10:43

編集2017/11/25 12:00
LouiS0616

総合スコア35658

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

LouiS0616

2017/11/25 11:08

使い方にもよりますが、ジェネレータの方が高速で簡潔であることが多いですね。 リンク先の回答に丁寧な解説があるので、そちらが理解できると効果的に用いられそうです。
simasima

2017/11/25 11:13

そうなのですね! ジェネレータはほぼ使ったことなかったので、これからも使っていきます。
simasima

2017/11/25 11:46

おっしゃる通りですね!題名が微妙でした... 最初は純数に再帰関数で書いていたのですが、スタック溢れがいやだったので単なるfor文で質問させていただきました。^ ^
guest

0

そもそも論としてべき乗演算子(**)を使用すればよいのではないでしょうか?
func_repeatを再帰にする必要がありますか?

Python

1# -*- coding: utf-8 -*- 2import timeit 3 4 5def double(x): 6 y = 2 * x 7 return y 8 9 10def func_repeat(I): 11 x = 1 12 for i in range(0, I): 13 x = double(x) 14 return x 15 16 17def func_answer(I): 18 return 2 ** I 19 20 21def question(): 22 return [func_repeat(j) for j in range(0, 11)] 23 24 25def answer(): 26 return [func_answer(j) for j in range(0, 11)] 27 28 29def main(): 30 iteration = 100000 31 print(timeit.timeit(question, number=iteration)) 32 print(question()) 33 print(timeit.timeit(answer, number=iteration)) 34 print(answer()) 35 36 37if __name__ == '__main__': 38 main() 39

□参考情報
timeit

投稿2017/11/25 11:22

umyu

総合スコア5846

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

simasima

2017/11/25 11:38

実際のプログラムはもっと複雑でしたので、もっとも簡単な例で質問させていただきました。
LouiS0616

2017/11/25 11:43

最終的にリストにするのなら、べき乗でも同じ計算を重複して行っていることに変わりないと思います。
umyu

2017/11/25 11:52

なるほどー。そういう要旨の質問でしたかー。失礼しました。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問