在windows系统下，n=100000时，UF1所用的时间小于UF2

Question

在windows系统下，n=100000时，UF1所用的时间小于UF2

Answer 1

liuyubobobo 2017-08-13 06:35:26

不太应该，请试试使用官方代码是否有这个结果：https://github.com/liuyubobobo/Play-with-Algorithms/tree/master/06-Union-Find/Course%20Code%20(C%2B%2B)/03-Quick-Union

另外，如果使用VS编写代码，请使用release模式测试代码性能。

• 提问者 握别 #1

  1.使用的IDE和老师相同，是CLion
  2.今晚尝试了把UnionFind2、UnionFind1、UnionFindTestHelper三个文件全部替换为官方代码，结果仍为：
  UF1, 200000 ops, 7.479 s
  UF2, 200000 ops, 8.312 s
  
  当n=50000时，结果为：
  UF1, 100000 ops, 3.804 s
  UF2, 100000 ops, 2.806 s
  
  当n=10000时，结果为：
  UF1, 20000 ops, 0.212 s
  UF2, 20000 ops, 0.059 s

• liuyubobobo 回复 提问者 握别 #2

  虽然在我这里测试依然是UF1的时间耗费大于UF2，但是由于计算机的环境不同，我只能认为出现这种情况也是可能的。你的计算机应该性能比较强劲，所以在UF1的union操作的顺次循环访问可以充分利用系统cache比较快，而UF2的find操作的访问地址是跳跃的，硬件无法进行这种加速。
  
  @stcheng1982 分析得非常有道理。UF1的union操作是O(n)级别的，find操作是O(1)级别的。但是对于UF2来说，虽然union是O(1)级别的，但是当数据量比较大的时候，形成的树可能会非常深，使得其find操作并不比O(n)快多少，而其isConnected要进行两次find操作，所以整体可能更慢。试试这一章后续所讲解的基于UF2的优化，再和UF1比比看？：）

• 慕尼黑3917127 #3

  老师感觉这个n的数量对树的高度影响比想象中大得多，能进一步分析一下吗

点开查看后面3条评论

Answer 2

stcheng1982 2017-08-12 15:03:59

UF2 当n 数量级上升后，会出现很多深度很大的集合的情况。这种情况下 isconnect和 union 方法中都会在find上花大量时间。而UF1 isconnect 始终是O（1） ， 只有union操作会遍历整个数组

• liuyubobobo #1

  赞！感谢你的回复：）