この短いアルゴリズムを書き直して効率を上げるには？

Question

この機能と同等の機能を書くには、ループを含まないでください？

Pythonコード：

luck = 0.3 
tries = 200000000 

getStrikes(): 
    strikes = 0 
    for i in range(tries): 
     if random.random() <= luck: 
      strikes++; 
    return strikes 

[OK]を、申し訳ありません私は、過去5分間にオリジナルのポストを編集するスパムしてきました。私が受け取ったフィードバックに基づいて尋ねたいことを明確にしたので、私は今停止します。

Answer 1

関数のプログラミングでは、折り畳みやリスト/生成子の解説のようないくつかのツールがありますが、最も基本的な考え方は再帰です。

ので、例えば、getTotal（）のために：私たちが最後に到達する前にスタックが長いオーバーフローするので

getTotal(sides, dice): 
    if dice == 0: 
     return 0 
    else 
     return rand.int(sides) + getTotal(sides, dice - 1) 

この機能、悲しいことに、あなたの具体的な例では動作しません。関数の末尾を再帰的にすることでその問題を解決するので、tail call optimizationを使用することができます（すべての言語でこの機能が使用されているわけではありませんが、ほとんどすべての関数型言語が使用します）。それは、0から始まるアキュムレータ変数追加することによって達成される：

getTotal(sides, dice, accumulator = 0): 
    if dice == 0: 
     return accumulator 
    else 
     return getTotal(sides, dice - 1, accumulator + rand.int(sides)) 

機能のこのバージョンでは、再帰呼び出しは、それが機能はありません非常に最後のものであることを意味し、「末尾呼び出し」、（あります以前のバージョンではそうではありませんが、追加は最後に起こるので、尾の再帰的なものではありません）。 getSixes()バージョンは同じ方法で行うことができます。ただし、ダイスロールをアキュムレータに追加するだけでなく、ロールがアキュムレータに対して6の場合にのみ1を加算します。

しかし、このパターンは多くの言語が「ショートカット」を持っているので、foldという一般的なパターンです。

def getTotal(sides, dice): 
    add = lambda x,y: x + y 
    return reduce(add, (rand.int(sides) for _ in range(dice))) 

reduceが左倍のためのPythonの名前であり、そしてaddたちは「関数である：私は表記の束を発明したくないので、私はPythonでこの次の例を書くつもりです折り返し(rand.int(sides) for _ in range(dice))部分は遅れて発生するジェネレータです（最初は一度にすべてではありません）。乱数（具体的にはdice）が生成されます。

機能プログラミングの別のトリックは、ブール関数に基づいて値を「フィルタリング」することです。ループを使用することは一般的に少し速く理由ですが、

def getSixes(sides, dice): 
    condition = lambda x: x == 6 
    return len(filter(condition, (rand.int(sides) for _ in range(dice)))) 

これらの方法のすべてがループを（つまり、同じビッグOの特性である）を使用したのと同じメモリ/速度特性を持っている：私たちはgetSixes()そのように解決することができますより少ないオーバーヘッドがあります。

編集：この回答は編集前の質問のバージョンに多く適用されますが、そのアイデアは新しいバージョンと非常によく似ています。

編集2：元のタイトルは、「ループを使用せずにこの問題をどのように書き換えますか」というものです。これは私の答えが当てはまるものです。私はあなたが私の答えが全く当てはまらない理由を数式が欲しいと気づいていませんでした。

Answer 2

strikesは、binomial distributionのランダム変数です。scipyは、Bernouilli trialsの膨大な数を合計するよりも効率的にこのディストリビューションからのサンプリングをサポートしています。ここで

は例です：臨床試験の数が多いにも関わらず

from scipy.stats import binom 

luck = 0.3 
trials = 200000000 
print binom(trials, luck).rvs() 

、これは、ほぼ瞬時に実行されます。