5

私はこのコードを持っています:

import Data.List

newList_bad  lst = foldl' (\acc x -> acc ++ [x*2]) [] lst
newList_good lst = foldl' (\acc x -> x*2 : acc) [] lst

これらの関数は、各要素に 2 を掛けたリストを返します。

*Main> newList_bad [1..10]
[2,4,6,8,10,12,14,16,18,20]
*Main> newList_good [1..10]
[20,18,16,14,12,10,8,6,4,2]

ghci で:

*Main> sum $ newList_bad [1..15000]
225015000
(5.24 secs, 4767099960 bytes)
*Main> sum $ newList_good [1..15000]
225015000
(0.03 secs, 3190716 bytes)

newList_bad関数の動作が の 200 倍遅いのはなぜnewList_goodですか? それがそのタスクの良い解決策ではないことを理解しています。しかし、なぜこの無害なコードの動作がこれほど遅いのでしょうか?

この「4767099960バイト」とは何ですか?? その単純な操作のために、Haskell は 4 GiB を使用しました??

コンパイル後:

C:\1>ghc -O --make test.hs
C:\1>test.exe
225015000
Time for sum (newList_bad [1..15000]) is 4.445889s
225015000
Time for sum (newList_good [1..15000]) is 0.0025005s
4

3 に答える 3

19

この問題については多くの混乱があります。与えられる通常の理由は、「リストの最後に繰り返し追加するには、リストを繰り返しトラバースする必要があるため、O(n^2)」ということです。しかし、それは厳密な評価の下では非常に単純です。遅延評価では、すべてが遅延することになっているため、これらの繰り返しのトラバーサルと追加が実際にあるかどうかという疑問が生じます。最後に追加することは、前に消費することによってトリガーされます。また、前に消費するため、リストが短くなっているため、これらのアクションの正確なタイミングは不明です。したがって、実際の答えはより微妙であり、遅延評価の下で特定の削減ステップを扱います。

直接の原因はfoldl'、アキュムレータの引数を弱いヘッドの通常の形式に強制することです。つまり、厳密でないコンストラクタが公開されるまでです。ここに含まれる機能は

(a:b)++c = a:(b++c)    -- does nothing with 'b', only pulls 'a' up
[]++c = c              -- so '++' only forces 1st elt from its left arg

foldl' f z [] = z
foldl' f z (x:xs) = let w=f z x in w `seq` foldl' f w xs

sum xs = sum_ xs 0     -- forces elts fom its arg one by one
sum_ [] a = a
sum_ (x:xs) a = sum_ xs (a+x)

したがって、実際の削減シーケンスは（with g = foldl' f）

sum $ foldl' (\acc x-> acc++[x^2]) []          [a,b,c,d,e]
sum $ g  []                                    [a,b,c,d,e]
      g  [a^2]                                   [b,c,d,e]
      g  (a^2:([]++[b^2]))                         [c,d,e]
      g  (a^2:(([]++[b^2])++[c^2]))                  [d,e]
      g  (a^2:((([]++[b^2])++[c^2])++[d^2]))           [e]
      g  (a^2:(((([]++[b^2])++[c^2])++[d^2])++[e^2]))   []
sum $ (a^2:(((([]++[b^2])++[c^2])++[d^2])++[e^2]))

これまでに実行したのは手順のみであることに注意してくださいO(n)。 の消費のa^2ためにここですぐに利用できますが、そうではありません。ここでは、左にネストされた式の構造が残っています。残りはダニエルフィッシャーによるこの答えで最もよく説明されます。その要点は、抜け出すために手順を実行する必要があるということです-そして、このアクセスの結果として残された構造はまだネストされたままなので、次のアクセスは手順を実行します、など-古典的な動作。したがって、本当の理由は、効率を上げるのに十分な引数を強制または再配置していないということです。sumb^2++b^2O(n-1)O(n-2)O(n^2)++

これは実際には直感に反します。ここでは、遅延評価が魔法のように「実行」することが期待できます。結局のところ、私たちは将来[x^2]リストの最後に追加する意図を表明しているだけであり、実際にはすぐには追加しません。したがって、ここでのタイミングはずれていますが、正しく行うことができます。リストにアクセスすると、新しい要素がリストに追加され、タイミングが正しければすぐに消費されます。 ）、たとえば、（時間内に）消費される直前に、トラバーサル/アクセスは常にになります。c^2b^2 b^2O(1)

これは、いわゆる「差分リスト」手法で実現されます。

newlist_dl lst = foldl' (\z x-> (z . (x^2 :)) ) id lst

ちょっと考えてみると、あなたの++[x^2]バージョンとまったく同じに見えます。同じ意図を表現し、左ネスト構造も残します。

