标签: memoization

当前任何一种流行的函数式语言都能很好地支持memoization,如果我要根据它的memoisation选择一个,你会推荐和为什么？

更新:我正在寻找优化有向图(节点可以是函数或数据).当图中的节点被更新时,我希望仅当它们依赖于已更改的节点时才重新计算其他节点的值.

Update2:需要免费或开源语言/运行时.

以下几种变量初始化方法之间是否存在差异？

@var ||= []
@var = [] if @var.nil?
@var = @var || []

请分享初始化变量的方式,并说明利弊.

我知道memoization似乎是关于堆栈溢出的haskell标记的一个常年话题,但我认为这个问题以前没有被问过.

我知道几个不同的'现成'Haskell的memoization库:

• memo-combinators和memotrie包,它们利用一个涉及懒惰无限数据结构的漂亮技巧,以纯粹的功能方式实现memoization.(据我所知,前者稍微灵活一些,而后者在简单的情况下更容易使用:请参阅此SO答案进行讨论.)
• uglymemo包,它在内部使用unsafePerformIO,但仍然提供了一个引用透明的接口.在内部使用unsafePerformIO 可以获得比前两个包更好的性能.(现成的,它的实现使用基于比较的搜索数据结构,而不是可能稍微更有效的散列函数;但我认为如果你找到并替换Cmpfor Hashable和Data.Mapfor Data.HashMap和添加appropraite imports,你得到一个基于哈希的版.)

但是,我不知道任何基于对象标识而不是对象值查找答案的库.这可能很重要,因为有时用作备忘录表的键的对象类型(即,作为被记忆的函数的输入)可能很大---如此之大以至于完全检查对象以确定是否之前看到它本身就是一个缓慢的操作.慢,而且也没有必要的,如果你将一次又一次地施加memoized函数被存储在给定的"位置在存储器"的对象1.(例如,如果我们正在记忆一个函数,这个函数是在一些具有大量结构共享的大型数据结构上递归调用的.)如果我们之前已经在那个确切的对象上计算了memoized函数,我们可以已经知道了答案,即使没有看对象本身!

实现这样的memoization库涉及一些微妙的问题,并且正确地执行它需要语言的几个特殊支持.幸运的是,GHC提供的特殊功能,我们需要的,是有纸的佩顿-琼斯,马洛和Elliott基本上担心这些问题多数为你解释如何建立一个坚实的实现.他们没有提供所有细节,但他们接近了.

我可以看到哪一个可能应该担心的细节,但是他们不担心的是线程安全---他们的代码显然根本不是线程安全的.

我的问题是:有没有人知道一个打包的库,它在Peyton-Jones,Marlow和Elliott论文中讨论了那种记忆,填写了所有的细节(最好还填写了适当的线程安全性)？

如果做不到这一点,我想我将不得不自己编写代码:是否有人对其他细微之处(除了线程安全和论文中讨论的内容)有任何想法,这样的库的实现者会记住哪些？

UPDATE

按照@ luqui的建议,下面是关于我面临的确切问题的更多数据.我们假设有一种类型:

data Node = Node [Node] [Annotation]

这种类型可以用来表示内存中一种简单的有根DAG,其中Nodes是DAG节点,root只是一个区分Node,每个节点都注明了一些Annotations,我认为其内部结构不需要关注我们(但是如果它很重要,那就问一下,我会更具体.)如果以这种方式使用,请注意Node内存中的s 之间可能存在显着的结构共享- 可能会有指数级的路径从根到a节点比节点本身.我从一个外部库中获得了这种形式的数据结构,我必须与它接口; 我无法更改数据类型.

我有一个功能

myTransform : Node -> Node

细节不需要我们关注(或者至少我是这么认为的;但如果需要的话,我可以更具体).它将节点映射到节点,检查它给出的节点的注释,以及它的直接子节点的注释,以提出Node具有相同子节点但可能具有不同注释的新节点.我想写一个函数

recursiveTransform : Node -> Node

其输出与数据结构"看起来一样",就像你做的那样:

recursiveTransform Node originalChildren annotations = …

我读了这篇文章,退出了一个很好的面试问题,作者想出了一个work break问题并提出了三个解决方案.高效使用一个memoization算法和笔者表示,其最坏情况下的时间复杂度是O(n^2)因为the key insight is that SegmentString is only called on suffixes of the original input string, and that there are only O(n) suffixes.

但是,我发现很难理解它为什么O(n^2).有人可以给我一个提示或证据吗？

Work Break Problem: 
    Given an input string and a dictionary of words,
    segment the input string into a space-separated
    sequence of dictionary words if possible. For
    example, if the input string is "applepie" and
    dictionary contains a standard set of English words,
    then …

