Memoization pascals三角形 [英] Memoization pascals triangle

问题描述

我对实际解决方案或解决问题的其他方法不感兴趣，这是我需要帮助的备忘录：）

我需要帮助做一个帕斯卡三角形记忆问题。我想在三角形的底部得到中间数字。 （Project Euler 15）

第一个例子没有被记忆（尽管名字的意思是这样）20 20不可解析

第二次尝试是尝试执行类似以下操作： http://www.haskell.org/ haskellwiki / Memoization

第三是hlints对no2的建议，如果这对于某人来说更具可读性。

我得到这个错误，但我不确定它的权利，即使它会编译...（从ghci以2 2作为参数运行）

 没有使用`zmemopascals'产生的$（num [a0]）
的实例
可能的修正：为（Num [a0]）添加一个实例声明
在表达式：zmemopascals 2 2 
在'it'的等式中：it = zmemopascals 2 2 
  

。

$ p $ 代码：
- 1
memopascals rc = [[pascals ab | b < - > [1..c]] | a < - [1..r]] !!（r-1）!!（c-1）
其中pascals 1 _ = 1
pascals _ 1 = 1
pascals xy = 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）
其中pascals 1 _ = 1
pascals _ 1 = 1
pascals xy = memopascals（x-1）y + memopascals x（y-1）


--3
zmemopascals rc = zip与pascals [1 ..] [1 ..] !! （r-1）!! （c-1）
其中pascals 1 _ = 1
pascals _ 1 = 1
pascals xy = memopascals（x-1）y + memopascals x（y-1）


解决方案

实现记忆有几个指导原则（看一看 这里有一些最近的讨论）。

首先，使用-O2优化标志GHC编译器。其次，使用单形式签名。命名你的中间列表，你想要实现共享。

然后，注意你的嵌套定义。如果嵌套定义依赖于其封闭（外部）范围中参数的值，那意味着对该外部函数的每次调用将不得不重新创建其所有嵌套定义，因此不会有任何一个列表共享，但许多单独的独立列表。

在您的函数中，分离出想要共享的列表表达式并命名， p>

  memopascals rc = xs !! （r-1）!! （c-1）
其中
 xs = [[pascals a b | b < -  [1..c]] | （x-1）y + memopascals x（y-1）a<  -  [1..r]] 
 pascals 1 _ = 1 
 pascals _ 1 = 1 
 pascals xy = 
  

您的 xs 定义依赖于 r 和 c 的值，但您可以调用外部函数 memopascals ，来自嵌套的 pascals 。每次调用 memopascals 都有来创建自己的 xs 副本，因为它依赖于 memopascals 的参数， r 和 c 。没有共享的可能。

如果您需要拥有该相关定义，则必须安排不要调用超出范围，而是停留在该范围内，以便所有内部（嵌套）定义可以重新使用。

  memopascals r c = f r c 
其中
 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 xy = f（x-1）y + fx（y-1）
  

现在，每次调用 memopascals 都会创建其内部定义（从它的嵌套范围），然后互相调用，从不调用范围 - 所以列表 xs 被重用，实现共享。

但是对 memopascals 的另一个调用将为列表的内部定义创建它自己的新副本 xs ，并将使用它。我们可以称之为本地共享，而不是全局共享（即memoization）。这意味着它运行速度很快，但第二次调用具有相同的参数与第一次调用时间相同 - 而不是完全备份时的0次。

只有一种方法可以实现 ，那就是让你的 xs 定义独立。然后编译器可以将所有嵌套的范围框架一起粉碎，执行 lambda解除转换嵌套关闭到 lambdas 等等：

  memopascals :: Int  - > Int  - >整数
 memopascals r c = [[pascals a b | b < -  [1 ..]] | a<  -  [1 ..]] !! （r-1）!! （c-1）
其中
 pascals 1 _ = 1 
 pascals _ 1 = 1 
 pascals xy = memopascals（x-1）y + memopascals x（y-1） 
  

使用-O2开关，GHC即使对于此版本也执行完整记忆。只要我们不忘记单形签名（或再次本地共享）。

I'm not interested in the actual solution or other methods solving the problem, it's the memoization i need help with :)

I need help doing a pascals triangle problem with memoization. I want to get the middle number in the base of the triangle. (Project Euler 15)

The first example is not memoized (although the name suggests so) "20 20" not solvable

Second attempt is an attempt on doing something similar to: http://www.haskell.org/haskellwiki/Memoization

Third is hlints suggestion on no2 if that is more readable for someone.

I get this error, but i'm not sure its right even if it would compile... (run from ghci with 2 2 as params

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)

解决方案

There are several guidelines to achieving memoization (take a look here for some recent discussion).

First, use -O2 optimization flag with GHC compiler. Second, use monomorphic type signature. Name your intermediate list(s), that you want to achieve sharing of.

Then, pay attention to your nested definitions. If a nested definition depends on value of an argument in its enclosing ("outer") scope, that means each call to that outer function will have to create all its nested definitions anew, so there won't be any one list to be shared, but many separate independent ones.

Here in your function, separating out and naming the list expression that you want shared, we get

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)

Your xs definition is dependent on values of r and c, but you call your "outer" function, memopascals, from within a nested one, pascals. Each invocation of memopascals has to create its own copy of xs because it depends on memopascals's arguments, r and c. No sharing possible.

If you need to have that dependent definition, you must arrange not to call "out of scope", but rather stay inside that scope, so that all the internal ("nested") definitions can be reused.

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)

Now each invocation of memopascals creates its internal definitions (from its nested scope) which then call each other, never calling out of scope - so the list xs gets reused, achieving sharing.

But another call to memopascals will create its own new copy of its internal definition of the list xs, and will use it. We can call this a "local" sharing, not a "global" sharing (i.e. memoization). That means it runs fast, but second call with same parameters takes the same time as the first - not the 0 time as with full memoization.

There's only one way to achieve that, and that is to make your xs definition independent. Then the compiler can smash all the nested scope frames together, perform lambda lifting turning nested closures into plain lambdas, etc. etc.:

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)

With -O2 switch, GHC performs full memoization even for this version. As long as we don't forget the monomorphic type signature (or it's local sharing again).

这篇关于Memoization pascals三角形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！