28

リストを処理し、追加の値（通常は関数が生成された時点では存在しません）を受け取った後、その要素を使用して何かを実行する関数を構築する関数型言語の例をたくさん見てきました。

  • 各要素と平均の差を計算する

    （「遅延評価」の最後の2つの例）

  • リストのステージングは​​、ML / OCamlなどの厳密な関数型言語で追加し、最初のリストを複数回トラバースしないようにします。

    （「ステージング」というタイトルのセクション）

  • foldrを使用してリストを別のリストと比較する（つまり、別のリストを最初のリストと比較する関数を生成する）

    listEq a b = foldr comb null a b
  where comb x frec [] = False
        comb x frec (e:es) = x == e && frec es
cmp1To10 = listEq [1..10]

これらすべての例で、著者は通常、元のリストを1回だけトラバースすることの利点を指摘しています。しかし、「確かに、N個の要素のリストをトラバースする代わりに、N個の評価のチェーンをトラバースしているので、何をするのか」と考えずにはいられません。私はそれに何らかの利益があるに違いないことを知っています、誰かがそれを説明してもらえますか？

編集：答えてくれた両方に感謝します。残念ながら、それは私が知りたかったことではありません。私は自分の質問を明確にしようとしますので、中間リストの作成に関する（より一般的な）質問（私はすでにさまざまな場所で読んだもの）と混同しないでください。また、投稿のフォーマットを修正していただきありがとうございます。

リストに適用する関数を作成する場合に興味があります。この場合、結果を評価するために必要な値がまだありません（リストであるかどうかは関係ありません）。次に、各リスト要素への参照の生成を回避することはできません（リスト構造が参照されなくなった場合でも）。また、以前と同じメモリアクセスがありますが、リストを分解する必要はありません（パターンマッチング）。

たとえば、前述のMLブックの「ステージング」の章を参照してください。私はMLとRacketで試してみました。具体的には、最初のリストを何度もトラバースせずに、最初のリストをトラバースし、2番目のリストを末尾に挿入する関数を返す「append」のステージバージョンです。驚いたことに、最後のポインターがそれぞれの場合で異なっていたため、リスト構造をコピーする必要があることを考慮しても、はるかに高速でした。

以下はマップの変形であり、リストに適用した後、関数を変更するときに高速になるはずです。listMap [1..100000]Haskellは厳密ではないので、 inの評価を強制する必要がありますcachedList（または、最初のアプリケーションの後もまだメモリ内にあるはずなので、そうではないかもしれません）。

listMap = foldr comb (const [])
  where comb x rest = \f -> f x : rest f

cachedList = listMap [1..100000]
doubles = cachedList (2*)
squares = cachedList (\x -> x*x)

-- print doubles and squares
-- ...

comb x rest f = ...Haskellではvsを使用しても違いがないことは知っていますが（間違っている場合は訂正してください）comb x rest = \f -> ...、このバージョンを選択してアイデアを強調しました。

更新：いくつかの簡単なテストの後、Haskellでの実行時間に違いは見つかりませんでした。問題は、Scheme（少なくとも私がテストしたRacket実装）やMLなどの厳密な言語についてのみです。

4

4 に答える 4

27

基本的に、ループ本体でいくつかの追加の算術命令を実行する方が、いくつかの追加のメモリフェッチを実行するよりも安価です。

トラバーサルとは、大量のメモリアクセスを行うことを意味するため、実行する回数が少ないほど良いです。トラバーサルを融合すると、メモリトラフィックが減少し、直線的な計算負荷が増加するため、パフォーマンスが向上します。

具体的には、このプログラムを検討して、リストの数学を計算します。

go :: [Int] -> [Int]
go = map (+2) . map (^3)

明らかに、リストの2つのトラバーサルを使用して設計します。最初のトラバーサルと2番目のトラバーサルの間で、結果は中間データ構造に格納されます。ただし、これは怠惰な構造であるため、O(1)メモリのコストのみがかかります。

これで、Haskellコンパイラはすぐに2つのループを次のように融合します。

go = map ((+2) . (^3))

何故ですか？結局のところ、どちらもO(n)複雑ですよね？違いは一定の要因にあります。

この抽象化を考慮して：最初のパイプラインの各ステップに対して、次のことを行います。

  i <- read memory          -- cost M
  j = i ^ 3                 -- cost A
  write memory j            -- cost M
  k <- read memory          -- cost M
  l = k + 2                 -- cost A
  write memory l            -- cost M

したがって、4つのメモリアクセスと2つの算術演算を支払います。

