并查集基于size优化，(python)另一种写法更快哦

来源：6-4 基于size的优化

qq_笑冰凌_04143298

2018-11-15

老师，您好！
在并查集，基于size优化这节，我用python写的，增加sz[]前和后，执行n=10000,效果并不明显，（时间分别是：2.82500004768s、2.80200004578s），这是为什么呢，python跟C++有什么区别吗？
反而用另一种写法，效果明显，直接在unionElements中，不调用find,重新写find的过程，并记录以它为根的节点数，然后再做关联。同样执行n=10000,时间为0.172000169754s
请老师看一下，这段代码

    def unionElements(self,p,q):
        if (p<0 or p>self.count):
            raise "p index id out of (0-(%d-1))" % self.count
        else:
            pSize = 1
            while(self.parent[p] != p):
                p = self.parent[p]
                pSize = pSize + 1
            qSize= 1
            while(self.parent[q] !=q ):
                q = self.parent[q]
                qSize = qSize +1
            if (pSize > qSize):
                self.parent[q] = self.parent[p]
            else:
                self.parent[p] = self.parent[q]

写回答

2回答

liuyubobobo

2018-11-16

Python和C++有很大的区别。这里面最大的区别就是：Python是一个脚本语言，而非编译语言。而C++是一个典型的编译语言。这意味着Python不是先编译，后运行的，而是一边解析，一边运行的；从而，解析器本身的工作方式，将更多的决定你的程序的性能，而不完全是算法。（关于编译型语言，解析型语言的不同工作原理，包括更多和编译相关的话题，可以在网上搜索相关资料进行自学。）

所以，我不是很建议使用脚本型语言来考察算法的底层实现性能的。这是因为，脚本型语言的程序运算性能，和你的脚本是如何写的，关系巨大（因为这关系到解析器如何解析），从而，使得逻辑的作用不是那么明显（两个使用同样算法的程序，书写方式不同，性能差异就会巨大）。这一点，在同复杂度的算法上表现更明显！你的这个问题就是一个例子：）

当然，并不是说不能用脚本语言学习算法，用任何语言学习算法的逻辑原理都是没有问题的。但是要想仔细探究比较不同算法的性能差异，尤其是通复杂度下一些细微优化的性能差异，近乎只能使用编译型语言：）

所以，你遇到的现象是正常的。这是Python的问题，不是你的问题：）当然，如果使用一个语言，了解这个语言的规则，怎么写效率更高，是很有必要，尤其是在脚本语言的学习过程中。不过这已经超出这个课程的话题了：）

如果使用脚本语言实验算法性能，就会遇到这个问题，比如：

https://coding.imooc.com/learn/questiondetail/81296.html

http://coding.imooc.com/learn/questiondetail/4984.html

https://coding.imooc.com/learn/questiondetail/11257.html

现在慕课网的问答区课程之间不互通了，我的其他课程的同学，使用脚本语言都会遇到同样的问题。甚至对于刷Leetcode或者做算法比赛的同学，会遇到同样的逻辑，C++和Java能通过，Python不能通过，必须小心的再在代码书写上进行优化才能通过的情况。这也是为什么，一些正式的国际顶级算法赛事，现场比赛只能使用编译型语言，即使到现在Python这么流行了，也不能使用Python的原因：）（当然还有其他原因，但这是很重要的一个原因）

加油！：）

qq_笑冰凌_04143298

谢谢老师给了这么全面的回答，受益非浅！

2018-11-16

共1条回复