首页 文章

数据值依赖性，更新和记忆

提问于
浏览 次
1

对不起，这个问题的描述是如此抽象：它对我的工作而言，出于商业机密的原因，我不能给出现实世界的问题，只是一个抽象 .

我有一个应用程序，它接收包含键值对的消息 . 密钥来自一组定义的关键字，每个关键字都有固定的数据类型 . 因此，如果“Foo”是一个整数而“Bar”是一个日期，您可能会收到如下消息：

Foo: 234
Bar: 24 September 2011

消息中可以包含任何密钥子集 . 键的数量相当大（几十个） . 但是现在让我们坚持使用Foo和Bar .

显然有一条这样的记录对应于这些消息：

data MyRecord {
   foo :: Maybe Integer
   bar :: Maybe UTCTime
   -- ... and so on for several dozen fields.
}

该记录使用“可能”类型，因为该字段可能尚未收到 .

我还需要从当前值（如果存在）计算出许多派生值 . 比如我想拥有

baz :: MyRecord -> Maybe String
baz r = do -- Maybe monad
   f <- foo r
   b <- bar r
   return $ show f ++ " " ++ show b

其中一些功能很慢，所以我不想不必要地重复它们 . 我可以为每个新消息重新计算baz，并在原始结构中备忘，但是如果一条消息使foo和bar字段保持不变，则会浪费CPU时间 . 相反，我可以在每次需要时重新计算baz，但如果基础参数自上次以来没有改变，那么这将浪费CPU时间 .

我想要的是某种智能记忆或基于推送的重新计算，只有在参数改变时才重新计算baz . 我可以通过注意baz仅依赖于foo和bar来手动检测到这一点，因此只能在更改这些值的消息上重新计算它，但是对于容易出错的复杂函数 .

另外一个问题是这些功能中的一些可能有多种策略 . 例如，您可能有一个可以使用'mplus'从Foo或Bar计算的值 .

有谁知道现有的解决方案？如果没有，我该怎么办呢？

haskell

3 回答

  • 2

    我假设你有一个"state"记录，这些消息都涉及更新它以及设置它 . 因此，如果 Foo 是 12 ，它可能稍后是 23 ，因此 baz 的输出会改变 . 如果不是这种情况，那么答案就变得微不足道了 .

    让我们从baz的“核心”开始 - 一个不在记录上的函数，而是你想要的值 .

    baz :: Int -> Int -> String

    现在让我们改变它：

    data Cached a b = Cached (Maybe (a,b)) (a -> b)
getCached :: Eq a => Cached a b -> a -> (b,Cached a b)
getCached c@(Cached (Just (arg,res)) f) x | x == arg = (res,c)
getCached (Cached _ f) x = let ans = f x in (ans,Cached (Just (x,ans) f)

bazC :: Cached (Int,Int) String
bazC = Cached Nothing (uncurry baz)

    现在，无论何时使用普通函数，都可以使用缓存转换函数，将生成的缓存转换函数替换回记录中 . 这本质上是一个尺寸为1的手册 .

    对于您描述的基本情况，这应该没问题 .

    一个包含动态依赖关系图的更加通用且更通用的解决方案名为“增量计算”，但我看到它的研究论文不仅仅是严肃的 生产环境 实现 . 你可以看看这些对于初学者，并遵循前面的参考线索：

    增量计算实际上也与函数式反应式编程非常相关，因此您可以查看一下conal 's papers on that, or play with Heinrich Apfelmus' reactive-banana库：http://www.haskell.org/haskellwiki/Reactive-banana

    在命令式语言中，看看python中的trellis：http://pypi.python.org/pypi/Trellis或lisp中的单元格：http://common-lisp.net/project/cells/

    回复于
  • 1

    您可以构建与您需要执行的计算相对应的有状态图 . 当出现新值时，将这些值推入图形并重新计算，更新图形直到达到输出 . （或者您可以将值存储在输入中并根据需要重新计算 . ）这是一个非常有状态的解决方案，但它可以工作 .

    您是否可以根据费率的实时输入等创建市场数据，如收益率曲线？

    回复于
  • 1

    我想要的是某种智能记忆或基于推送的重新计算，只有在参数改变时才重新计算baz .

    听起来像你想要一个不可变的变量，但允许从“尚未计算”到“计算”的一次性变异 . 嗯，你很幸运：这正是懒惰的评价给你的！因此，我提出的解决方案非常简单：只需为您要计算的每个项目的字段扩展记录 . 这是一个这样的例子，我们正在做的CPU密集型任务正在破坏一些加密方案：

    data Foo = Foo
    { ciphertext :: String
    , plaintext :: String
    }

-- a smart constructor for Foo's
foo c = Foo { ciphertext = c, plaintext = crack c }

    这里的要点是对 foo 的调用有这样的费用：

    • 如果你从不要求结果的 plaintext ，那就便宜了 .

    • 在第一次调用 plaintext 时，CPU会长时间搅拌 .

    • 在对 plaintext 的后续调用中，立即返回先前计算的答案 .

    回复于

相关问题