所以,我刚开始关注coursera.org网站的新算法课程。因为这门课程是用JAVA编写的,我不想同时学习JAVA+算法,所以我将把JAVA示例“翻译”成python。然而,我有点卡住了,因为应该更快的算法性能更差。对我来说奇怪的是,当我运行测试时,输入量很大,速度较慢的算法是最快的,。。。我认为这与我实例化不同对象的数组(ID)中发生的奇怪现象有关:
import time
from utils.benchmark import *
from quickunion import *
from quickunion_weighted import *
from quickfind import *
# create only one array of id's so the comparison is fair
ids = random_tree(10)
my_trees = [QuickFindUF, QuickUnionUF,
QuickUnionWeighted, QuickUnionPathCompression]
print "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n"
def test(classes, tree):
for e in classes:
tmp = e(arr=tree)
print tmp.id
print "%s:" % tmp.__class__.__name__
t = time.clock()
print "\tare 3 and 6 connected?: %s" % tmp.connected(3, 6)
"\tunion(3, 6): "
tmp.union(3,6)
print "\tare 3 and 6 connected?: %s" % tmp.connected(3, 6)
print "Total time: {0} ".format(time.clock()-t)
if __name__ == '__main__':
test(my_trees, ids)
这将打印以下结果:
[1, 8, 1, 7, 4, 8, 5, 7, 8, 2]
QuickFindUF:
are 3 and 6 connected?: False
are 3 and 6 connected?: True
Total time: 2.7e-05
[1, 8, 1, 5, 4, 8, 5, 5, 8, 2]
QuickUnionUF:
are 3 and 6 connected?: True
are 3 and 6 connected?: True
Total time: 2.6e-05
[1, 8, 1, 5, 4, 8, 5, 5, 8, 2]
QuickUnionWeighted:
are 3 and 6 connected?: True
are 3 and 6 connected?: True
Total time: 2.8e-05
[1, 8, 1, 5, 4, 8, 5, 5, 8, 2]
QuickUnionPathCompression:
are 3 and 6 connected?: True
are 3 and 6 connected?: True
Total time: 2.7e-05
出于某种原因,除了QuickFindUF实例之外,其他所有实例中的数组在进行比较之前都发生了更改。知道为什么吗?你知道吗
您的算法正在修改传入的列表实例。Python没有按可复制值获取参数的概念;每个绑定名称都是按值传递的对象引用,但有些对象类型是不可变的。你知道吗
向算法传递列表的副本:
相关问题 更多 >
编程相关推荐