9

このコードのように:

import Data.Char
groupsOf _ [] = []
groupsOf n xs = 
    take n xs : groupsOf n ( tail xs )

problem_8 x = maximum . map product . groupsOf 5 $ x
main = do t <- readFile "p8.log" 
      let digits = map digitToInt $concat $ lines t
      print $ problem_8 digits

Haskell では、多くのプログラムgroupsOfが上記のコードのリストのような中間結果を構築し、保存しているように見えます。上記のコードは、Haskell の Web サイトから取得した Euler プロジェクトの問題 8 の参照回答です。元の質問では、 のような非常に長い数字の連鎖で連続する 5 桁の最大の積を求めます45343231635723421312443535767983456。したがって、コードはすべての製品を計算し、リストとして保存します。他の言語では、一時的な最大値のみを保持し、それより小さい値は破棄すると思います。

それでgroupsOf、本当にすべての中間結果を保存しますか? 問題が拡大した場合はどうなりますか？メモリを割り当てすぎますか?

4

3 に答える 3

12

いいえ、のせいではありませんgroupsOf。一度に 1 つのグループをメモリに保持するだけで済みます。ただし、怠惰すぎるため、大きなサンクmaximumが構築される可能性があるため、厳密性分析が実行されるようにまたはでコンパイルするか、代わりに1を使用してください。-O-O2foldl1' max

1 foldl1'が見つかりましたData.List

于 2011-11-26T00:07:18.043 に答える
8

Haskell では、多くのプログラムが、上記のコードの groupsOf リストなど、いくつかの中間結果を構築して保存しているように見えます。

正直なところ、これはHaskellが本当に輝くことができる場所だからです。実際、怠惰のおかげで、ユーザー側で複雑なマイクロ管理を行わなくても、使用するメモリははるかに少なくて済みます。

レイジー IO (例: readFile) の便利な点の 1 つは、必要なだけのファイルのみを読み取り、ファイルの内容を消費するときにファイルをガベージ コレクションできることです。(まぁ、大体そうです。バッファリングの設定次第です。)

プログラムがどのように実行されるかの大まかなスケッチを次に示します。

t <- readFile "p8.log"

のサンクを作成しますt :: String。ファイルが存在することを確認し、読み取りモードで開いてください。

 let digits = map digitToInt $concat $ lines t

サンクを作成するdigits :: [Int]

 print $ problem_8 digits

これを実行しようとすると、すべての作業が実際に完了します。problem_8 digits :: Int印刷するには、十分に評価する必要があります。そのため、サンクを作成してproblem_8 digits強制します。

maximum . map product . groupsOf 5 $ digits

この時点で、どちらが大きいかを確認するためにmaximum、 の最初の 2 つの要素が必要です。map product . groupsOf 5 $ digitsしたがって、渡すにmap productは の最初の 2 つの要素を確認する必要があります。groupsOf 5 digits

ここで、最初の要素を生成するためにgroupsOf 5、 の最初の 5 つの要素が必要になりdigitsます。この時点で、おそらくファイルの最初の行が読み取られ、定義された変換が実行されます。groupsOf最初の要素と、おそらく 2 番目の要素を構成できます (その行に 6 文字以上あると仮定します)。groupsOf 5 digits最初の 2 つの要素をチェーンに渡し、productそれらの 2つの要素にマッピングしmaximum、2 つのうちどちらが大きいかを確認します。2 つのうち大きい方の結果を保持します。

この時点 (実際には、この時点よりも少し前) で、中間結果を完全に破棄できます。の最初の 2 つの要素はgroupOf 5 digits完全に不要になりました。それらを再び検査する必要はなく、ガベージコレクターはいつでもそれらを収集できます。そのファイルの最初の 2 文字も使用されなくなり、破棄することができます。

さて、これは非常にハンドウェーブであり、おそらくわずかに不正確です. しかし、あなたはその考えを理解していますか？Haskell はレイジーです (よく言えば、Haskell は「非厳密」であり、通常は遅延によって実装されます)、その実行スタイルは厳密な言語とは大きく異なります。これにより、実際に大量のメモリを占有することなく、大量の中間表現とデータ構造のように見えるものを使用できます。GHC などの優れたコンパイラは、信じられないほどメモリ使用量を最適化できます。

于 2011-11-26T07:46:19.913 に答える
3

ここでの「中間結果」が何を意味するのか正確にはわかりません...しかし、あなたのコードは私にはうまく見えます。具体的には、あなたの実装groupsOfは末尾再帰モジュロ consであるため、スタック オーバーフローについて心配する必要はないと思います。

しかし、私はあなたの質問を誤解しているかもしれません。明確にしていただけますか？

于 2011-11-26T00:04:58.643 に答える