3

https://softwareengineering.stackexchange.com/a/136146/18748の回答の1つで行われた主張は次のとおりです。

関数型言語を1つか2つ試してみてください。再帰を使用してErlangに階乗を実装してみて、20000のときに顎が床にぶつかるのを見てください！5秒で戻ります（サイトにスタックオーバーフローはありません）

Java / C / C ++ / Python（任意）で再帰/反復を使用するよりも高速/効率的であるのはなぜですか？これを実現する基礎となる数学的/理論的概念は何ですか？残念ながら、私は学部生（「C」で始まる）で関数型プログラミングに触れたことがなかったので、「なぜ」を知らないだけかもしれません。

4

4 に答える 4

1

テールコールの最適化

遅延評価：「遅延評価を使用する場合、式は変数にバインドされるとすぐに評価されませんが、評価者が式の値を生成することを強制されたときに評価されます。」

Clojure で階乗を実装するさまざまな方法に関するこの質問では、両方の概念が示されています。遅延シーケンスと TCO の詳細については、Stuart Halloway と Aaron Bedra の著書Programming Clojureにも記載されています。

Programming Clojure から採用された次の関数は、フィボナッチ数列の最初の 1M メンバーで遅延シーケンスを作成し、10 万番目のメンバーを実現します。

user=> (time (nth (take 1000000 (map first (iterate (fn [[a b]] [b (+ a b)]) [0N 1N]))) 100000))
"Elapsed time: 252.045 msecs"
25974069347221724166155034.... 
(20900 total digits)

(512MB ヒープ、Intel Core i7、2.5GHz)

于 2013-03-11T23:01:52.333 に答える
1

高速ではなく(何よりも?)、テール コールの最適化とは何の関係もありません (ここで流行語を投げかけるだけでは十分ではありません。テール コールの最適化がループよりも高速であるべき理由も説明する必要があります。単純にそうではありません! )

反対に、私は関数型プログラミングが嫌いではないことに注意してください! しかし、神話を広めることは、関数型プログラミングの根拠にはなりません。

ところで、ここで実際に20000!?

やった：

main _ = println (product [2n..20000n])

これは Java にコンパイルされた JVM 言語であり、Java の大きな整数を使用します (遅いことが知られています)。また、JVM の起動コストにも悩まされます。また、これは最速の方法ではありません (たとえば、明示的な再帰はリストの作成を節約できます)。

結果は次のとおりです。

181920632023034513482764175686645876607160990147875264
...
... many many lines with digits
...          
000000000000000000000000000000000000000000000000000000000000000

real    0m3.330s
user    0m4.472s
sys     0m0.212s

(Intel® Core™ i3 CPU M 350 @ 2.27GHz × 4)

C で GMP を使用しても、その時間の 50% も使用しないと安全に想定できます。

したがって、機能的であるほど速いというのは神話であり、機能的であるほど遅いです. それは神話でさえありません。より速い/遅いものと比較して言わない限り、それは単にナンセンスです。

于 2013-03-12T00:48:40.290 に答える