在MATLAB中实现Union-Find数据结构

Question

给我分配了连通部件标记( CCL )算法，为了实现CCL算法，我首先必须实现Union查找算法。

这是我的尝试，任何评论和建议都将不胜感激。

classdef UnionFind < handle
   properties 
       PARENT = containers.Map('KeyType', 'double', 'ValueType','any');
   end
   methods
       % Constructor Function
%        function obj = UnionFind(items)
%            for i = 1:5
%                obj.PARENT(items(i)) = items(i);
%            end
%        end
       % Add Item Function
       function addItem(obj, itemToAdd)
          obj.PARENT(itemToAdd) = itemToAdd; 
       end
       % Find Function
       function root = Find(obj, itemToFind)
          while (obj.PARENT(itemToFind) ~= itemToFind)
             obj.PARENT(itemToFind) = obj.PARENT(obj.PARENT(itemToFind));
             itemToFind = obj.PARENT(itemToFind);
          end
          root = itemToFind;
       end
       % Union Function
       function Union(obj, setOne, setTwo)
          obj.PARENT(setOne) = setTwo; 
       end
   end
end

Answer 1

我制作了一个纸条来执行您的数据结构来测试它。它并不能验证正确性，它只是为了计时。

tic
uf = UnionFind;
uf.addItem(1);
for ii = 2:10000
    uf.addItem(ii);
    n = randi(4);
    if n == 4 % happens in 25% of cases
        uf.Union(ii, uf.Find(randi(ii-1)));
    end
    if n ~= 1 % happens in 75% of cases
        uf.Union(uf.Find(ii), uf.Find(randi(ii-1))); % ii is no longer necessarily the root
    end
end
toc

基本上，它在数据结构中增加了10,000个元素，将新元素与随机选择的先验元素结合起来，在50%的情况下，在另外25%的案例中，使用两个先验元素。这与数据结构在连接组件标记算法中的使用方式不完全匹配(Find将被更频繁地调用)，但它越来越接近。

使用(R2019b)运行这个脚本大约需要1.7S。使用普通数字数组替换containers.Map的简单更改如下：

   properties
       %PARENT = containers.Map('KeyType', 'double', 'ValueType','any');
       PARENT = [];
   end

将执行时间改为0.097 s。containers.Map不是一个非常有效的数据结构(它是一个自定义类，很像任何用户都可以编写的类，显然访问成本要比本地类型高)。假设元素是连续整数(就像连接组件标记算法和使用Union-Find的任何其他图像处理算法中的情况一样)，使用地图没有任何好处，可以使用元素的值索引一个简单的数组。

代码的第二个改进是可用性: Union操作应该始终在两个根上进行。让Union函数查找其两个输入参数的根是很方便的，而且它可以防止错误使用(使用非根元素的合并在使用此数据结构的任何算法中都会产生错误的结果)：

       function Union(obj, setOne, setTwo)
          %obj.PARENT(setOne) = setTwo;
          obj.PARENT(obj.Find(setOne)) = obj.Find(setTwo);
       end

现在，我们可以简化测试代码，使其根本不调用Find。另一个改进是返回新的root。这也很常见，并且还将改进我们的测试代码：

       function root = Union(obj, setOne, setTwo)
          root = obj.Find(setTwo);
          obj.PARENT(obj.Find(setOne)) = root;
       end

通常，Union操作从两棵树中选择较小的树，使之成为另一棵树的子树。然而，目前还不清楚维护树大小所需的额外存储空间和逻辑是否值得，因此必须实现这一点并进行比较。一个简单的替代方法是始终将具有较小索引的根设置为另一棵树的父级。这确保了，更多的情况下，更大的树将是父树。看起来可能是这样的：

       function root = Union(obj, setOne, setTwo)
          roots = sort([obj.Find(setOne), obj.Find(setTwo)]);
          obj.PARENT(roots(1)) = roots(2);
          root = roots(1);

这使运行时增加了大约40%，所以这不是一个好的改变。

我们的测试代码现在简化为：

tic
uf = UnionFind;
uf.addItem(1);
for ii = 2:10000
    root = ii;
    uf.addItem(root);
    n = randi(4);
    if n == 4 % happens in 25% of cases
        root = uf.Union(root, randi(ii-1));
    end
    if n ~= 1 % happens in 75% of cases
        root = uf.Union(root, randi(ii-1));
    end
end
toc

关于使用handle作为基类:这将类转换为“句柄类”，不能复制此类型的对象，所有“副本”都引用相同的底层数据。这有时会导致MATLAB中意外的行为，通常b=a, b(1)=0不会改变a。但是，我认为在这种情况下，为这个数据结构使用句柄类是合理的，其原因与MATLAB的containers.Map是句柄类的原因相同。

路径压缩Union-查找数据结构在实现路径压缩之前不会变得真正有效。这意味着树木保持完全平坦，所有的叶子都直接指向根部。在这种情况下，Find通常是O(1)操作，而不是O(log n)，它将使用该数据结构的CLL算法从O(n log )转换为接近O(n)的数据结构。

路径压缩通常使用递归实现。在没有递归的情况下实现它是非常困难的。但是MATLAB的函数调用仍然相当昂贵，因此还不清楚这是否会是一个改进。再一次，我们需要实现它并进行比较以确定地知道。

OP中的代码使用树减半。这是一个合理的折衷方案，因为它可以在没有递归的情况下实现。

路径压缩如下所示：

       function root = Find(obj, item)
          root = obj.PARENT(item);
          if root ~= item
              root = obj.Find(root);
              obj.PARENT(item) = root;
          end
       end

这会使测试代码的运行时间增加大约15%，所以这不是一个好的改变。

最后：

• 所有大写中的变量名(PARENT)在我看来都很奇怪，使用所有小写字母将更符合MATLAB的习惯风格。
• 构造函数被注释掉。在大多数情况下，您不需要这个构造函数，您可以完全删除它，或者取消注释。一段注释掉的代码可能会让人感到困惑。
• 没有帮助短信。文件顶部的注释块应该解释类的用途以及如何使用它。在MATLAB中输入help UnionFind将显示这个注释块。同样，每个函数都应该有一些文档作为注释块，无论是在function行的上方还是下面。