并查集路径压缩比rank版本要慢

Question

如题，java8中测试了10000000的数据量，路径压缩要比rank版本慢，而且如果同时做路径压缩和rank优化更慢

Answer 1

liuyubobobo 2019-12-16 17:32:07

我只能说有可能。其实测试路径压缩的效率，关键不是数据量多少，而是合并过程，是否会形成超级长的链条。如果会产生诸如 1 <- 2 <- 3 <- 4 <- 5 ... <- 10000 这样的链，路径压缩一定优于没有路径压缩。

但如果你的测试用例不产生这种长链，那么路径压缩过程本身是额外的操作，自然会有更多的消耗。但是应该不会把性能拖累的太差。

继续加油！：）