3

我有一个功能

slow :: Double -> Double

它经常被调用（数亿次），但只被调用大约一千个离散值。这似乎是一个很好的记忆候选者，但我不知道如何记忆一个 Double 的函数。

制作列表的标准技术不起作用，因为它不是整数类型。我查看了 Data.MemoCombinators，但它本身并不支持 Doubles。有一个bits用于处理更多数据类型的函数，但Double 不是Data.Bits.

有没有一种优雅的方式来记忆“慢”？

4

2 回答 2

6

你总是可以使用丑陋的备忘录。内部是不纯的，但它很快并且可以满足您的需求（除非参数是 NaN）。

于 2013-07-16T21:14:20.200 回答
3

我认为StableMemo应该完全按照您的意愿行事，但我对此没有任何经验。

有两种主要方法：使用Ord属性将键存储在树结构中，例如Map. 这不需要您需要的整体属性，例如MemoTrie方法；因此速度较慢但非常简单。

另一种适用于更通用类型的替代方法是使用Hash 函数无序映射到一个大的整数域，以便将键存储在哈希映射中。这将大大加快速度，但几乎一样简单，因为 的界面HashMap很大程度上与 的界面相匹配Map，因此您可能希望采用这种方式。

现在，可悲的是，两者都不像MemoCombinators. 它直接建立在IntTrie，专门用于提供惰性/无限/纯接口。相比之下，两者Map，特别是HashMap，都可以很好地用于不纯的记忆，但天生就不能纯粹地做到这一点。你可能会扔一些UnsafePerformIO（呃哦），或者只是在IOmonad 中公开地做（yuk！）。或使用StableMemo.

但是，如果您已经知道它将是哪些值，至少在大多数调用中，在 compile-time ，它实际上是简单和安全的。然后，您可以在开始时用这些值填充本地哈希映射，并在每次调用时查找它是否存在，否则只需直接调用昂贵的函数：

import qualified Data.HashMap.Lazy as HM

type X = Double  -- could really be anything else

notThatSlow :: Double -> X
notThatSlow = \v -> case HM.lookup v memo of
                 Just x  -> x
                 Nothing -> slow v
 where memo = HM.fromList [ (v, x) | v<-expectedValues, let x = slow v ]
于 2013-07-16T19:25:26.720 回答