21

我有一个接受参数并产生结果的函数。不幸的是，该函数需要很长时间才能产生结果。该函数经常使用相同的输入调用，这就是为什么如果我可以缓存结果会很方便。就像是

let cachedFunction = createCache slowFunction
in (cachedFunction 3.1) + (cachedFunction 4.2) + (cachedFunction 3.1)

我正在研究 Data.Array，虽然该数组是惰性的，但我需要使用对列表（使用 listArray）对其进行初始化 - 这是不切实际的。如果'key'是'Double'类型，我根本无法初始化它，即使理论上我可以为每个可能的输入分配一个整数，我有数万个可能的输入，我实际上只使用了少数。我需要使用函数而不是列表来初始化数组（或者，最好是哈希表，因为只会使用少数结果）。

更新：我正在阅读 memoization 文章，据我了解，MemoTrie 可以按照我想要的方式工作。也许。有人可以尝试生成“cachedFunction”吗？最好是一个需要 2 个 Double 参数的慢速函数？或者，或者，这需要一个 Int 参数在一个 ~ [0..1 亿] 的域中不会吃掉所有的内存？

4

7 回答 7

20

嗯，有Data.HashTable。不过，哈希表往往不能很好地处理不可变数据和引用透明性，所以我认为它没有多大用处。

对于少量值，将它们存储在搜索树中（例如Data.Map）可能就足够快了。如果您可以忍受对您Double的 s 进行一些修改，那么更强大的解决方案是使用类似 trie 的结构，例如Data.IntMap; 它们的查找时间主要与密钥长度成正比，并且在集合大小上大致恒定。如果Int限制太多，您可以在 Hackage 上四处挖掘以找到在使用的密钥类型方面更灵活的 trie 库。

至于如何缓存结果，我认为您想要的通常称为“memoization”。如果您想按需计算和记忆结果，该技术的要点是定义一个包含所有可能结果的索引数据结构，这样当您要求特定结果时，它只强制执行获得答案所需的计算你要。常见的例子通常涉及到列表的索引，但同样的原则应该适用于任何非严格的数据结构。根据经验，非函数值（包括无限递归数据结构）通常会被运行时缓存，而不是函数结果，因此诀窍是将所有计算包装在一个顶层定义中取决于任何论点。

编辑： MemoTrie 示例啊喂！

这是一个快速而肮脏的概念证明；可能存在更好的方法。

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
import Data.MemoTrie
import Data.Binary
import Data.ByteString.Lazy hiding (map)

mangle :: Double -> [Int]
mangle = map fromIntegral . unpack . encode

unmangle :: [Int] -> Double
unmangle = decode . pack . map fromIntegral

instance HasTrie Double where
    data Double :->: a = DoubleTrie ([Int] :->: a)
    trie f = DoubleTrie $ trie $ f . unmangle
    untrie (DoubleTrie t) = untrie t . mangle

slow x 
    | x < 1 = 1
    | otherwise = slow (x / 2) + slow (x / 3)

memoSlow :: Double -> Integer
memoSlow = memo slow

请注意 MemoTrie 包使用的 GHC 扩展；希望这不是问题。将其加载到 GHCi 中并尝试使用 (10^6) 或 (10^7) 之类的调用slowvs.memoSlow以查看它的实际效果。

将其推广到接受多个参数或诸如此类的函数应该相当简单。有关使用 MemoTrie 的更多详细信息，您可能会发现其作者的这篇博文很有帮助。

于 2010-02-07T16:32:43.613 回答
5

See memoization

于 2010-02-07T16:20:45.003 回答
4

There are a number of tools in GHC's runtime system explicitly to support memoization.

Unfortunately, memoization isn't really a one-size fits all affair, so there are several different approaches that we need to support in order to cope with different user needs.

You may find the original 1999 writeup useful as it includes several implementations as examples:

Stretching the Storage Manager: Weak Pointers and Stable Names in Haskell by Simon Peyton Jones, Simon Marlow, and Conal Elliott

于 2010-02-12T20:44:41.797 回答
3

我将添加我自己的解决方案，这似乎也很慢。第一个参数是一个返回 Int32 的函数 - 这是参数的唯一标识符。如果您想通过不同的方式（例如通过'id'）唯一标识它，则必须将H.new 中的第二个参数更改为不同的散列函数。我将尝试找出如何使用 Data.Map 并测试我是否获得更快的结果。

import qualified Data.HashTable as H
import Data.Int
import System.IO.Unsafe

cache :: (a -> Int32) -> (a -> b) -> (a -> b)
cache ident f = unsafePerformIO $ createfunc
    where 
        createfunc = do
            storage <- H.new (==) id
            return (doit storage)

        doit storage = unsafePerformIO . comp
            where 
                comp x = do
                    look <- H.lookup storage (ident x)

                    case look of
                        Just res -> return res
                        Nothing -> do
                            result <- return (f x)
                            H.insert storage (ident x) result
                            return result
于 2010-02-09T21:09:11.340 回答
2

您可以将慢速函数编写为高阶函数，返回函数本身。因此，您可以在慢速函数内进行所有预处理，并在返回的（希望是快速的）函数中进行每次计算中不同的部分。一个示例可能如下所示：（SML 代码，但思路应该很清楚）

fun computeComplicatedThing (x:float) (y:float) = (* ... some very complicated computation *)
fun computeComplicatedThingFast = computeComplicatedThing 3.14 (* provide x, do computation that needs only x *)
val result1 = computeComplicatedThingFast 2.71 (* provide y, do computation that needs x and y *)
val result2 = computeComplicatedThingFast 2.81
val result3 = computeComplicatedThingFast 2.91
于 2010-02-07T17:04:36.880 回答
1

我有数万个可能的输入，而我实际上只使用了少数几个。我需要初始化数组......使用函数而不是列表。

我会去listArray (start, end) (map func [start..end])

  • func上面并没有真正被调用。Haskell 是惰性的，它会创建 thunk，当实际需要该值时会对其进行评估。
  • 使用普通数组时，您始终需要初始化其值。因此，无论如何创建这些 thunk 所需的工作都是必要的。
  • 几万远不是很多。如果你有数万亿，那么我建议使用哈希表 yada yada
于 2010-02-07T19:48:37.357 回答
0

我不具体了解haskell，但是如何将现有答案保存在一些散列数据结构（可能称为字典或散列图）中？您可以将慢速函数包装在另一个函数中，该函数首先检查地图，只有在没有找到答案时才调用慢速函数。

您可以通过将地图的大小限制为特定大小并在达到该大小时丢弃最近最少使用的条目来使其变得花哨。为此，您还需要保留 key-to-timestamp 映射的映射。

于 2010-02-07T16:36:20.830 回答