1

私は実際の解決策や問題を解決する他の方法には興味がありません。それは私が助けを必要としているメモ化です:)

メモ化でパスカルの三角形の問題を解決するのに助けが必要です。三角形の底辺の真ん中の数字を取得したいです。(Project Euler 15)

最初の例はメモ化されていません (名前はそう示唆していますが) "20 20" は解決できません

2 番目の試みは、次のような試みです: http://www.haskell.org/haskellwiki/Memoization

3 番目は、no2 に関する hlints の提案です。

私はこのエラーを受け取りますが、それがコンパイルされても正しいかどうかはわかりません... (2 2 をパラメーターとして ghci から実行します)

no instance for (Num [a0])
arising from a use of `zmemopascals'
Possible fix: add an instance declaration for (Num [a0])
In the expression: zmemopascals 2 2
In an equation for `it': it = zmemopascals 2 2

.

Code:
--1 
memopascals r c =  [[pascals a b | b<-[1..c]] | a<-[1..r]] !! (r-1) !! (c-1) 
 where pascals 1 _ = 1 
       pascals _ 1 = 1 
       pascals x y = memopascals (x-1) y + memopascals x (y-1) 

--2 
--xmemopascals :: Int -> Int -> Int 
xmemopascals r c =  map (uncurry pascals) (zip [1..] [1..]) !! (r-1) !! (c-1) 
 where pascals 1 _ = 1 
       pascals _ 1 = 1 
       pascals x y = memopascals (x-1) y + memopascals x (y-1) 


--3 
zmemopascals r c =  zipWith pascals [1 ..] [1 ..] !! (r-1) !! (c-1) 
 where pascals 1 _ = 1 
       pascals _ 1 = 1 
       pascals x y = memopascals (x-1) y + memopascals x (y-1)
4

3 に答える 3

2

memopascals 5 5のような呼び出しは内部的に三角形の一部を構築し、そこから単一の値を返すため、メモ化は関数では機能しません。別の呼び出しmempascals 6 6は、の内部にあるその部分的な三角形とは関係がありませんmemopascals 5 5。

効率的なメモ化のために、共通の部分（三角形で計算された数値を表すリストのリストなど）を別の関数に入れて、特定のインデックスにアクセスする関数で使用する必要があります。このようにして、同じリストのリストを使用して、異なるインデックスを検索します。

通常、これを行う最も簡単な方法fullpascals :: [[Int]]は、完全な（無限の）データ構造を生成するような1つの関数を記述し、そのデータ構造にアクセスする別の関数よりも次のように記述することです。

memopascals x y = fullpascals !! (x-1) !! (y-1)

あなたの場合fullpascalsは、現在の関数の1つと同じですが、特定のインデックスのパラメーターがありません。memopascals再帰のために内部的に使用することもできます。

補足： wikiのmemoized_fib例では、メモ化される「共通部分」は、すべてのfibのリストではなく、すべてのfibのリストにアクセスする関数です。コンパイラはこれを最適化するのに十分賢いので、効果は同じです。

于 2012-07-13T15:29:35.557 に答える
1

メモ化を実現するためのガイドラインがいくつかあります（最近の議論については、こちらをご覧ください）。

まず、GHCコンパイラで-O2最適化フラグを使用します。次に、単相型の署名を使用します。共有したい中間リストに名前を付けます。

次に、ネストされた定義に注意してください。ネストされた定義がそれを囲む（「外部」）スコープ内の引数の値に依存する場合、その外部関数を呼び出すたびに、ネストされたすべての定義を新たに作成する必要があるため、共有されるリストは1つもありません。、しかし多くの別々の独立したもの。

この関数では、共有するリスト式を分離して名前を付けると、次のようになります。

memopascals r c = xs !! (r-1) !! (c-1) 
 where
   xs = [[pascals a b | b<-[1..c]] | a<-[1..r]] 
   pascals 1 _ = 1 
   pascals _ 1 = 1 
   pascals x y = memopascals (x-1) y + memopascals x (y-1)

定義xsはとの値に依存しますが、ネストされた関数内から「外部」関数を呼び出します。の各呼び出しは、の引数に依存するため、の独自のコピーを作成する必要があります。共有できません。rcmemopascalspascalsmemopascals xsmemopascalsrc

その依存定義が必要な場合は、「スコープ外」を呼び出さずに、そのスコープ内にとどまるように調整して、すべての内部（「ネストされた」）定義を再利用できるようにする必要があります。

memopascals r c = f r c
 where
   f r c = xs !! (r-1) !! (c-1)
   xs = [[pascals a b | b<-[1..c]] | a<-[1..r]] 
   pascals 1 _ = 1 
   pascals _ 1 = 1 
   pascals x y = f (x-1) y + f x (y-1)

これで、の呼び出しごとmemopascalsに内部定義が（ネストされたスコープから）作成され、スコープ外で呼び出されることなく相互に呼び出されるため、リストxsが再利用され、共有が実現します。

しかし、への別の呼び出しmemopascalsは、リストの内部定義の独自の新しいコピーを作成しxs、それを使用します。これは、「グローバル」共有（つまりメモ化）ではなく、「ローカル」共有と呼ぶことができます。つまり、高速に実行されますが、同じパラメーターを使用した2番目の呼び出しには、最初の呼び出しと同じ時間がかかります。完全なメモ化の場合の0時間ではありません。

それを達成する唯一の方法があります、そしてそれはあなたのxs定義を独立させることです。次に、コンパイラはすべてのネストされたスコープフレームをまとめてスマッシュし、ラムダリフティングを実行して、ネストされたクロージャをプレーンなラムダに変換します。

memopascals :: Int -> Int -> Integer
memopascals r c = [[pascals a b | b<-[1..]] | a<-[1..]] !! (r-1) !! (c-1) 
 where 
   pascals 1 _ = 1 
   pascals _ 1 = 1 
   pascals x y = memopascals (x-1) y + memopascals x (y-1)

-O2スイッチを使用すると、GHCはこのバージョンでも完全なメモ化を実行します。単形型の署名（またはローカル共有）を忘れない限り。

于 2012-07-17T00:02:27.250 に答える
1 
zmemopascals r c =  zipWith pascals [1 ..] [1 ..] !! (r-1) !! (c-1) 
 where pascals 1 _ = 1 
       pascals _ 1 = 1 
       pascals x y = memopascals (x-1) y + memopascals x (y-1)

エラーにとって重要というわけではありませんが、最後の行では、zmemopascalsではなく呼び出したいと考えていますmemopascals。

最初の行には、2つのリストインデックス演算子があります。したがって、いくつかのzipWith pascals [1 .. ] [1 .. ]タイプが必要です。の定義は言う[[a]]apascals

pascals :: Num t => Int -> Int -> t

したがってzipWith pascals [1 .. ] [1 .. ] :: [t]。したがって、型推論はそれを検出しt = [a]ますが、コンパイラーはインスタンスを検出しませんNum [a]。

メモ化の場合、再計算を避けるために、@ sthが提案するように、完全な三角形に名前を付ける必要があります（Fibonacciのメモ化は、コンパイラーが十分に賢いためにのみ機能し、その形式によって保証されません）。

別のオプションは、を使用して三角形を作成することiterateです。

pascal :: Int -> Int -> Integer
pascal n k = iterate nextRow [1] !! n !! k
  where
    nextRow ks = zipWith (+) (0:ks) (ks ++ repeat 0)
于 2012-07-13T15:35:03.200 に答える