代码之家 › 专栏 › 技术社区 › fuz

如何在haskell中高效地实现迭代深化搜索?

iterative-deepening lazy-evaluation memory-management tree haskell

fuz · 技术社区 · 14 年前

我有一个优化问题要解决。您有某种数据结构:

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

在我开始之前,我的问题是:

O(n) n仍然很小,但还不足以让整棵树随着时间的推移留在内存中)?

2 回复 | 直到 4 年前

Travis Brown 14 年前

我的建议是:

只需在最直接的方法。
轮廓。
必要时优化速度或内存使用。

这个 真实世界的Haskell profiling and optimization 一旦你进入第2步和第3步,它会非常有用。

例如,下面是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" 具有 children x = [x ++ "a", x ++ "bb", x ++ "ccc"] 作为 . 它看起来相当快,需要很少的内存(我认为与深度成线性关系)。如果数据结构不够好,为什么不先尝试这样的方法,然后转移到更复杂的数据结构呢?

sclv 14 年前

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

为你的树考虑一个类似拉链的结构。每个节点都有一个值和一个表示向下、向上等的thunk。当移动到下一个节点时,可以正常移动(将上一个节点的值放置在相应的槽中)或忽略(将计算结果为上一个节点的表达式放置在右槽中)。然后你就可以控制自己有多少“历史”。

推荐文章

root · 计数算法

1 年前

Ash · 递归列表拆分和索引

2 年前

Someone · 如何实际删除节点?

2 年前

bb ef · 如何使用递归从列表中删除某些内容?python

6 年前

Linkmaster · 在用于BST的类中是否可能有类成员变量BST?

6 年前

Adam Morad · 方案更改树值

6 年前

A Akshat · 如何为函数中的结构分配动态内存插槽,该结构可以从程序中的任何位置访问

6 年前

johnny 5 · 角度将ViewChild绑定到类中的属性

6 年前

user2467011 · 为什么给定的二叉树是用空节点构造的?

6 年前

Yuki.kuroshita · 从二叉树中删除节点及其所有子节点,而不使用树数据结构

6 年前