8

fある入力を受け入れて数値を生成する関数があると仮定します。関数内でf、入力に従ってリストが作成され、その後、（たとえばを使用してfoldl' g）縮小されて、最終的な出力番号が生成されます。g 結局、中間リストはリデュースされるので、中間リストを表現せずにリデュース機能を適用することは可能ですか。ここでの目標は、リストの保存（または、精度の低い単語を「保存」する場合は表現）に使用されるメモリを制限することです。

これを説明するために、この関数は中間リスト用のスペースをfoldPairProduct取りO(N1 * N2)ます（消費されるスペースは、式と遅延評価のために複雑になる可能性がありますが、比例またはそれより悪いと思います）。N1, N22つの入力リストのサイズは次のとおりです。

foldPairProduct :: (Num a, Ord a)  => (a -> a -> a) -> [a] -> [a] -> a
foldPairProduct f xs ys = foldl1 f [ x*y | x <- xs, y <- ys]

ロジックの代替実装はfoldPairProduct'で、これはO(2 * 2)スペースを取ります。

foldPairProduct' :: Num a => (Maybe a -> Maybe a -> Maybe a) -> [a] -> [a] -> Maybe a  
foldPairProduct' _ _ [] = Nothing
foldPairProduct' _ [] _ = Nothing
foldPairProduct' f (x:xs) (y:ys) = 
  foldl1 f [Just $ x*y, foldPairProduct' f [x] ys, foldPairProduct' f xs [y], 
            foldPairProduct' f xs ys]

複数のリストを入力として受け入れることを除いてfoldCrossProduct、実装が類似している場合、状況は悪化します。foldPairProduct中間リストのスペースの複雑さ（命令型言語の意味では）はO(N1 * N2 * ...* Nk)、です。ここkで、はの長さです[[a]]。

foldCrossProduct :: Num a => (a -> a -> a) -> [[a]]  -> a
foldCrossProduct f xss = foldl1 f (crossProduct xss)

crossProduct :: Num a => [[a]] -> [a]
crossProduct [] = []
crossProduct (xs:[]) = xs
crossProduct (xs:xss) = [x * y | x <- xs, y <- crossProduct xss]

の実装アイデアに従った場合foldPairProduct'、スペースの複雑さはk^2、はるかにスペース効率が高くなります。私の質問は次のとおりです。

  1. foldPairProduct'私はリストのペアのために実装しました。ただし、任意の数のリストに実装するのは簡単ではないようです。

  2. Haskellを命令型言語と比較するつもりはありませんが、一定のスペースを使用する（つまり、言及された長さの中間リストを表現せずに）実装はありますか？たぶんモナドは助けになるでしょうが、私はそれにとても慣れていません。

  3. コンパイラは実際にその魔法を実行しますか？つまり、リストが中間であり、削減されることに気づき、実際にスペース効率でリストを評価する方法を見つけ出します。結局のところ、それが遅延評価とコンパイラ最適化が設計されていると私が思ったものです。

  4. コメントは大歓迎です。ありがとう。

アップデート1

パフォーマンステストでは、入力サイズの変化に基づいて、foldPairProductおよびの「スペースの複雑さ」に関する分析と、 GCによってコピーされたバイト数の観察が確認されました。 foldCrossProductN1, N2, N3

パフォーマンステストは、foldPairProduct'驚くべきことにN1 * N2、またはさらに悪いスペース使用量を示した分析を否定します。これはおそらく、再帰呼び出しが非効率的に評価されているためです。結果は以下に添付されています（ghc設定はYurasが行ったものと同じです）。

アップデート2

コメントと回答から学んだように、いくつかのさらなる実験を更新しました。の場合、使用中のメモリfoldPairProductの合計は、DanielFischerが説明したスペースの複雑さと一致しています。

なぜならfoldCrossProduct、ダニエルの複雑さの分析は私には理にかなっていますが、結果は線形のメモリ使用量を示していません。ダニエルのアドバイスに従って、とを入れ替えるx <- xsとy <- crossproduct ys、実際に線形空間の複雑さが実現します。

の場合foldCrossProduct (max) [[1..100],[1..n], [1..1000]]、n = 100、1000、10000、100000の場合、使用されるメモリは2、2、3、14MBです。

foldPairProduct [1..n] [1..10000]

n = 100
  120,883,320 bytes allocated in the heap 
   56,867,728 bytes copied during GC
      428,384 bytes maximum residency (50 sample(s)) 
       98,664 bytes maximum slop
            3 MB total memory in use (0 MB lost due to fragmentation)     

n = 1000
 1,200,999,280 bytes allocated in the heap 
   569,837,360 bytes copied during GC   
       428,384 bytes maximum residency (500 sample(s))
        99,744 bytes maximum slop 
             3 MB total memory in use (0 MB lost due to fragmentation) 
n = 10000

  12,002,152,040 bytes allocated in the heap
   5,699,468,024 bytes copied during GC 
         428,384 bytes maximum residency (5000 sample(s))
          99,928 bytes maximum slop 
               3 MB total memory in use (0 MB lost due to fragmentation)

n = 100000

 120,013,672,800 bytes allocated in the heap 
  56,997,625,608 bytes copied during GC 
         428,384 bytes maximum residency (50000 sample(s)) 
          99,984 bytes maximum slop 
               3 MB total memory in use (0 MB lost due to fragmentation)

foldPairProduct [1..10000] [1..n]

n = 100

     121,438,536 bytes allocated in the heap 
          55,920 bytes copied during GC     
          32,408 bytes maximum residency (1 sample(s)) 
          19,856 bytes maximum slop  
               1 MB total memory in use (0 MB lost due to fragmentation)

n = 1000

   1,201,511,296 bytes allocated in the heap 
         491,864 bytes copied during GC     
          68,392 bytes maximum residency (1 sample(s)) 
          20,696 bytes maximum slop                   
               1 MB total memory in use (0 MB lost due to fragmentation)

n = 10000

  12,002,232,056 bytes allocated in the heap 
   5,712,004,584 bytes copied during GC     
         428,408 bytes maximum residency (5000 sample(s)) 
          98,688 bytes maximum slop 
               3 MB total memory in use (0 MB lost due to fragmentation)

n = 100000

 120,009,432,816 bytes allocated in the heap
  81,694,557,064 bytes copied during GC 
       4,028,408 bytes maximum residency (10002 sample(s))
         769,720 bytes maximum slop 
              14 MB total memory in use (0 MB lost due to fragmentation)

foldPairProduct [1..n] [1..n]

n = 100
 1,284,024 bytes allocated in the heap
    15,440 bytes copied during GC
    32,336 bytes maximum residency (1 sample(s))
    19,920 bytes maximum slop                  
         1 MB total memory in use (0 MB lost due to fragmentation)  

n = 1000
 120,207,224 bytes allocated in the heap  
     114,848 bytes copied during GC 
      68,336 bytes maximum residency (1 sample(s)) 
      24,832 bytes maximum slop 
           1 MB total memory in use (0 MB lost due to fragmentation)  

n = 10000

  12,001,432,024 bytes allocated in the heap 
   5,708,472,592 bytes copied during GC 
         428,336 bytes maximum residency (5000 sample(s)) 
          99,960 bytes maximum slop 
               3 MB total memory in use (0 MB lost due to fragmentation) 

n = 100000
 1,200,013,672,824 bytes allocated in the heap 
   816,574,713,664 bytes copied during GC 
         4,028,336 bytes maximum residency (100002 sample(s)) 
           770,264 bytes maximum slop 
                14 MB total memory in use (0 MB lost due to fragmentation)

foldCrossProduct（max）[[1..n]、[1..100]、[1..1000]]

n = 100
     105,131,320 bytes allocated in the heap 
      38,697,432 bytes copied during GC     
         427,832 bytes maximum residency (34 sample(s)) 
         209,312 bytes maximum slop 
               3 MB total memory in use (0 MB lost due to fragmentation)

n = 1000
   1,041,254,480 bytes allocated in the heap 
     374,148,224 bytes copied during GC 
         427,832 bytes maximum residency (334 sample(s))
         211,936 bytes maximum slop 
               3 MB total memory in use (0 MB lost due to fragmentation)

n = 10000
  10,402,479,240 bytes allocated in the heap 
   3,728,429,728 bytes copied during GC     
         427,832 bytes maximum residency (3334 sample(s))
         215,936 bytes maximum slop
               3 MB total memory in use (0 MB lost due to fragmentation)

foldCrossProduct（max）[[1..100]、[1..n]、[1..1000]]

n = 100
     105,131,344 bytes allocated in the heap 
      38,686,648 bytes copied during GC  
         431,408 bytes maximum residency (34 sample(s)) 
         205,456 bytes maximum slop 
               3 MB total memory in use (0 MB lost due to fragmentation)

n = 1000
   1,050,614,504 bytes allocated in the heap
     412,084,688 bytes copied during GC 
       4,031,456 bytes maximum residency (53 sample(s)) 
       1,403,976 bytes maximum slop
              15 MB total memory in use (0 MB lost due to fragmentation)    
n = 10000
    quit after over 1362 MB total memory in use (0 MB lost due to fragmentation)

foldPairProduct'[1..n] [1..n]

n = 100
 4,351,176 bytes allocated in the heap
    59,432 bytes copied during GC    
    74,296 bytes maximum residency (1 sample(s))
    21,320 bytes maximum slop                  
         1 MB total memory in use (0 MB lost due to fragmentation)

n = 1000
 527,009,960 bytes allocated in the heap 
  45,827,176 bytes copied during GC 
     211,680 bytes maximum residency (1 sample(s)) 
      25,760 bytes maximum slop 
           2 MB total memory in use (0 MB lost due to fragmentation)
4

3 に答える 3

4

（わかりました、私は間違っていました。リストの1つが複数回使用されているため、一定のスペースでは機能しません。したがって、線形スペースの複雑さが発生する可能性があります）

最適化を有効にしてテストプログラムをコンパイルしようとしましたか？あなたfoldPairProductは私にとって良さそうです、そして私はそれが一定の空間で働くことを期待しています。

追加：はい、一定のスペースで動作します（合計3 MBのメモリが使用されています）：

shum@shum-laptop:/tmp/shum$ cat test.hs 

foldPairProduct f xs ys = foldl1 f [ x*y | x <- xs, y <- ys]

n :: Int
n = 10000

main = print $ foldPairProduct (+) [1..n] [1..n]
shum@shum-laptop:/tmp/shum$ ghc --make -fforce-recomp -O test.hs 
[1 of 1] Compiling Main             ( test.hs, test.o )
Linking test ...
shum@shum-laptop:/tmp/shum$ time ./test +RTS -s
2500500025000000
  10,401,332,232 bytes allocated in the heap
   3,717,333,376 bytes copied during GC
         428,280 bytes maximum residency (3335 sample(s))
         219,792 bytes maximum slop
               3 MB total memory in use (0 MB lost due to fragmentation)

                                    Tot time (elapsed)  Avg pause  Max pause
  Gen  0     16699 colls,     0 par    4.27s    4.40s     0.0003s    0.0009s
  Gen  1      3335 colls,     0 par    1.52s    1.52s     0.0005s    0.0012s

  INIT    time    0.00s  (  0.00s elapsed)
  MUT     time    2.23s  (  2.17s elapsed)
  GC      time    5.79s  (  5.91s elapsed)
  EXIT    time    0.00s  (  0.00s elapsed)
  Total   time    8.02s  (  8.08s elapsed)

  %GC     time      72.2%  (73.2% elapsed)

  Alloc rate    4,659,775,665 bytes per MUT second

  Productivity  27.8% of total user, 27.6% of total elapsed


real    0m8.085s
user    0m8.025s
sys 0m0.040s
shum@shum-laptop:/tmp/shum$
于 2013-02-21T00:13:50.947 に答える
4

ループ融合と呼ばれるリストの作成/変更/消費には特定の最適化があります。Haskellは純粋で厳密ではないため、のような多くの法則がありmap f . mag g == map (f . g)ます。

コンパイラが何らかの理由でコードを認識せず、（フラグを渡した後）次善のコードを生成する場合は、-Oストリームフュージョンを詳細に調べて、何がそれを妨げているかを確認します。

于 2013-02-21T00:35:03.887 に答える
2 
foldPairProduct :: (Num a, Ord a)  => (a -> a -> a) -> [a] -> [a] -> a
foldPairProduct f xs ys = foldl1 f [ x*y | x <- xs, y <- ys]

良い思い出の市民になることができます。2番目の引数ysは繰り返し使用されるため、計算中に完全にメモリ内に存在する必要がありますが、中間リストは消費されるときに遅延生成されるため、一定量のメモリのみに寄与し、全体的なO(length ys)スペースが複雑になります。もちろん、length xs * length ysセルが生成および消費するリストが必要であるため、全体的な割り当てはO(length xs * length ys)[各a値が有界空間を使用すると仮定]です。GC中にコピーされるバイト数（したがって、GCに必要な時間）は、より大きな割り当て領域を提供することによって大幅に削減できます+RTS -A1M。

3,717,333,376 bytes copied during GC

デフォルト設定の場合

20,445,728 bytes copied during GC

GC time 4.88sとからGC time 0.07sの時間xs == ys = [1 .. 10000] :: [Int]とf = (+)。

しかし、それは厳密性アナライザーがその仕事をしていることに依存します-それが使用されているタイプが例えばIntコンパイル中に既知であり、結合関数が厳密であることがわかっている場合、それはうまくいきます。コードが特殊化されていない場合、または結合関数が厳密であることがわかっていない場合、折り畳みはO(length xs * length ys)サイズのサンクを生成します。この問題は、より厳密なを使用することで軽減できますfoldl1'。

foldPairProduct' :: Num a => (Maybe a -> Maybe a -> Maybe a) -> [a] -> [a] -> Maybe a  
foldPairProduct' _ _ [] = Nothing
foldPairProduct' _ [] _ = Nothing
foldPairProduct' f (x:xs) (y:ys) = 
  foldl1 f [Just $ x*y, foldPairProduct' f [x] ys, foldPairProduct' f xs [y], 
            foldPairProduct' f xs ys]

厳密性が不十分であるという問題に正面からぶつかります。Justコンストラクターによってラップされた値は、全体的な結果には必要ない可能性があるため、ここではコンパイラーによって厳密にすることはできませO(length xs * length ys)んJust。もちろん、一部の人にとってはf、のようconstに、そのまま動作します。すべての値が使用されている場合にそれが良い記憶市民であるためには、十分に厳密な結合関数を使用する必要があり、結果fの下の値も強制しますJust（それがaの場合Just）。使用するfoldl1'ことも役立ちます。これにより、O(length ys + length xs)スペースが複雑になる可能性があります（リストxsとysは複数回使用されるため、再利用されます）。

foldCrossProduct :: Num a => (a -> a -> a) -> [[a]]  -> a
foldCrossProduct f xss = foldl1 f (crossProduct xss)

crossProduct :: Num a => [[a]] -> [a]
crossProduct [] = []
crossProduct (xs:[]) = xs
crossProduct (xs:xss) = [x * y | x <- xs, y <- crossProduct xss]

GHCはCSE（共通部分式除去）をほとんど行いませんが、リストcrossProduct xssは（おそらく）ここで異なるxs間で共有されるため、O(N2*...*Nk)スペースが複雑になります。リスト内の要素の順序が重要でない場合は、次のように並べ替えます。

crossProduct (xs:xss) = [x * y | y <- crossProduct xss, x <- xs]

役立ちます。次にcrossProduct xss、一度にメモリに入れる必要はないので、段階的に生成および消費できますxs。複数回使用されるため、覚えておく必要があります。再帰呼び出しの場合、残りのリストの最初のリストを共有する必要があるため、全体的なO(N1+...+Nk-1)スペースが複雑になります。

于 2013-02-21T12:44:58.270 に答える