1

いくつかの問題を解決するには、次のように定義されたパスカルの三角形の変形を計算する必要があります。

f(1,1) = 1, 
f(n,k) = f(n-1,k-1) + f(n-1,k) + 1 for 1 <= k < n, 
f(n,0) = 0,
f(n,n) = 2*f(n-1,n-1) + 1.

与えられたnに対して、n番目の行（f（n、1）.. f（n、n））を効率的に取得したいと思います。もう1つの制限：f（n、k）は、> = 2 ^ 32の場合、-1である必要があります。

私の実装：

next :: [Int64] -> [Int64]
next list@(x:_) = x+1 : takeWhile (/= -1) (nextRec list)

nextRec (a:rest@(b:_)) = boundAdd a b : nextRec rest
nextRec [a] = [boundAdd a a]

boundAdd x y
    | x < 0 || y < 0 = -1
    | x + y + 1 >= limit = -1
    | otherwise = (x+y+1)

-- start shoud be [1]
fLine d start = until ((== d) . head) next start

問題：非常に大きな数の場合、スタックオーバーフローが発生します。haskellにリスト全体を評価させる方法はありますか？各行に上限を超える要素を含めることはできないことは明らかです。これらの要素は最終的に-1になり、格納されず、各行は前の行にのみ依存するためです。遅延評価のため、最後の行が2番目の要素を必要とし、途中のすべてのトランクが格納されるまで、各行の先頭のみが計算されます... c ++で非常に効率的な実装がありますが、 haskellでそれを成し遂げる方法も。

4

1 に答える 1

5

私のために働く：どのHaskell実装を使用していますか？この三角形を計算する単純なプログラムは、GHC 6.10.4 で問題なく動作します。1000行目をうまく印刷できます：

nextRow :: [Integer] -> [Integer]
nextRow row = 0 : [a + b + 1 | (a, b) <- zip row (tail row ++ [last row])]

tri = iterate nextRow [0]

main = putStrLn $ show $ tri !! 1000               -- print 1000th row

スタックをオーバーフローさせることなく、行 100000 の最初の 10 個の数字を出力することさえできます。何が問題なのかわかりません。グローバル名triは、結果のトライアングル全体を維持している可能性がありますが、たとえそうであったとしても、それは比較的無害に思えます。

評価の順序を強制する方法: Prelude 関数seq(Haskell の他の基本機能では実装できない魔法の関数) を使用して、サンクを特定の順序で評価するように強制できます。Haskell に print を指示するとa `seq` b、最初に のサンクを評価しa、次に を評価して出力しbます。

seqは浅いことに注意してください:サンクではなくなるように強制するのに十分な評価のみを行います。aがタプル型の場合a、結果は依然としてサンクのタプルである可能性があります。リストの場合、結果は、先頭と末尾の両方にサンクを持つコンス セルになる可能性があります。

このような単純な問題に対してこれを行う必要はないようです。合理的な実装には、数千のサンクが多すぎるべきではありません。しかし、それは次のようになります。

-- Evaluate a whole list of thunks before calculating `result`.
-- This returns `result`.
seqList :: [b] -> a -> a
seqList lst result = foldr seq result lst

-- Exactly the same as `nextRow`, but compute every element of `row`
-- before calculating any element of the next row.
nextRow' :: [Integer] -> [Integer]
nextRow' row = row `seqList` nextRow row

tri = iterate nextRow' [0]

折りたたみはseqList基本的に に展開されlst!!0 `seq` lst!!1 `seq` lst!!2 `seq` ... `seq` resultます。

行 100,000 の最初の 10 要素だけを印刷する場合、これは私にとってはるかに遅くなります。これは、三角形の 99,999 行の完全な行を計算する必要があるためだと思います。

于 2010-03-08T17:26:14.823 に答える