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

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

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

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

Q&A

解決済

3回答

2050閲覧

再帰処理においてタイムアウトしてしまう

sino_prtyo

総合スコア15

Python 3.x

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

0グッド

0クリップ

投稿2018/09/08 18:44

前提・実現したいこと

CheckioのProbability_diceという問題を解くためのコードを書いたのですが、再帰処理を使っているせいで引数の値が大きくなると計算時間が遅くなり、タイムアウトしてしまいます
より高速に計算できる方法を教えていただきたいです

Probability_dice
複数のさいころ(dice_number)を振ってさいころの合計値が所望の値(target)になる確率を求める。ただしさいころはsides面体であり、立方体とは限らない。

発生している問題・エラーメッセージ

処理がタイムアウトします

該当のソースコード

def probability(dice_number,sides,target): def indefinite_equation(x_num,total,sides,ans=0): if((total)<=0): ans += 0 elif((x_num==1)and(1<=(total)<=sides)): ans += 1 elif(x_num==1): ans += 0 else: for i in range(1,sides+1): ans += indefinite_equation(x_num-1,total-i,sides) return ans return indefinite_equation(dice_number,target,sides)/sides**dice_number

試したこと

ここに問題に対して試したことを記載してください。

補足情報(FW/ツールのバージョンなど)

ここにより詳細な情報を記載してください。

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

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

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

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

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

guest

回答3

0

ベストアンサー

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

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

0

lru_cacheを使用して再帰関数の処理を高速化する手法もありますよ。
(ただし、ご質問のケースで制限時間に間に合うようになるかは不明)

プログラミングスキルチェック問題でよくあるフィボナッチ数の計算など、同じ関数を繰り返し呼び出す処理をお手軽に高速化できるので覚えておくと役に立ちます。

使い方は以下のようなイメージになります。

python

1from functools import lru_cache 2 3def probability(dice_number,sides,target): 4 @lru_cache(maxsize=None) 5 def indefinite_equation(x_num,total,sides,ans=0): 6 # <以下省略> 7

投稿2018/09/09 05:51

退会済みユーザー

退会済みユーザー

総合スコア0

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

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

0

まずは、

ans += 0

の文は無意味なので、これ及びこれに係る条件式は省略できますね。
あと、この程度のコード量なら再帰にせず、ループで実装できるんじゃないでしょうか。
再帰は関数呼び出しが行われるため、遅いですよ。

投稿2018/09/08 22:28

y_waiwai

総合スコア87719

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

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問