Python: comportement étrange lors du passage de tableau à l'objet

Question

Donc, je viens de commencer à suivre le nouveau cours d'algorithme de coursera.org. Comme le cours est en Java, et que je ne veux pas apprendre les algorithmes Java + en même temps, je suis en train de "traduire" les samples JAVA en python. Cependant, je suis un peu coincé, car les algorithmes qui devraient être plus rapides sont moins performants. Le plus étrange pour moi, c'est qu'avec une grosse entrée quand j'exécute les tests, l'algorithme le plus lent est le plus rapide, ... et je pense que cela a quelque chose d'étrange avec le tableau (ids) que j'instancie différents objets avec:

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) 

Cette imprime les résultats suivants:

[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 

Pour une raison quelconque, les tableaux sont modifiés avant de se comparer à tous, mais l'instance QuickFindUF. Des idées pourquoi?

C'est le repo que j'ai créé. https://github.com/herrmendez/python-algorithms

Answer 1

Votre algorithme modifie l'instance de liste adoptée en Python n'a pas le concept de prendre des arguments par valeur copiable; Chaque nom lié est une référence d'objet transmise par valeur, mais certains types d'objets sont immuables.

passer le algorithme une copie de la liste:

from copy import deepcopy 

... 

    tmp = e(arr=deepcopy(tree))