如果我可以选择使用递归或memoization来解决我应该使用的问题？换句话说,如果它们都是可行的解决方案,因为它们提供了正确的输出,并且可以在我正在使用的代码中合理地表达,何时我会使用另一个？

我有一个计算映射(带有软值),我用它来缓存昂贵的计算结果.

现在我有一种情况,我知道在接下来的几秒钟内可能会查找一个特定的密钥.该密钥的计算成本也比大多数都要高.

我想在最小优先级线程中提前计算该值,以便在最终请求该值时,它已经被缓存,从而缩短了响应时间.

这样做的好方法是:

1. 我可以控制执行计算的线程(特别是它的优先级).
2. 避免重复工作,即仅进行一次计算.如果计算任务已经在运行,那么调用线程会等待该任务而不是再次计算该值(FutureTask实现这一点.使用Guava的计算映射,如果你只调用get它,那么这是真的,但如果你将它与调用混合,则不是put.)
3. "预先计算值"方法是异步的和幂等的.如果计算已在进行中,则应立即返回,而不等待该计算完成.
4. 避免优先级倒置,例如,如果高优先级线程在中等优先级线程执行不相关的操作时请求该值,但计算任务在低优先级线程上排队,则高优先级线程不能被饿死.也许这可以通过临时提升计算线程的优先级和/或在调用线程上运行计算来实现.

如何在所涉及的所有线程之间进行协调？

附加信息
我的应用程序中的计算是图像过滤操作,这意味着它们都是CPU绑定的.这些操作包括仿射变换(范围从50μs到1ms)和卷积(最多10ms).当然,不同线程优先级的有效性取决于操作系统抢占较大任务的能力.

考虑这个功能:

f as = if length as > 100 then length as else 100

由于函数是纯粹的,因此很明显两个调用的长度都是相同的.我的问题是Haskell优化器将上面的代码转换成以下代码吗？

f as = 
  let l = length as
  in if l > 100 then l else 100

如果是,那么哪个级别设置启用它？如果没有,那么为什么呢？在这种情况下,内存浪费不能成为本答案中解释的原因,因为一旦函数执行完成,引入的变量就会被释放.

请注意,由于本地范围,这不是此问题的重复,因此可能会得到完全不同的答案.

在Java中,显式声明的字符串由JVM实现,因此相同String的后续声明会产生两个指向同一String实例的指针,而不是两个单独的(但相同的)字符串.

例如:

public String baz() {
    String a = "astring";
    return a;
}

public String bar() {
    String b = "astring"
    return b;
}

public void main() {
    String a = baz()
    String b = bar()
    assert(a == b) // passes
}

我的问题是,CPython(或任何其他Python运行时)对字符串做同样的事情吗？例如,如果我有一些课程:

class example():
    def __init__():
        self._inst = 'instance' 

并创建此类的10个实例,它们中的每一个都有一个实例变量引用内存中的相同字符串,或者我最终会得到10个单独的字符串？

从下面的代码中可以看出,||=运营商正在从课外进行评估.

class Foo
  attr_reader :bar

  def baz
    self.bar ||= 'baz'
  end

  private

  attr_writer :bar
end

puts Foo.new.baz
# => in `baz': private method `bar=' called for #<Foo:0x007fd9720829a8> (NoMethodError)

引用关于官方扩展的接受答案|| =条件赋值运算符:

In other words, the expansion c = c || 3 is (excluding bugs like in pre-1.9) correct.

重写baz方法self.bar = self.bar || 'baz'不会引发错误.

我正在寻找关于Ruby 如何以及为什么以这种方式表现的明确答案,因为它似乎违反直觉.

这种行为出现在Ruby版本1.9.3,2.0.0和2.1.2上,这让我相信这不是一个错误.

我遇到了一个有趣的问题,并想知道是否以及如何在Java中完成:创建一个可以记住任何函数/方法的方法.该方法具有以下参数:方法/函数及其参数.

例如,假设我有这种方法:

int addOne(int a) { return a + 1;}

并且我使用相同的参数调用我的memoization方法两次:例如addOne和5,第一个调用应该实际调用addOne方法并返回结果并且还存储该给定参数的结果.第二次我打电话的时候应该知道之前已经打过电话,只是查看上一个答案.

我的想法是有一个类似于HashMap<Callable,HashMap<List<Objects>,Object>>你将存储以前的答案并在以后查找它们的地方.我认为这可以用lambda表达式以某种方式完成但我不熟悉它们.我不太确定写这个方法,并希望得到一些帮助.

这可以通过这种方法完成吗？