La mauvaise performance que vous observez est causé par un bogue dans le Python garbage collector. Pour résoudre ce problème, désactivez la collecte des ordures que vous construisez la liste et de l'activer lorsque vous avez terminé. Vous trouverez un rendement qui se rapproche de la amoritized 0(1) le comportement attendu de la liste en ajoutant en Python.
(Vous pouvez également ajuster le garbage collector de déclencheurs ou de manière sélective virés comme vous le progrès, mais je ne suis pas d'explorer ces options dans cette réponse, parce qu'ils sont plus complexes, et je soupçonne que votre cas est favorable à la solution ci-dessus.)
Arrière-plan:
Voir: http://bugs.python.org/issue4074 et aussi http://docs.python.org/release/2.5.2/lib/module-gc.html
Le rapporteur observe que, ajoutant des objets complexes, des objets qui ne sont pas des nombres ou des chaînes de caractères) à une liste ralentit de manière linéaire avec la liste se développe dans la longueur.
La raison de ce comportement est que le garbage collector est à vérifier et revérifier chaque objet de la liste pour voir si elles sont admissibles pour la collecte des ordures. Ce comportement provoque l'augmentation linéaire dans le temps pour ajouter des objets à une liste. Un correctif devrait débarquer en py3k, de sorte qu'il ne devrait pas s'appliquer à l'interprète que vous utilisez.
Test:
J'ai couru un test pour le démontrer. Pour 1k itérations je ajouter 10k objets d'une liste, et d'enregistrer le moteur d'exécution pour chaque itération. L'ensemble de l'exécution différence est immédiatement évident. Avec la collecte des ordures désactivé au cours de la boucle interne de l'essai, le moteur d'exécution sur mon système est de 18,6 s. Avec la collecte des ordures activé pour l'ensemble du test, la durée d'exécution est 899.4 s.
C'est le test:
import time
import gc
class A:
def __init__(self):
self.x = 1
self.y = 2
self.why = 'no reason'
def time_to_append(size, append_list, item_gen):
t0 = time.time()
for i in xrange(0, size):
append_list.append(item_gen())
return time.time() - t0
def test():
x = []
count = 10000
for i in xrange(0,1000):
print len(x), time_to_append(count, x, lambda: A())
def test_nogc():
x = []
count = 10000
for i in xrange(0,1000):
gc.disable()
print len(x), time_to_append(count, x, lambda: A())
gc.enable()
Source: http://hypervolu.me/~erik/programming/python_lists/listtest.py.txt
Résultat graphique: le Rouge est de la cg sur, le bleu est la cg off. l'axe y est la seconde échelle logarithmique.
![]()
Comme pour les deux parcelles diffèrent de plusieurs ordres de grandeur dans la composante y, ici, ils sont de façon indépendante avec l'axe des y ont évolué de manière linéaire.
![]()
![]()
Il est intéressant de noter, avec la collecte des ordures, nous ne voyons que de petits pics en exécution par 10k ajoute, ce qui suggère que Python liste réaffectation des coûts relativement faibles. En tout cas, ils sont de plusieurs ordres de grandeur inférieure à la collecte des ordures coûts.
La densité des parcelles ci-dessus il est difficile de voir qu'avec le garbage collector, la plupart des intervalles réellement avoir de bonnes performances; c'est seulement lorsque le garbage collector cycles que nous rencontrons le comportement pathologique. Vous pouvez observer ce dans cet histogramme de 10k ajouter de temps. La plupart des points de données à l'automne autour de 0,02 s par 10k ajoute.
![]()
Les données brutes utilisées pour la production de ces parcelles peut être trouvé à http://hypervolu.me/~erik/programmation/python_lists/
