0

所以，我刚刚开始关注 coursera.org 的新算法课程。由于课程是 JAVA 的，而且我不想同时学习 Java+算法，所以我正在将 JAVA 示例“翻译”成 python。但是，我有点卡住了，因为应该更快的算法性能更差。对我来说奇怪的是，当我运行测试时输入很大，较慢的算法是最快的，......我认为这与我实例化的数组（ids）发生的一些奇怪的事情有关不同的对象：

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 实例之外，数组在比较之前都发生了变化。任何想法为什么？

这是我创建的仓库：https ://github.com/herrmendez/python-algorithms

4

1 回答 1

0

您的算法正在修改传入的列表实例。Python 没有通过可复制值获取参数的概念；每个绑定名称都是按值传递的对象引用，但有些对象类型是不可变的。

将列表的副本传递给算法：

from copy import deepcopy

...

    tmp = e(arr=deepcopy(tree))
于 2013-02-11T16:02:31.287 回答