foldl は末尾再帰的ですが、なぜ、foldr は、foldl よりも高速に実行されるのでしょうか?
https://stackoverflow.com/questions/3429634
-
26-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
私はfoldlとfoldrをテストしたかったのです。私が見たところ、末尾再帰の最適化のため、可能な限り、foldr ではなくfoldl を使用する必要があります。
意味あり。ただし、このテストを実行した後、私は混乱しています。
foldr (time コマンドを使用する場合は 0.057 秒かかります):
a::a -> [a] -> [a]
a x = ([x] ++ )
main = putStrLn(show ( sum (foldr a [] [0.. 100000])))
foldl (time コマンドを使用する場合は 0.089 秒かかります):
b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])
main = putStrLn(show ( sum (foldl b [] [0.. 100000])))
この例が些細な例であることは明らかですが、なぜfoldrがfoldlに勝つのかがわかりません。これは、foldl が勝つ明らかなケースではないでしょうか?
解決
遅延評価の世界へようこそます。
あなたは厳格な評価の観点からそれについて考える、foldlのルックス「良い」とfoldrルックス「悪い」foldlのは、テール再帰的ですが、foldrは、それが最初の最後の項目を処理できるように、スタック内のタワーを建設しなければならないので、ます。
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
これは、あまりにも良いではないでしょう。効率的にそれを行うための唯一の方法は、逆の要素を構築することです、それはそうです。
これはmapがfoldrの観点から説明できることが判明します：
map f xs = foldr (\x ys -> f x : ys) [] xs
それはそれを見て、伝えるのは難しいですが、遅延評価キックfoldrはすぐにその最初の引数をf与えることができるためでます：
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
fによって定義mapは単に最初のパラメータを使用して結果リストの最初の項目を返すことができるので、、折り目は一定の間隔で遅延して動作することができる。
Haskellはそれをどのように評価するかで見てみましょう。
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
sum = foldl (+) 0
sum [1..1000000] = foldl (+) 0 [1..1000000]
= foldl (+) ((+) 0 1) [2..1000000]
= foldl (+) ((+) ((+) 0 1) 2) [3..1000000]
= foldl (+) ((+) ((+) ((+) 0 1) 2) 3) [4..1000000]
...
= (+) ((+) ((+) (...) 999999) 1000000)
Haskellのは、それが行くように加算を実行するのが面倒です。代わりに、番号を取得することを強制する必要が未評価のサンクのタワーで終わります。それはすべてのサンクを評価するために深く再帰することがあるので、スタックオーバーフローが、この評価の際に発生します。
foldl'に特別な機能があります。 foldl' (+) 0 [1..1000000]は、スタックオーバーフローしません。 （注：私はあなたのテストでfoldlでfoldl'を交換しようとしたが、それは実際にそれが実行速度が遅くなった。） 他のヒント
編集：にこの問題を再度思い現在のすべての説明やや不十分なので立ちたいと思っていまく説明をします。
の違いがどのよう foldl や foldr 用削減機能です。を見る foldr まで拡大して
foldr (\x -> [x] ++ ) [] [0..10000]
[0] ++ foldr a [] [1..10000]
[0] ++ ([1] ++ foldr a [] [2..10000])
...
このリストで処理することにより、 sum, は、消費が
sum = foldl' (+) 0
foldl' (+) 0 ([0] ++ ([1] ++ ... ++ [10000]))
foldl' (+) 0 (0 : [1] ++ ... ++ [10000]) -- get head of list from '++' definition
foldl' (+) 0 ([1] ++ [2] ++ ... ++ [10000]) -- add accumulator and head of list
foldl' (+) 0 (1 : [2] ++ ... ++ [10000])
foldl' (+) 1 ([2] ++ ... ++ [10000])
...
私は左側のリストを連結したものの、この削減に一致する結果を得た.の重要な部分は、絞り加工を最小にするためのリストtraversals.の foldr のみを横断のリストを一度にconcatenationsを必要としない連続リストtraversals、 sum 最後に消費、リストの一つ。批判的に、ヘッドのリストから foldr すぐ sum, ので、 sum できる限り早い時期に赴任と価値観をgcによって生成されます。核融合の枠組みなど vector, であっても、中間リストが融合します。
ここに foldl 機能：
b xs = ( ++xs) . (\y->[y])
foldl b [] [0..10000]
foldl b ( [0] ++ [] ) [1..10000]
foldl b ( [1] ++ ([0] ++ []) ) [2..10000]
foldl b ( [2] ++ ([1] ++ ([0] ++ [])) ) [3..10000]
...
ご注意現在のヘッドのリストになるまで foldl は終了いたしました。このリストを構築することが必要である前にメモリに sum 組み込むことができます。することなどを明らかに。走行、二つのバージョン +RTS -s を示す悲惨なゴミの回収パフォーマンスからのfoldlバージョン。
この場合も foldl' ません。追加された厳しさの foldl' なに働きかけることによって、中間リストを作成します。のヘッドのリストは利用不可でfoldl'が終了し、その結果は、まだ遅くなることによ foldr.
私は以下のルールを決める最高の選択 fold
- のために折る 削減, -利用
foldl'（例：ここでも快適にお過ごしいただけ/最終のフォーカストラバーサル) - その利用
foldr. - 使用しない
foldl.
ほとんどの場合 foldr 最高の倍のニーズが高まったことから、フォーカストラバーサル方向に最適な怠け者評価の一覧表も掲載しています。また、一つだけで加工可能な限りのリストが表示されます。の厳しさの foldl' できるので場合に、このかさからするお客様にはお勧めです。ると、その構造がどのぐさです。
私は誰の考えていない、実際にこの1上の本当の答えは、まだ言った私は（も真であるとdownvotesを歓迎して）何かが欠けている場合を除きます。
私はこのケースで異なる最大のfoldrは、このようなリストを構築することだと思います
[0] ++（[1] ++（[2] ++（... ++ [1000000]）））
foldlは次のようにリストを作成に対します：
（（（[0] ++ [1]）++ [2]）++ ...）++ [999888]）++ [999999]）++ [1000000]
foldrバージョン++に常にその左引数として一つだけのリスト要素を持っていることを微妙な、しかし、予告の違い。 foldlのバージョンでは、（平均の周り500000上）++の左引数で999999個の要素が、右引数で一つだけの要素にそこまでされます。
++は、左の引数のサイズに時間比例を取りますそれは実際に）コピーを行う必要があります。それがどのように大きな問題ではありませんので、右側の引数リストは、変更されません。
foldlバージョンは非常に遅い理由です。それは私の意見では怠惰とは何の関係も持っていないいます。
問題は、末尾再帰の最適化はメモリの最適化であり、実行時間の最適化ではないことです。
末尾再帰の最適化により、再帰呼び出しごとに値を記憶する必要がなくなります。
つまり、foldl は実際には「良い」ものであり、foldr は「悪い」ものです。
たとえば、foldr とfoldl の定義を考えてみます。
foldl f z [] = z
foldl f z (x:xs) = foldl f (z `f` x) xs
foldr f z [] = z
foldr f z (x:xs) = x `f` (foldr f z xs)
これが式「foldl (+) 0 [1,2,3]」の評価方法です。
foldl (+) 0 [1, 2, 3]
foldl (+) (0+1) [2, 3]
foldl (+) ((0+1)+2) [3]
foldl (+) (((0+1)+2)+3) [ ]
(((0+1)+2)+3)
((1+2)+3)
(3+3)
6
foldl は値 0、1、2... を覚えていませんが、式全体 (((0+1)+2)+3) を引数として遅延的に渡し、最後の評価が行われるまで評価しないことに注意してください。 foldl では、基本ケースに到達し、まだ評価されていない 2 番目のパラメーター (z) として渡された値を返します。
一方、foldr は次のように動作します。
foldr (+) 0 [1, 2, 3]
1 + (foldr (+) 0 [2, 3])
1 + (2 + (foldr (+) 0 [3]))
1 + (2 + (3 + (foldr (+) 0 [])))
1 + (2 + (3 + 0)))
1 + (2 + 3)
1 + 5
6
ここでの重要な違いは、foldl が最後の呼び出しで式全体を評価し、記憶されている値に到達するために戻る必要がなくなる点です。foldr は呼び出しごとに 1 つの整数を記憶し、呼び出しごとに加算を実行します。
foldr とfoldl は必ずしも同等ではないことに留意することが重要です。たとえば、ハグで次の式を計算してみます。
foldr (&&) True (False:(repeat True))
foldl (&&) True (False:(repeat True))
foldr とfoldl は、説明されている特定の条件下でのみ同等です。 ここ
(私の下手な英語ですみません)
[0.. 100000]リストはfoldrは、最後の要素で始めることができますので、すぐに拡張する必要があります。それは一緒に物事を折るなどし、中間結果である。
[100000]
[99999, 100000]
[99998, 99999, 100000]
...
[0.. 100000] -- i.e., the original list
は、コンパイラは値を再利用して自由です。 [99999, 100000]のような中間値が、でも代わりに別々のリストの拡大[0.. 100000]リストに単純にポインタすることができます。
Bの場合、中間値を見てみます：
[0]
[0, 1]
[0, 1, 2]
...
[0, 1, ..., 99999]
[0.. 100000]
は、それらの中間の各リストは、再利用することはできません。あなたは、メモリ内のビルドに時間がかかる余分なリストの束を作成しているので。したがって、この場合には、あなたは割り当て、中間値であり、これらのリストに記入し、より多くの時間を費やしています。
これは完全なリストを拡大することにより開始し、ちょうど前に、リストの後ろからポインタを移動し続けるので、あなただけの実行より速く、リストのコピーを作っているので。
どちらfoldlもfoldrはテール最適化です。それだけfoldl'です。
しかし、あなたの場合は++の連続した評価は何度も何度も成長しているアキュムレータを通過する原因となりますので、foldl'と++を使用することは良いアイデアではありません。
さて、私は差は明らかであるような方法で自分の関数を書き直してみましょう -
a :: a -> [a] -> [a]
a = (:)
b :: [b] -> b -> [b]
b = flip (:)
あなたは、bがより複雑であることがわかります。あなたは正確aになりたい場合に計算される値のための1つの還元工程を必要としますが、bは2を必要とします。それは多くの削減が行われなければならない二回と第二の例では、あなたが測定された時間差になります。
//編集：。しかし、私はずっとそれについて気にしないように、時間の複雑さは、同じである。
