3

我来自命令式背景，正在尝试实现一个简单的不相交集（“union-find”）数据结构，以练习在 Haskell 中创建和修改（持久）数据结构。目标是有一个简单的实现，但我也关心效率，我的问题与此有关。

首先，我创建了一个不相交集的森林实现，并使用按等级联合，并从定义“点”的数据类型开始：

data Point = Point
  { _value  :: Int
  , _parent :: Maybe Point
  , _rank   :: Int
  } deriving Show

脱节集森林是一个IntMap带有Int → Point映射的：

type DSForest = IntMap Point

empty :: DSForest
empty = I.empty

单例集只是从其值x到值为x的 Point的映射，没有父级且等级为 1：

makeSet :: DSForest -> Int -> DSForest
makeSet dsf x = I.insert x (Point x Nothing 0) dsf

现在，有趣的部分—— union。此操作将通过将另一个点设置为其父点来修改一个点（并在某些情况下更改其等级）。在Points 等级不同的情况下，Point简单地“更新”（创建一个新点）以使其父点指向另一个。在它们相等的情况下，Point创建一个新的，其等级增加一：

union :: DSForest -> Int -> Int -> DSForest
union dsf x y | x == y = dsf 
union dsf x y = 
   if _value x' == _value y'
      then dsf 
      else case compare (_rank x') (_rank y') of
                  GT -> I.insert (_value y') y'{ _parent = Just x' } dsf 
                  LT -> I.insert (_value x') x'{ _parent = Just y' } dsf 
                            -- 1) increase x's rank by one:
                  EQ -> let x''  = x'{ _rank = _rank x' + 1 } 
                            -- 2) update the value for x's rank to point to the new x:
                            dsf' = I.insert (_value x'') x'' dsf 
                            -- 3) then update y to have the new x as its parent:
                         in I.insert (_value y') y'{ _parent = Just x'' } dsf'
  where x' = dsf ! findSet dsf x
        y' = dsf ! findSet dsf y

现在，对于我真正的问题，如果在这种EQ情况下我做了以下事情：

EQ -> let dsf' = I.insert (_value x') x'{ _rank = _rank x' + 1} dsf 
       in I.insert (_value y') y'{ _parent = Just x'{ _rank = _rank x' + 1 }} dsf'

即首先插入一个新的Point x并增加其等级，然后让y'' 的父级成为一个新的Point x并增加其等级，这是否意味着它们不再指向Point内存中的相同？（这有关系吗？在使用/创建持久数据结构时我应该担心这些事情吗？）

为了完整起见，这里是findSet：

findSet :: DSForest -> Int -> Int
findSet dsf' x' = case _parent (dsf' ! x') of
                     Just (Point v _ _)  -> findSet dsf' v
                     Nothing             -> x'

（也欢迎对这段代码的效率和设计发表一般评论。）

4

3 回答 3

3

这是否意味着它们不再指向内存中的同一点？

我认为您不应该担心这一点，因为这只是不可变值的运行时系统（又名 Haskell 的 RTS）的实现细节。

就其他建议而言，我会说让函数findSet返回Point自身而不是键，因为这将消除union.

findSet :: DSForest -> Int -> Point
findSet dsf' x' = case _parent pt of
                     Just (Point v _ _)  -> findSet dsf' v
                     Nothing             -> pt
                  where
                      pt = (dsf' ! x')

对函数进行适当的更改union。

于 2013-08-06T10:25:11.807 回答
3

第一条评论：不相交集并集查找数据结构非常非常难以以纯粹的功能方式做好。如果您只是想练习使用持久性数据结构，我强烈建议您从更简单的结构开始，例如二叉搜索树。

现在，要查看一个问题，请考虑您的 findSet 函数。它没有实现路径压缩！也就是说，它不会使通往根的路径上的所有节点都直接指向根。为此，您需要更新 DSForest 中的所有这些点，因此您的函数将返回 (Int, DSForest) 或者可能返回 (Point, DSForest)。在 monad 中执行此操作以处理通过 DSForest 的所有管道比手动通过该森林更容易。

但现在是第二个问题。假设您按照刚才的描述修改了 findSet。它仍然不能完全满足您的要求。特别是，假设您有一个链，其中 2 是 1 的子项，3 是 2 的子项，4 是 3 的子项。现在您在 3 上执行 findSet。这将更新 3 的点，使其父项是 1 而不是 2。但是 4 的父级仍然是旧的 3 点，其父级是 2。这可能无关紧要，因为看起来你从来没有真正对父点做任何事情，除了拉出它的值（在 findSet 中）。但是，除了提取它的值之外，您从不对父点做任何事情，这一事​​实告诉我，它应该是一个 Maybe Int 而不是一个 Maybe Point。

让我重复并扩展我在开始时所说的话。不相交集是一种特别难以以功能/持久方式处理的数据结构，因此我强烈建议从更简单的树结构开始，例如二叉搜索树或左派堆甚至抽象语法树。这些结构具有所有访问都通过根目录的属性——也就是说，您总是从根目录开始，然后沿着树向下工作以到达正确的位置。此属性使作为持久数据结构标志的共享类型变得更加容易。

不相交集数据结构不具有该属性。不是总是从根开始，一直到感兴趣的节点，而是从任意节点开始，然后一直回到根。当您有像这样不受限制的入口点时，通常最简单的处理方法是通过单独的地图（在您的情况下为 DSForest）调解所有共享，但这意味着在任何地方来回传递该地图。

于 2013-08-06T15:20:32.853 回答
2

共享是编译器的事情。当它识别公共子表达式时，编译器可能会选择用内存中的同一个对象来表示它们。但是，即使您使用这样的编译器开关（如-fno-cse），也没有义务这样做，并且两者可能（并且通常在没有开关的情况下）由两个不同但具有相同价值的对象表示在记忆中。回复：参考透明度。

OTOH，当我们命名某事物并使用该名称两次时，我们（合理地）期望它代表内存中的同一个对象。但是编译器可能会选择复制它并在两个不同的使用站点中使用两个单独的副本，尽管不知道这样做。但它可能。回复：参考透明度。

也可以看看：

这里有几个列表生成函数的例子，取自上面的最后一个链接。它们依赖于编译器不复制任何东西，即确实按照需要lambda 演算操作语义（如 nponeccop 在评论中解释的那样）的调用共享任何命名对象，并且不会自行引入任何额外的共享以消除公共子表达式：

  1. 共享定点组合器，创建循环：

    fix f = x where x = f x

  2. 非共享定点组合器，创建伸缩多级链（即常规递归链）

    _Y f = f (_Y f)

  3. 两阶段组合 - 循环和提要

    _2 f = f (fix f)

于 2013-08-06T13:42:24.940 回答