标签: union-find

我注意到Data.UnionFind使用IO monad通过IORefs提供指针.我想大家都很乐意unsafePerformIO在纯代码中本地使用它,因为数据结构很好理解,但是......

这种数据结构是否有规范的清洁方法？也许是IO的包装,unsafePerformIO通过禁止大多数IO操作,不可避免地"不安全""看"？

这是我想回答的面试问题:

给定包含N成员的社交网络和包含M成对成员形成友谊的时间戳的日志文件,设计算法以确定所有成员连接的最早时间(即,每个成员是朋友的朋友的朋友). ..一个朋友).假设日志文件按时间戳排序,并且友谊是等价关系.算法的运行时间应该是M log N或更好,并使用与之成比例的额外空间N.

我想的第一件事就是......"我不能这样做!".

但后来我想到这个社交网络怎么能表达为数据结构.Union-find是一种可以使用的数据结构.现在我必须了解所有成员连接时的含义.如何查看实际数据结构以及每个成员彼此成为朋友时的样子？

我想只有在我能够从视觉上或概念上理解系统如何完全连接之后我才能开始弄清楚如何找到与该事件相对应的时间戳.

对于许多问题,我看到推荐的解决方案是使用union-find数据结构.我试着阅读它并思考它是如何实现的(使用C++).我目前的理解是它只是一组集合.因此,要找到元素所属的集合,我们需要n*log n操作.当我们必须执行union时,我们必须找到需要合并的两个集合set_union并对它们进行处理.这对我来说看起来并不十分有效.我对这个数据结构的理解是正确的还是我错过了什么？

对于自动机算法,我需要一种功能语言的快速Union-Find数据结构.由于我需要正式证明数据结构的正确性,我宁愿选择一个简单的结构.

我想要做的是计算一组S关系中元素的等价类R ? S × S.我想最终得到的是一些函数f: S ? S,它将任何元素映射S到其R等价类的(规范)代表.通过"规范",我的意思是我不关心它是什么代表,只要它对于一个等价类的所有元素都是相同的,即我想要f x = f y ? (x,y) ? R持有.

在函数式语言中,最好的数据结构和算法是什么？我应该补充一点,我真的需要"正常"的功能代码,即没有可变性/状态变换器monad.

编辑:与此同时,我提出了这个算法:

m := empty map
for each s ? S do
  if m s = None then
    for each t in {t | (s,t) ? R}
      m := m[t ? s]

这将创建一个映射,将任何元素映射S到其等价类的代表,其中代表是迭代所到达的第一个元素S.我认为这实际上有线性时间(如果地图操作是不变的).但是,我仍然对其他解决方案感兴趣,因为我不知道这在实践中有多高效.

(我的关系在内部表示为"S→(S Set)选项",因此迭代超过{t |(s,t)∈R} - 这是对该结构的廉价操作.)

我正在观看Robert Sedgewick关于快速联盟改进的视频.(https://youtu.be/sEo6LlPxpHE?t=267)

在那里他使用树的大小而不是高度.实际上问题是找到根节点.如果高度很高,发现将很困难.所以我们应该找到一种方法来减轻身高的影响.只有我们比较高度才能达到预期的效果？将较短的树连接到较高的树而不是解决问题而是:将具有较少节点数的树连接到具有较大节点数的树？

以下案例怎么样？

根据视频中的逻辑:

树的大小= 4

B树的大小= 7

如果你将A连接到B. 实际上我们正在使结果树更高(高度4).但是,如果我们基于树高度完成它,我们可以通过将树B连接到A来解决它.结果树的高度为3.

我对吗 ？如果错了我在哪里错了？

我知道可以使用 DFS 和 BFS 检测直接图中的循环。我想知道我们是否可以使用Union-Find检测有向图中的循环？

• 如果是，那么如何？和
• 如果我们不能，那为什么？

我有一条描述图形的记录作为节点和边的集合:

data MyGraph a = MyGraph {
  nodes :: Set a,
  edges :: Set (a,a),
  components :: UnionFindM a -- ?
}
emptyGraph = MyGraph{
  nodes = empty, edges = empty,
  components = emptyUnionFind singleton union --?
}
addEdge g (a,b) = g{
  edges = (a,b) `insert` (edges g),
  components = (components g) >>= (equate a b) -- ?
}

由于我不会删除边缘,我想使用union-find结构跟踪连接的组件(我可以在添加边缘时轻松更新),因为我想映射连接的组件,因此它将是有用的将它们保存为一组.当然,我想获得一个节点的组件.

我发现了我选择的等价库,因为我无法看到如何使用union-find创建集合,而持久性等价需要知道值范围.

现在我可以创建关系,并使用以下命令返回集合:

import Control.Monad(liftM)
import Data.Equivalence.Monad
import Data.Set(singleton, union, fromList)
f = runEquivM …

所以这就是我想要做的:我有一个包含几个等价关系的列表:

l = [[1, 2], [2, 3], [4, 5], [6, 7], [1, 7]]

我想结合共享一个元素的集合.这是一个示例实现:

def union(lis):
  lis = [set(e) for e in lis]
  res = []
  while True:
    for i in range(len(lis)):
      a = lis[i]
      if res == []:
        res.append(a)
      else:
        pointer = 0 
        while pointer < len(res):
          if a & res[pointer] != set([]) :
            res[pointer] = res[pointer].union(a)
            break
          pointer +=1
        if pointer == len(res):
          res.append(a)
     if res == lis:
      break
    lis,res = res,[]
  return res

它打印出来

[set([1, 2, 3, …

存在"具有路径压缩的加权快速联盟"算法.

代码:

public class WeightedQU 
{
    private int[] id;
    private int[] iz;

    public WeightedQU(int N)
    {
        id = new int[N];
        iz = new int[N];
        for(int i = 0; i < id.length; i++)
        {
            iz[i] = i;
            id[i] = i;
        }
    }

    public int root(int i)
    {
        while(i != id[i])
        {
            id[i] = id[id[i]];   // this line represents "path compression"
            i = id[i];
        }
        return i;
    }

    public boolean connected(int p, int q)
    {
        return root(p) == root(q);
    }

    public void …

我本来期望这样一个有用的数据结构被包含在内,C++ Standard Library但我似乎无法找到它.