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

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

ただいまの
回答率

91.37%

  • Python 3.x

    2395questions

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

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

解決済

回答 2

投稿 2017/11/25 19:22

  • 評価
  • クリップ 0
  • VIEW 76

simasima

score 38

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

def double(x):
    y = 2*x
    return y

def func_repeat(I):
    x = 1
    for i in  range(0, I):
        x = double(x)
    return x

arr = [func_repeat(j) for j in range(0,11)]


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

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

ご教授お願いします。

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

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

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

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

checkベストアンサー

+4

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

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

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

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

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

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

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

投稿 2017/11/25 19:43

編集 2017/11/25 21:00

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/11/25 20:01

    ありがとうございます!appendを利用するしかないかと思っていましたが、この方法が可読性や速度を考えるとベストのように思います。

    また、appendよりyieldの方が高速みたいですね。勉強になりました。
    ref. Which is generally faster, a yield or an append?
    https://stackoverflow.com/questions/3487802/which-is-generally-faster-a-yield-or-an-append

    キャンセル

  • 2017/11/25 20:08

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

    キャンセル

  • 2017/11/25 20:13

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

    キャンセル

  • 2017/11/25 20:46

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

    キャンセル

0

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

# -*- coding: utf-8 -*-
import timeit


def double(x):
    y = 2 * x
    return y


def func_repeat(I):
    x = 1
    for i in range(0, I):
        x = double(x)
    return x


def func_answer(I):
    return 2 ** I


def question():
    return [func_repeat(j) for j in range(0, 11)]


def answer():
    return [func_answer(j) for j in range(0, 11)]


def main():
    iteration = 100000
    print(timeit.timeit(question, number=iteration))
    print(question())
    print(timeit.timeit(answer, number=iteration))
    print(answer())


if __name__ == '__main__':
    main()


□参考情報
timeit

投稿 2017/11/25 20:22

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/11/25 20:38

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

    キャンセル

  • 2017/11/25 20:43

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

    キャンセル

  • 2017/11/25 20:52

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

    キャンセル

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

ただいまの回答率

91.37%

関連した質問

同じタグがついた質問を見る

  • Python 3.x

    2395questions

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