1回答

liuyubobobo

2017-01-16

已采纳

6-2的quick find思路下的union-find，因为其union操作为O(n)级别的，所以执行n个指令，其复杂度是O(n^2)级别的。倒推回去，如果你的数据量n=10000用8s，n=1000大概用0.08s（100倍）这个数量级（当然和你当时生成数据具体有多少find指令，有多少union指令相关，但大概是这个数量级）。所以你会觉得n=1000很快，但n多一个数量级（10倍），时间就难以忍受了。这就是O(n)和O(n^2)复杂度算法之间的本质差异。（在我的实验中，n=10000，0.4s，可以忍受；但是n=100000，一下在就是40s了。）

具体到C++,Java和Python不同语言之间的速度差，嗯，没办法，脚本语言本身就是这么慢！首先，我的课程中n=10000的结果是0.4s左右；你的Python是8s，20倍的差异，这个量级是差不多的。尤其是对于循环这种任务。不信的话，可以把程序写得再简单一些，就看把一个n维数组的所有元素都赋值为42，看看差别?:-)

不过python的内核高度使用C语言优化，所以调用python标准库函数会非常快。正因如此，不适宜用python做底层数据结构的实现。在使用python做实现上，也要注意pythonic，比如quick-find里的那层循环赋值，我估计使用map就要快不少。

同时，也有不少为Python加速的第三方，可以尝试一下，最典型的如pypy, CPython等。不过，效率依然是脚本语言最大的缺点，Google现在在尝试使用GO取代一部分Python服务，就是基于这个考虑。

2

1

Sombra

谢谢，知道了

2017-01-17

共1条回复