融合した結果については、次のようになります。

  i <- read memory          -- cost M
  j = (i ^ 3) + 2           -- cost 2A
  write memory j            -- cost M

ここでA、およびMは、ALUおよびメモリアクセスで計算を行うための定数係数です。

1つではなく他の一定の要因（2つのループ分岐）もあります。

したがって、メモリアクセスが無料でない限り（長い目で見ればそうではありません）、2番目のバージョンの方が常に高速です。

不変シーケンスを操作するコンパイラーは、配列融合を実装できることに注意してください。これは、これを行う変換です。GHCはそのようなコンパイラです。

于 2012-12-03T17:28:59.067 に答える
16

もう1つの非常に重要な理由があります。リストを1回だけトラバースし、それに対する他の参照がない場合、GCは、リスト要素をトラバースするときに、リスト要素によって要求されたメモリを解放できます。さらに、リストが遅延生成される場合、常に一定のメモリ消費しかありません。例えば 

import Data.List

main = do
    let xs = [1..10000000]
        sum = foldl' (+) 0 xs
        len = foldl' (\_ -> (+ 1)) 0 xs
    print (sum / len)

を計算しますが、参照を保持する必要があり、後で計算する必要があるsumため、参照を保持してxsいるメモリを解放できません。len（またはその逆。）したがって、プログラムはかなりの量のメモリを消費し、xs必要なメモリが大きくなります。

ただし、リストを1回だけトラバースすると、リストは遅延して作成され、要素はすぐにGCになる可能性があるため、リストがいくら大きくても、プログラムはO(1)メモリのみを使用します。

{-# LANGUAGE BangPatterns #-}
import Data.List

main = do
    let xs = [1..10000000]
        (sum, len) = foldl' (\(!s,!l) x -> (s + x, l + 1)) (0, 0) xs
    print (sum / len)
于 2012-12-03T20:37:33.093 に答える
3

おしゃべりな答えを事前に申し訳ありません。

それはおそらく明らかですが、パフォーマンスについて話している場合は、常に測定によって仮説を検証する必要があります。

数年前、私はSTGマシンであるGHCの操作的意味論について考えていました。そして、私は自分自身に同じ質問をしました—確かに有名な「ワントラバーサル」アルゴリズムはそれほど素晴らしいものではありませんか？表面上は1回の走査のように見えますが、内部には、通常は元のリストと非常によく似たこのサンクチェーン構造もあります。

有名なRepMin問題のいくつかのバージョン（厳密さはさまざまです）を作成しました。数字で満たされたツリーを指定して、同じ形状のツリーを生成しますが、すべての数字をすべての数字の最小値に置き換えます。私の記憶が正しければ（覚えておいてください-常に自分で確認してください！）、素朴な2トラバーサルアルゴリズムは、さまざまな巧妙な1トラバーサルアルゴリズムよりもはるかに高速に実行されました。

私はまた、私の観察をサイモン・マーロウと共有しました（私たちはその間両方ともFPサマースクールにいました）、そして彼は彼らがGHCでこのアプローチを使用していると言いました。しかし、あなたが考えているように、パフォーマンスを改善するためではありません。代わりに、大きなAST（Haskellのものなど）の場合、すべてのコンストラクターを書き留めると（コード行に関して）多くのスペースが必要になるため、（構文上の）トラバーサルを1つだけ書き留めることで、コードの量を減らすことができます。 。

個人的には、このトリックを避けています。間違えると、デバッグが非常に不快なループが発生するからです。

于 2012-12-09T17:36:02.053 に答える
2

したがって、あなたの質問に対する答えは、部分的なコンパイルです。事前に行われるため、個々の要素に到達するためにリストをトラバースする必要はありません。すべての参照は事前に検出され、コンパイル済みの関数内に格納されます。

その関数をトラバースする必要性についてのあなたの懸念に関しては、それはインタプリタ言語でも当てはまります。しかし、コンパイルはこの問題を排除します。

怠惰が存在する場合、このコーディングトリックは逆の結果につながる可能性があります。完全な方程式があれば、たとえばHaskell GHCコンパイラはあらゆる種類の最適化を実行できます。これにより、リストが完全に削除され、コードがループに相当するものになります。-O2これは、たとえばswitchを使用してコードをコンパイルするときに発生します。

偏微分方程式を書き出すと、このコンパイラの最適化が妨げられ、関数の実際の作成が強制される可能性があります。結果として得られるコードは大幅に遅くなります。私はあなたのcachedListコードを試しましたが、0.01秒の実行時間が0.20秒に変わるのを見ました（私が行った正確なテストを今は覚えていません）。

于 2012-12-14T18:59:53.867 に答える