from time import perf_counter
def flatten(array):
result = []
def recurse(arr):
for item in arr:
if isinstance(item, list):
recurse(item)
else:
result.append(item)
recurse(array)
return result
On peut simplifier en
def flatten(L, R):
for x in L:
if isinstance(x, list):
flatten(x,R)
else:
R.append(x)
L = [8, [42, [7,3],[[10],[5]], [[]],[[[999]]], 0], 101]
R=[]
flatten(L, R)
print(R)
ce qui se montre encore un peu plus rapide.
fred1599 a écrit:
from time import perf_counter
from function import flatten
def data(n, p, N):
temp = [[z] for z in range(n)]
for i in range(p):
temp = [temp]
L = [temp for _ in range(N)]
return L
n, p, N = 1000, 900, 1000
L = data(n, p, N)
b = perf_counter()
print(flatten(L))
print("rec_flatten :", round(perf_counter() - b, 2), "secondes")
Résultat : 0,09 s
Sans le print() j'arrive à 0,03 s
Bien sûr, j'avais mesuré sans le print. En outre, le temps d'exécution en Python seul est déjà très court, donc il est plus significatif de prendre un jeu de données plus important. Et là, comme indiqué dans mon message précédent, le ratio est de 8,5 ce qui n'est pas négligeable alors que ton code en fait ne prend en compte aucun typage et donc c'est l'API C de Python (lente) qui prend en charge ton code, ça se voit si on sort le fichier html annoté. Je crois que je viens en partie de comprendre ce ratio : une fonction récursive c'est comme une itération et on sait bien que Python est lent à cela. Ici, le fait que la fonction récursive soit exécutée dans du code écrit en C la rend beaucoup plus rapide qu'en Python.
Pour le confirmer, il te suffit de faire l'expérience suivante avec la suite de Fibonacci :
# fibo.pyx
cdef fiboA(n):
if n > 2:
return fiboA(n - 1) + fiboA(n - 2)
return 1
cdef int fiboB(int n):
if n > 2:
return fiboB(n - 1) + fiboB(n - 2)
return 1
def PyA(n):
return fiboA(n)
def PyB(n):
return fiboB(n)
# test.py
from time import perf_counter
from fibo import PyA, PyB
def fibo(n):
if n > 2:
return fibo(n - 1) + fibo(n - 2)
return 1
n = 42
begin = perf_counter()
s =fibo(n)
end = perf_counter()
print("Python pur %.2fs" % (end - begin))
begin = perf_counter()
sA = PyA(n)
end = perf_counter()
print("Cython léger %.2fs" % (end - begin))
begin = perf_counter()
sB = PyB(n)
end = perf_counter()
print("Cython typé %.2fs" % (end - begin))
print(s == sA == sB, s)
Qu'est-ce que j'ai manqué? Le deepcopy préserve bien la structure de liste de listes. Est-ce que tu t'attendais à une RecursionError dans deepcopy?
Ubuntu Python 3.10 :
File "/usr/lib/python3.10/copy.py", line 137, in deepcopy
d = id(x)
RecursionError: maximum recursion depth exceeded while calling a Python object
Google colab Python 3.8
/usr/lib/python3.8/copy.py in deepcopy(x, memo, _nil)
144 copier = _deepcopy_dispatch.get(cls)
145 if copier is not None:
--> 146 y = copier(x, memo)
147 else:
148 if issubclass(cls, type):
RecursionError: maximum recursion depth exceeded while calling a Python object
Autrement dit, Python est capable de créer une structure de données qu'il est incapable de copier parce qu'il a choisi de coder la copie en Python et récursivement. A peine croyable !
Python n'a pas choisi de coder. C'est un langage de programmation, pas une personne.
Par contre une personne comme vous et moi peut faire des choix, par exemple de chercher ou pas comment modifier les limites par défaut https://docs.python.org/3/library/sys.html#sys.setrecursionlimit quand elles ne conviennent pas dans un cas particulier. Plutot que d'accuser le langage.
- Edité par michelbillaud 5 février 2023 à 9:29:41
Python n'a pas choisi de coder. C'est un langage de programmation, pas une personne.
Oui, enfin Python n'en est pas encore à se coder lui-même.
michelbillaud a écrit:
Par contre une personne comme vous et moi peut faire des choix, par exemple de chercher ou pas comment modifier les limites par défaut https://docs.python.org/3/library/sys.html#sys.setrecursionlimit quand elles ne conviennent pas dans un cas particulier. Plutot que d'accuser le langage.
Oui, je le sais bien : Limitation du nombre d’appels récursifs et il aurait été mieux de suggérer de faire une issue ou de recoder itérativement deepcopy qui parcourt une structure de données comme on parcourrait un graphe en profondeur. Dans beaucoup de lib de graphes, on code ou même recode des algorithmes naturellement récursifs en leur équivalent itératif, voir par exemple des lib NetworkX ou Networkit, pour éviter les débordements de pile et les lenteurs d'exécution.
Découverte Python Doc Tkinter Les chaînes de caractères
Découverte Python Doc Tkinter Les chaînes de caractères
Python c'est bon, mangez-en.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.
Découverte Python Doc Tkinter Les chaînes de caractères
Découverte Python Doc Tkinter Les chaînes de caractères