違いは、Daniel Fischerによる同じ回答で説明されているように、(.)チェーンは、最初に強制されると、段階的に右ネスト構造1に再配置($)され、その後、各アクセスが行われ、追加のタイミングが正確に説明されているように最適になることです。上記の段落なので、全体的な動作が残ります。O(n)O(1)O(n)

1これは一種の魔法ですが、実際に起こります。:)

于 2013-02-18T18:10:27.277 に答える
15

古典的なリストの動作。

想起：

(:)  -- O(1) complexity
(++) -- O(n) complexity

したがって、O(n) アルゴリズムではなく、O(n^2) アルゴリズムを作成しています。

リストに段階的に追加するこの一般的なケースでは、dlistを使用するか、最後に逆にしてみてください。

于 2013-02-18T14:41:08.430 に答える
3

少し大きな視点で他の回答を補完するには、遅延リストでfoldl'は、リストを返す関数で使用することは通常悪い考えです。 foldl'これは、リストを厳密な (非遅延) スカラー値に縮小する場合 (たとえば、リストの合計) に役立つことがよくあります。しかし、結果としてリストを作成している場合foldrは、怠惰のため、通常はより優れています。コンストラクターは遅延して:いるため、実際に必要になるまでリストの末尾は計算されません。

あなたの場合：

newList_foldr lst = foldr (\x acc -> x*2 : acc) [] lst

これは実際には次と同じmap (*2)です:

newList_foldr lst = map (*2) lst
map f lst = foldr (\x acc -> f x : acc) [] lst

評価 (最初のmap-less 定義を使用):

newList_foldr [1..10] 
  = foldr (\x acc -> x*2 : acc) [] [1..10]
  = foldr (\x acc -> x*2 : acc) [] (1:[2..10])
  = 1*2 : foldr (\x rest -> f x : acc) [] [2..10]

これは、Haskell がいつnewList [1..10]強制されたかを評価するのとほぼ同じです。この結果の消費者がそれを要求した場合にのみ、さらに評価を行い、消費者を満足させるのに必要なだけ評価します。たとえば、次のようになります。

firstElem [] = Nothing
firstElem (x:_) = Just x

firstElem (newList_foldr [1..10])
  -- firstElem only needs to evaluate newList [1..10] enough to determine 
  -- which of its subcases applies—empty list or pair.
  = firstElem (foldr (\x acc -> x*2 : acc) [] [1..10])
  = firstElem (foldr (\x acc -> x*2 : acc) [] (1:[2..10]))
  = firstElem (1*2 : foldr (\x rest -> f x : acc) [] [2..10])
  -- firstElem doesn't need the tail, so it's never computed!
  = Just (1*2)

これは、foldr-basednewListが無限リストでも機能することも意味します。

newList_foldr [1..] = [2,4..]
firstElem (newList_foldr [1..]) = 2

一方、を使用する場合はfoldl'、常にリスト全体を計算する必要があります。これは、無限リストを操作できないことも意味します。

firstElem (newList_good [1..])    -- doesn't terminate

firstElem (newList_good [1..10])
  = firstElem (foldl' (\acc x -> x*2 : acc) [] [1..10])
  = firstElem (foldl' (\acc x -> x*2 : acc) [] (1:[2..10]))
  = firstElem (foldl' (\acc x -> x*2 : acc) [2] [2..10])
  -- we can't short circuit here because the [2] is "inside" the foldl', so 
  -- firstElem can't see it
  = firstElem (foldl' (\acc x -> x*2 : acc) [2] (2:[3..10]))
  = firstElem (foldl' (\acc x -> x*2 : acc) [4,2] [3..10])
    ...
  = firstElem (foldl' (\acc x -> x*2 : acc) [18,16,14,12,10,8,6,4,2] (10:[]))
  = firstElem (foldl' (\acc x -> x*2 : acc) [20,18,16,14,12,10,8,6,4,2] [])
  = firstElem [20,18,16,14,12,10,8,6,4,2]
  = firstElem (20:[18,16,14,12,10,8,6,4,2])
  = Just 20

foldrに基づくアルゴリズムは を計算するのに 4 ステップかかりましたが、firstElem_foldr (newList [1..10])に基づくアルゴリズムfoldl'は 21 ステップのオーダーでした。さらに悪いことに、4 つのステップは一定のコストですが、21 は入力リストの長さに比例します。<code>firstElem (newList_good [1..150000]) は 300,001 ステップかかりますfirstElem (newList_foldr [1..150000]がfirstElem (newList_foldr [1..]、その問題。

また、一定のスペースと一定の時間で実行されることに注意してくださいfirstElem (newList_foldr [1.10])（一定のスペース以上を割り当てるには、一定以上の時間が必要です）。foldl厳密な言語からのプロトリズム—「foldl末尾再帰であり、定数空間で実行され、foldr末尾再帰ではなく、線形空間で実行されるか、さらに悪い」—Haskellでは当てはまりません。

于 2013-02-18T18:57:55.803 に答える