标签: memoization

互联网上有一些自动记忆库可用于各种不同的语言; 但不知道它们的用途,使用方法以及它们的工作原理,很难看出它们的价值.使用memoization有什么令人信服的论据,以及memoization特别闪耀的问题域是什么？这里特别感谢不知情的信息.

对于我正在研究的项目,有许多州可以依赖计算来返回相同的结果(并且没有副作用).显而易见的解决方案是对所有昂贵的功能使用memoization.

我需要有一个处理多个状态的memoization(这样我就可以使一个缓存集无效而不会使另一个缓存集无效).对于这种事情,有人知道一个好的C库吗？(注意它不能是C++,我们正在谈论C.)

我已经在Python中使用了一些很好的实现,它们使用装饰器来灵活地记忆一堆不同的函数.我有点想知道是否有一个通用库可以用C做类似的事情(尽管可能有明确的函数包装而不是方便的语法).我认为,当一个常见的问题必须有一些现成的解决方案时,必须单独为每个功能添加缓存是愚蠢的.

我要寻找的特征如下:

1. 可以使用各种类型的输入和输出缓存函数
2. 管理多个不同的缓存(这样您就可以进行短期和长期缓存)
3. 具有使缓存无效的良好功能
4. 旨在用于包装函数,而不是更改现有函数

有人知道可以处理所有或大部分这些必需品的C实现吗？

有没有办法将函数的输出记忆到磁盘？

我有一个功能

def getHtmlOfUrl(url):
    ... # expensive computation

并希望做类似的事情:

def getHtmlMemoized(url) = memoizeToFile(getHtmlOfUrl, "file.dat")

然后调用getHtmlMemoized(url),以便为每个url只执行一次昂贵的计算.

我一直在使用下面的memoizing装饰器(来自伟大的书籍Python算法:掌握Python语言中的基本算法......喜欢它,顺便说一句).

def memo(func):
    cache = {}
    @ wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

这个装饰器的问题是基于字典的缓存意味着我的所有参数都必须是可清除的.

有没有人有一个允许不可用的参数(例如字典)的实现(或对这一个的调整)？

我知道缺少哈希值意味着"这是否在缓存中？" 变得非常重要,但我只是想我会问.

===编辑给出上下文===

我正在开发一个函数,它返回一个Parnas风格的"使用层次结构"给定模块的字典:依赖项.这是设置:

def uses_hierarchy(requirements):
    """
    uses_hierarchy(requirements)

    Arguments:
    requirements - a dictionary of the form {mod: list of dependencies, }

    Return value:
    A dictionary of the form {level: list of mods, ...}

    Assumptions:
    - No cyclical requirements (e.g. if a requires b, b cannot require a).
    - Any dependency not listed as a mod assumed …

以下代码来自Pathikrit的动态编程存储库.我的美丽和独特使我感到困惑.

def subsetSum(s: List[Int], t: Int) = {
  type DP = Memo[(List[Int], Int), (Int, Int), Seq[Seq[Int]]]
  implicit def encode(key: (List[Int], Int)) = (key._1.length, key._2)

  lazy val f: DP = Memo {
    case (Nil, 0) => Seq(Nil)
    case (Nil, _) => Nil
    case (a :: as, x) => (f(as, x - a) map {_ :+ a}) ++ f(as, x)
  }

  f(s, t)
}

该类型Memo在另一个文件中实现:

case class Memo[I <% K, K, O](f: I => O) extends (I => …

2008年7月中旬,Memoization被添加到Rails核心.这里使用的演示.

我还没有找到任何关于何时应该记忆方法的好例子,以及每个方法的性能影响.例如,这篇博客文章表明,通常不应该使用备忘录.

对于可能具有巨大性能影响的东西,除了提供简单的教程外,似乎没有什么资源可供使用.

有没有人看到他们自己的项目中使用的memoization？哪些因素会让您考虑记忆方法？

在我自己做了一些研究之后,我发现在Rails核心中使用了很多次memoization.

这是一个例子:http://github.com/rails/rails/blob/1182658e767d2db4a46faed35f0b1075c5dd9a88/actionpack/lib/action_view/template.rb.

这种用法似乎违背了上述博客文章的发现,发现备忘可能会损害性能.

让我们以Wes Dyer的函数memoization方法为出发点:

public static Func<A, R> Memoize<A, R>(this Func<A, R> f)
{
  var map = new Dictionary<A, R>();
  return a =>
    {
      R value;
      if (map.TryGetValue(a, out value))
        return value;
      value = f(a);
      map.Add(a, value);
      return value;
    };
}

问题是,当从多个线程使用它时,我们可能会遇到麻烦:

Func<int, int> f = ...
var f1 = f.Memoize();
...
in thread 1:
var y1 = f1(1);
in thread 2:
var y2 = f1(1);
// We may be recalculating f(1) here!

我们试着避免这种情况.锁定map:

public static Func<A, R> …

我知道这个http://onjava.com/pub/a/onjava/2003/08/20/memoization.html但是还有什么吗？

我一直认为Haskell会做一些自动智能记忆.例如,天真的斐波那契实施

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

因此会很快.现在我读了这个,似乎我错了--Haskell似乎没有做自动记忆.或者我理解错了什么？

还有其他语言可以自动(即隐式,非显式)进行记忆吗？

实施备忘录的常用方法有哪些？在我看到的所有示例实现中,它们都使用了散列映射,但其大小没有任何限制.显然,这在实践中不起作用,因为你需要某种限制.鉴于此,它变得更加复杂,因为当你达到极限时,你必须扔掉一些数据.并且它变得复杂:如果限制可能是动态的并且经常使用的功能应该比不常使用的功能具有更高的限制吗？当你达到极限时,你扔掉了什么条目？只是最新使用的一个？在这种情况下,您还需要对数据进行排序.您可以使用链接列表和哈希映射的某种组合来实现这一点.这是常见的方式吗？

你可以链接(或参考)一些常见的实际实现吗？

谢谢,艾伯特

编辑:我最感兴趣的是我描述的问题,即如何实现这样的限制.对任何解决这个问题的论文的任何引用都会非常好.

编辑:可以在此处找到一些示例实现(具有限制)的想法.

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

为了尝试这样的解决方案,我考虑将其添加到Haskell作为优化.我真的很想知道这会有多好.

我想知道是否有人已经这样做了.

const f = (arg1) => (arg2) => { /* returns something */ }

关于2个参数是否可以记忆f,即:

f(1)(2);
f(1)(3); // Cache not hit
f(4)(2); // Cache not hit
f(1)(2); // Cache hit