在函数式编程语言中自动记忆 [英] Automatic memoizing in functional programming languages

查看:182
本文介绍了在函数式编程语言中自动记忆的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我一直认为Haskell会做某种自动智能记忆。例如,天真的斐波那契实现

  fib 0 = 0 
fib 1 = 1
fib n = fib (n-2)+ fib(n-1)

会因此而变快。现在我读了这个,看起来我错了 - Haskell似乎没有做自动记忆。或者我理解错了什么?



是否有其他语言可以自动执行(即隐式,而不是显式)memoization?

执行记忆的常用方法是什么?在我看到的所有示例实现中,它们都使用hashmap,但其大小没有任何限制。显然,这在实践中不起作用,因为你需要某种限制。考虑到这一点,它变得更加复杂,因为当你达到极限时,你必须抛弃一些数据。在那里它变得复杂了:应该限制动态而且经常使用的函数应该比使用较少的函数具有更高的限制吗?当你达到极限时,你会扔掉什么?只是最新使用的一个?在这种情况下,您需要将您的数据另外排序。你可以使用链表和散列图的组合来实现这一点。这是常见的方式吗?



你可能会链接(或引用)一些常见的真实世界的实现吗?

感谢,
Albert




编辑:我最感兴趣的是我所描述的问题,实施这样的限制。任何对任何论文的引用都是非常好的。




编辑:一些自己的想法有限制)可以在此处找到。






编辑:我没有试图解决特定应用程序中的特定问题。我正在寻找通用的memoization解决方案,它可以全局应用于(纯函数)程序的 all 函数(因此没有实现内存限制的算法不是解决方案)。当然那里(可能)不是最佳/最好的解决方案。但是这使得我的问题没有那么有趣。



为了尝试这样的解决方案,我想把它作为一个优化添加到Haskell中。我真的不知道这样做会有多好。



我想知道是否有人已经做到了。

解决方案


Haskell似乎没有自动记忆。或者我理解错了什么?


不,Haskell不会。但是,共享表达式仅计算一次。在Paul Johnson给出的例子中, x 作为 thunk y z 都可以引用 x x 在范围内,并且它们指向相同的位置。一旦 x 必须被评估,它将被评估一次,只有评估结果将被保留。所以这不是真正的memoisation,但它是实现的结果。


是否有其他语言自动执行(即隐式,不明确)memoization?


我见过装饰器 @ memoized 出现在一些python源代码中。你当然可以完全为它创建自己的装饰器/实现。


$ b


实现记忆的常用方法是什么?


没有真正的常用方法来实现记忆。对于类似fib的模式(只有一个参数,这是一个数字),在fib-example中使用的memoisation可以设计出一个通用的解决方案(hashmaps),它可以工作,但它也可能对您的具体问题并不理想。

通过记忆功能可以产生副作用,因此您可能希望缓存生存在State monad中。但是,一般而言,您希望保持算法尽可能纯粹,所以如果它有递归,那么您已经陷入了一团糟。这是因为你会递归地调用函数的memoised版本,但是需要在State monad中运行,所以现在你的整个函数必须在State monad中运行。这也会影响懒惰,但您可以尝试 lazy state monad



牢记这一点:自动记忆是非常难以实现的。但你可以轻松地走过很长的路。自动记忆功能可能涉及程序转换,在定点写东西可能会有很长的路要走。


编辑:我最感兴趣的是我描述的问题,即如何实现这样的限制。一旦你有了记忆的基本机制,你可以调整查找和存储函数为你记忆表执行LRU或其他一些保持内存消耗小的机制。也许你可以从这个C ++示例得到LRU的想法。


I always thought that Haskell would do some sort of automatic intelligent memoizing. E.g., the naive Fibonacci implementation

fib 0 = 0
fib 1 = 1
fib n = fib (n-2) + fib (n-1)

would be fast because of that. Now I read this and it seems I was wrong -- Haskell doesn't seem to do automatic memoization. Or do I understand something wrong?

Are there other languages which do automatic (i.e. implicit, not explicit) memoization?

What are common ways to implement memoization? In all sample implementations I have seen, they use a hashmap but there isn't any limit in its size. Obviously, this wouldn't work in practice because you need some sort of limit. And given that, it becomes more complicated because when you hit the limit, you have to throw some data away. And there it becomes complicated: Should the limit maybe be dynamically and often used functions should have a higher limit than less often used functions? And what entry do you throw away when you hit the limit? Just the latest used one? In that case, you need to have your data also sorted in addition. You could use some combination of a linked list and a hash map to achieve that. Is that the common way?

Could you maybe link (or refer) to some common real-world implementations?

Thanks, Albert


Edit: I am mostly interested in that problem I described, i.e. how to implement such a limit. Any references to any papers which address this would be very nice.


Edit: Some own thoughts with a sample implementation (which has a limit) can be found here.


Edit: I am not trying to solve a specific problem in a specific application. I am searching for general solutions for memoization which could be applied globally to all functions of a (pure functional) program (thus algorithms which don't implement a memory limit are not a solution). Of course there (probably) is no optimal/best solution. But this makes my question not less interesting.

For trying out such solution, I thought about adding it to Haskell as an optimization. I really wonder how well that would perform.

And I wonder if someone has done that already.

解决方案

Haskell doesn't seem to do automatic memoization. Or do I understand something wrong?

No, Haskell doesn't. However, shared expressions are calculated only once. In the example given by Paul Johnson x is stored on the heap as a thunk. Both y and z can refer to x as x is in scope, and they refer to the same location. Once x has to be evaluated it will be evaluated only once and only the result of the evaluation will be kept. So this is not really memoisation but it is a result of the implementation.

Are there other languages which do automatic (i.e. implicit, not explicit) memoization?

I've seen the decorator @memoized come along in some python source code. You could of course completely create your own decorator / implementation for it. Complete with LRU and other policies you want to use.

What are common ways to implement memoization?

There is no real common way to implement memoisation. For fib-like patterns (only one argument, which is a number) the memoisation as used in the fib-example One could devise a general solution (the hashmaps one) and it will work, but it might also be suboptimal for your specific problem.

With memoisation you have side-effects, so you probably want the cache to live in the State monad. However, in general you want to keep your algorithms as pure as possible so if it has recursion, you are already getting in a bit of a mess. This is because you will call the memoised version of the function recursively, but that needs to run in the State monad, so now your whole function has to run in the State monad. This also effects laziness, but you could try the lazy state monad.

Keeping this in mind: good automatic memoisation is very difficult to achieve. But you can come a long way easily. Automatically memoising functions probably involves program transformation, where writing things in fix point could go a long way.

Edit: I am mostly interested in that problem I described, i.e. how to implement such a limit. Any references to any papers which address this would be very nice.

Once you have the basic mechanism of memoisation you could tweak the lookup and store functions for you memoising table to implement LRU or some other mechanism of keeping memory consumption small. Maybe you can get the idea for LRU from this C++ example.

这篇关于在函数式编程语言中自动记忆的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