3

我有一个要解决的优化问题。你有某种数据结构：

data Foo =
  { fooA :: Int
  , fooB :: Int
  , fooC :: Int
  , fooD :: Int
  , fooE :: Int
}

和评级函数：

rateFoo :: myFoo -> Int

我必须rateFoo通过更改结构中的值来优化结果。在这种具体情况下，我决定使用迭代深化搜索来解决问题。用于最佳优化的（无限）搜索树由另一个函数创建，该函数简单地将所有可能的更改递归地应用于树：

fooTree :: Foo -> Tree

我的搜索功能如下所示：

optimize :: Int -> Foo -> Foo
optimize threshold foo = undefined

在我开始之前，我的问题是：

由于树可以由每个点的数据生成，是否可以只生成算法当前需要的树的部分？是否可以释放内存并在需要时重新生成树以节省内存（可以在 n 级生成一个叶，O(n)并且 n 仍然很小，但不足以随着时间的推移将整个树都放在内存中）？

这是我可以从运行时获得的东西吗？运行时可以取消计算表达式（将已计算的表达式转换为未计算的表达式）吗？或者我必须为此做些什么肮脏的黑客行为？

4

2 回答 2

4

运行时不会取消计算表达式。

然而，有一种简单的方法可以得到你想要的。

为你的树考虑一个类似拉链的结构。每个节点都有一个值和一个代表向下、向上等的 thunk。当您移动到下一个节点时，您可以正常移动（将前一个节点值放在相应的槽中）或忘记移动（放置一个计算结果为前一个的表达式右侧插槽中的节点）。然后你可以控制你坚持多少“历史”。

于 2010-09-21T14:56:24.210 回答
3

这是我的建议：

  1. 只需以最直接的方式实现您的算法。
  2. 轮廓。
  3. 如有必要，优化速度或内存使用。

我很快了解到我不够聪明和/或经验不足，无法推断 GHC 将做什么或垃圾收集将如何工作。有时，我确信在第一次时会出现灾难性的内存效率低下的事情，而且——不太常见——看起来简单的事情需要大量的严格注释等大惊小怪。

一旦您进入第 2 步和第 3 步，Real World Haskell 关于分析和优化的章节将非常有用。

例如，这是一个非常简单的 IDDFS 实现，其中f展开子项，p是搜索谓词，x是起点。

search :: (a -> [a]) -> (a -> Bool) -> a -> Bool
search f p x = any (\d -> searchTo f p d x) [1..]
  where
    searchTo f p d x
      | d == 0    = False
      | p x       = True
      | otherwise = any (searchTo f p $ d - 1) (f x)

我通过搜索"abbaaaaaacccaaaaabbaaccc"with children x = [x ++ "a", x ++ "bb", x ++ "ccc"]as进行了测试f。它看起来相当快并且需要很少的内存（我认为与深度成线性关系）。为什么不先尝试这样的事情，如果还不够好，然后再转向更复杂的数据结构呢？

于 2010-09-21T12:43:35.097 回答