Façons efficaces de dupliquer tableau / liste en Python
Note: je suis un développeur Ruby qui essaie de trouver mon chemin en Python.
quand j'ai voulu comprendre pourquoi certains scripts utilisent mylist[:] au lieu de list(mylist) pour dupliquer des listes, j'ai fait un benchmark rapide des différentes méthodes pour dupliquer range(10) (voir code ci-dessous).
EDIT: j'ai mis à jour les tests pour utiliser le timeit de Python comme suggéré ci-dessous. Il est donc impossible de la comparer directement à Ruby, parce que timeit ne rend pas compte de la boucle alors que Benchmark de Ruby le fait, donc le code Ruby est pour référence seulement .
Python 2.7.2
Array duplicating. Tests run 50000000 times
list(a) 18.7599430084
copy(a) 59.1787488461
a[:] 9.58828091621
a[0:len(a)] 14.9832749367
pour référence, J'ai écrit le même script dans Ruby too:
Ruby 1.9.2p0
Array duplicating. Tests 50000000 times
user system total real
Array.new(a) 14.590000 0.030000 14.620000 ( 14.693033)
Array[*a] 18.840000 0.060000 18.900000 ( 19.156352)
a.take(a.size) 8.780000 0.020000 8.800000 ( 8.805700)
a.clone 16.310000 0.040000 16.350000 ( 16.384711)
a[0,a.size] 8.950000 0.020000 8.970000 ( 8.990514)
Question 1: qu'est-ce que mylist[:] faire différemment qu'il est 25 % plus rapide que même mylist[0:len(mylist)] . Est-ce qu'il copie en mémoire directement ou quoi?
Question 2: edit: les benchmarks mis à jour ne montrent plus de différences énormes entre Python et Ruby. était: est-ce que j'ai implémenté les tests d'une manière manifestement inefficace, de sorte que Ruby code est tellement plus rapide que Python?
Maintenant, les exemples de code:
Python:
import timeit
COUNT = 50000000
print "Array duplicating. Tests run", COUNT, "times"
setup = 'a = range(10); import copy'
print "list(a)tt", timeit.timeit(stmt='list(a)', setup=setup, number=COUNT)
print "copy(a)tt", timeit.timeit(stmt='copy.copy(a)', setup=setup, number=COUNT)
print "a[:]tt", timeit.timeit(stmt='a[:]', setup=setup, number=COUNT)
print "a[0:len(a)]t", timeit.timeit(stmt='a[0:len(a)]', setup=setup, number=COUNT)
Ruby:
require 'benchmark'
a = (0...10).to_a
COUNT = 50_000_000
puts "Array duplicating. Tests #{COUNT} times"
Benchmark.bm(16) do |x|
x.report("Array.new(a)") {COUNT.times{ Array.new(a) }}
x.report("Array[*a]") {COUNT.times{ Array[*a] }}
x.report("a.take(a.size)") {COUNT.times{ a.take(a.size) }}
x.report("a.clone") {COUNT.times{ a.clone }}
x.report("a[0,a.size]"){COUNT.times{ a[0,a.size] }}
end
2 réponses
utilisez le module timeit en python pour tester les temps.
from copy import *
a=range(1000)
def cop():
b=copy(a)
def func1():
b=list(a)
def slice():
b=a[:]
def slice_len():
b=a[0:len(a)]
if __name__=="__main__":
import timeit
print "copy(a)",timeit.timeit("cop()", setup="from __main__ import cop")
print "list(a)",timeit.timeit("func1()", setup="from __main__ import func1")
print "a[:]",timeit.timeit("slice()", setup="from __main__ import slice")
print "a[0:len(a)]",timeit.timeit("slice_len()", setup="from __main__ import slice_len")
Résultats:
copy(a) 3.98940896988
list(a) 2.54542589188
a[:] 1.96630120277 #winner
a[0:len(a)] 10.5431251526
c'est sûrement les pas supplémentaires impliqués dans a[0:len(a)] qui sont la raison de sa lenteur.
Voici la comparaison du code octet des deux:
In [19]: dis.dis(func1)
2 0 LOAD_GLOBAL 0 (range)
3 LOAD_CONST 1 (100000)
6 CALL_FUNCTION 1
9 STORE_FAST 0 (a)
3 12 LOAD_FAST 0 (a)
15 SLICE+0
16 STORE_FAST 1 (b)
19 LOAD_CONST 0 (None)
22 RETURN_VALUE
In [20]: dis.dis(func2)
2 0 LOAD_GLOBAL 0 (range)
3 LOAD_CONST 1 (100000)
6 CALL_FUNCTION 1
9 STORE_FAST 0 (a)
3 12 LOAD_FAST 0 (a) #same up to here
15 LOAD_CONST 2 (0) #loads 0
18 LOAD_GLOBAL 1 (len) # loads the builtin len(),
# so it might take some lookup time
21 LOAD_FAST 0 (a)
24 CALL_FUNCTION 1
27 SLICE+3
28 STORE_FAST 1 (b)
31 LOAD_CONST 0 (None)
34 RETURN_VALUE
Je ne peux pas faire de commentaire sur le timing ruby vs. Le timing python. Mais je peux commenter sur list vs. slice . Voici une inspection rapide du bytecode:
>>> import dis
>>> a = range(10)
>>> def func(a):
... return a[:]
...
>>> def func2(a):
... return list(a)
...
>>> dis.dis(func)
2 0 LOAD_FAST 0 (a)
3 SLICE+0
4 RETURN_VALUE
>>> dis.dis(func2)
2 0 LOAD_GLOBAL 0 (list)
3 LOAD_FAST 0 (a)
6 CALL_FUNCTION 1
9 RETURN_VALUE
Avis list exige LOAD_GLOBAL pour trouver la fonction list . La recherche des globals (et des fonctions d'appel) en python est relativement lente. Cela expliquerait pourquoi a[0:len(a)] est aussi plus lent. Rappelez-vous également que list doit être capable de gérer itérateurs arbitraires alors que trancher ne le fait pas. Cela signifie que list doit allouer une nouvelle liste, empaqueter des éléments dans cette liste car il itère sur la liste et redimensionner si nécessaire. Il y a quelques choses ici qui sont chères -- redimensionner si nécessaire et itérer (effectivement en python, pas en C). Avec la méthode de découpage, vous pouvez calculer la taille de la mémoire dont vous aurez besoin afin peut probablement éviter de redimensionner, et l'itération peut être fait complètement en C (probablement avec un memcpy ou quelque chose comme ça.
disclaimer : Je ne suis pas un dev python, donc je ne sais pas comment les internes de list() sont implémentés à coup sûr. Je ne fais que spéculer sur ce que je sais de la spécification.
EDIT -- donc j'ai regardé la source (avec un peu de conseils de Martijn). Le code correspondant est listobject.c . list appels list_init qui appelle alors listextend à la ligne 799. Cette fonction a quelques vérifications pour voir si elle peut utiliser une rapide branche si l'objet est une liste ou un tuple (ligne 812). Enfin, le levage lourd est fait à partir de la ligne 834:
src = PySequence_Fast_ITEMS(b);
dest = self->ob_item + m;
for (i = 0; i < n; i++) {
PyObject *o = src[i];
Py_INCREF(o);
dest[i] = o;
}
comparez cela à la version slice qui je pense est défini dans list_subscript (ligne 2544). Qui appelle list_slice (ligne 2570) où le levage lourd est effectué par la boucle suivante (ligne 486):
src = a->ob_item + ilow;
dest = np->ob_item;
for (i = 0; i < len; i++) {
PyObject *v = src[i];
Py_INCREF(v);
dest[i] = v;
}
Ils sont à peu près le même code, il n'est donc pas surprenant que la performance soit presque la même pour les grandes listes (où la charge des petites choses comme déballer les tranches, regarder les variables globales, etc devient moins important)
Voici comment je pourrais lancer python tests (et les résultats pour mon système Ubuntu):
$ python -m timeit -s 'a=range(30)' 'list(a)'
1000000 loops, best of 3: 0.39 usec per loop
$ python -m timeit -s 'a=range(30)' 'a[:]'
10000000 loops, best of 3: 0.183 usec per loop
$ python -m timeit -s 'a=range(30)' 'a[0:len(a)]'
1000000 loops, best of 3: 0.254 usec per loop