Je n'arrive pas à aplatir une liste de liste (de façon non récursive). J'ai écrire la fonction suivante :
def aplatir(liste):
liste_aplatie =[]
for e in liste:
if type(e) == list :
for i in range(len(e)):
liste_aplatie.append(e[i])
else:
liste_aplatie.append(e)
return liste_aplatie
Mais celle-ci ne fonctionne pas j'ai alors ajouté :
def aplatir2(liste):
liste_aplatie =[]
for e in liste:
if type(e) == list :
for i in e:
if type(i) == list :
for j in i:
liste_aplatie.append(j)
else:
liste_aplatie.append(i)
else:
liste_aplatie.append(e)
return liste_aplatie
mais elle ne fonctionne toujours pas
Comment puis-je faire ?
Je vous donne un exemple de liste qui doit pouvoir être aplatie :
À première vue, je dirais que tu ne gères que deux niveaux...
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
l = [8, [2, [7,3],[[10],[5]], [[[999]]], 0], 101]
foo = 1
while foo:
s = []
foo = 0
for i in l:
if type(i)==list:
s.extend(i)
foo = 1
else:
s.append(i)
l = s
J'ai essayé les deux méthodes, la première est un peu plus rapide. Les deux méthodes fonctionnent correctement. - from time import perf_counter # L = list(range(10)) for _ in range(7): L = [L for l in range(10)] b = perf_counter() i = -1 while (i:=i+1) < len (L): while type(L[i]) == list: L[i:i+1] = L[i] print(round(perf_counter()-b,2), "secondes") for l in L: if type(l) == list: print(l) break # L = list(range(10)) for _ in range(7): L = [L for l in range(10)] b = perf_counter() i = 0 while i < len (L): if type(L[i]) == list : L[i:i+1] = L[i] else: i += 1 print(round(perf_counter()-b,2), "secondes") for l in L: if type(l) == list: print(l) break - 22.58 secondes 23.83 secondes
Le Tout est souvent plus grand que la somme de ses parties.
l = [8, [2, [7,3],[[10],[5]], [[[999]]], 0], 101]
l = str(l).replace('[','').replace(']','')
l = eval(f"[{l}]")
print (l)
- Edité par josmiley il y a environ 1 heure
ça donne juste un truc qui ne marche pas
>>> l = [ '[' ]
>>> l = str(l).replace('[','').replace(']','')
>>> print (l)
''
---
Bon, une méthode simple (une boucle, un test) et propre
on retire le premier élément de la liste
si c'est une liste on la colle devant le reste de la liste
sinon, on le met dans la liste des résultats
et ce, tant que (etc)
def flatten(aList):
result = []
while aList != []:
first, *aList = aList
if type(first) == list:
aList = first + aList
else:
result.append(first)
return result
test
l = [8, [2, [7,3],[[10],[5]], [[[999]]], 0], 101]
print(flatten(l))
affiche
>>> [8, 2, 7, 3, 10, 5, 999, 0, 101]
L'idée (utiliser une liste auxiliaire qui cumule les résultats partiels) correspond à la technique classique du "paramètre tampon" en programmation récursive.
def flatten(alist):
iterator, sentinel, stack = iter(alist), object(), []
while True:
value = next(iterator, sentinel)
if value is sentinel:
if not stack:
break
iterator = stack.pop()
elif isinstance(value, str):
yield value
else:
try:
new_iterator = iter(value)
except TypeError:
yield value
else:
stack.append(iterator)
iterator = new_iterator
l = [8, [2, [7, 3], [[10], [5]], [[[999]]], 0], 101]
print([i for i in flatten(l)])
Plus une autre avec générateur,
from collections.abc import Iterable
def flatten(alist):
for x in alist:
if isinstance(x, Iterable) and not isinstance(x, (str, bytes)):
yield from flatten(x)
else:
yield x
l = [8, [2, [7, 3], [[10], [5]], [[[999]]], 0], 101]
print([i for i in flatten(l)])
Bref il y a l'embarras du choix, avec un minimum de temps de recherches, on trouve !
- Edité par fred1599 30 janvier 2023 à 21:51:36
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Je n'ai pas d'autre idée (en dehors de la récursivité) que de coder ça avec une simple pile P et je trouve ça assez naturel : chaque fois que le parcours découvre une nouvelle liste, on l'empile dans P, chaque fois qu'on épuise une liste, on la dépile de P. J'utilise une pile d'itérateurs de listes, ça m'évite de gérer des indices.
Le code :
def flatten(L):
P=[]
R=[]
P.append(iter(L))
while P:
it=P[-1]
try:
v=next(it)
if type(v)==list:
P.append(iter(v))
else:
R.append(v)
except:
P.pop()
return R
L = [8, [42, [7,3],[[10],[5]], [[]],[[[999]]], 0], 101]
print(flatten(L))
Suis relativement déçu par les performances car me semblait algorithmiquement optimal, c'est légèrement plus lent que le premier code de josmiley testé par plf. Toutefois, j'ai crû comprendre que vos codes modifiaient la liste à examiner, je ne trouve pas ça terrible (c'est vrai qu'on pourrait faire une deepcopy).
Bref il y a l'embarras du choix, avec un minimum de temps de recherches, on trouve !
Le pop(0) est fatal pour les performances : plus de 40 secondes pour aplatir une liste de profondeur 1 et de 100000 éléments, ça devrait mettre quelques dixièmes de secondes.
michelbillaud a écrit:
ça donne juste un truc qui ne marche pas
>>> l = [ '[' ]
>>> l = str(l).replace('[','').replace(']','')
>>> print (l)
''
La liste donnée est censée être valide pour le problème posé. Au contraire la méthode proposée par josmiley est très efficace, il suffit juste de se débarrasser du eval pour la rendre propre, ce qui est facile ici.
michelbillaud a écrit:
Bon, une méthode simple (une boucle, un test) et propre
on retire le premier élément de la liste
si c'est une liste on la colle devant le reste de la liste
sinon, on le met dans la liste des résultats
et ce, tant que (etc)
def flatten(aList):
result = []
while aList != []:
first, *aList = aList
if type(first) == list:
aList = first + aList
else:
result.append(first)
return result
Problème de performance encore plus important que ci-dessus alors qu'aplatir une liste de 100000 éléments n'a rien de déraisonnable (avec ce code, nécessite 2 minutes sur ma machine).
L'origine du problème est moins flagrante que le pop(0) ci-dessus. Je dirais que c'est à la ligne 4, en apparence anodine, mais qui effectue 99999 affectations (répétées avec une unité de moins à chaque étape suivante) d'où une complexité qui devient quadratique.
On pourrait croire effectivement que
first, *aList = aList
déclare juste un pointeur aList vers le 2e élément de la liste mais sans doute que le pseudo-opérateur * oblige à faire une copie massive de pointeurs.
C'est équivalent à un slice aList[1:] du point de vue des performances :
def flatten(aList):
result = []
while aList != []:
first=aList[0]
aList = aList[1:]
if type(first) == list:
aList = first + aList
else:
result.append(first)
return result
et un slice aList[1:] effectue autant de copies de pointeurs que d'éléments dans le slice, ce qui confirme que malgré les apparences, créer des slices peut avoir un impact énorme sur les performances.
La bonne méthode n'est pas de prendre le premier élément de la liste mais le dernier, le coût amorti de l'opération est alors un O(1) :
from copy import deepcopy
def aplatir(L):
R = []
L=deepcopy(L)
while L:
item = L.pop()
if isinstance(item, list):
L.extend(item)
else:
R.append(item)
return R[::-1]
et là, cela nécessite 0.25 s de traiter une liste de 100000 éléments.
Sur les performances : si on cherche les performances, on ne commence pas par s'attacher les pieds et se bander les yeux en s'imposant
De ne pas recourir à la récursivité
De le faire en python :-)
Si on veut juste que ça marche pour l'exemple donné, on écrit
print ( [8, 2, 7, 3, 10, 5, 999, 0, 101])
Et "c'est valide pour le probleme posé" ? Il n'est pourtant écrit nulle part que les listes ne contiennent que des nombres.
Enfin, si on compare des performances, on ne compare pas des algorithmes, mais des implémentations. Le choix de la représentation des listes, et le cout des opérations "elementaires".
- Edité par michelbillaud 1 février 2023 à 8:12:23
Le pop(0) est fatal pour les performances : plus de 40 secondes pour aplatir une liste de profondeur 1 et de 100000 éléments, ça devrait mettre quelques dixièmes de secondes.
Dommage de parler du code le moins intéressant de tout ceux que je présente... À mon sens les générateurs peuvent sortir leur épingle du jeu.
Après l'analyse à outrance... si je veux de la performance, je prends un algo C et je crée mon module python avec cython ou je prends numpy, pandas et ses amis car pour 100000 éléments ça doit valoir le coup de l'utiliser.
Perso, je venais juste montrer au PO que sur le net il y avait l'embarras du choix et qu'il y a un manque de recherches de sa part. Qui puis est c'est une question très couramment posée, et le but n'est pas de faire une course au code le plus moche et rapide.
- Edité par fred1599 1 février 2023 à 9:42:40
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
a un coût proportionnel à la taille de la liste parce que - à l'intérieur dedans l'implémentation - elle produit un tableau qui est une copie de list, privé du premier élément. Pas de mystère, c'est écrit dans la doc https://wiki.python.org/moin/TimeComplexity
<< Internally, a list is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move). If you need to add/remove at both ends, consider using a collections.deque instead. >>
Donc si on veut un algorithme linéaire (est-ce le but de l'exercice ?), on regarde la même page, et on voit que pour retirer un élément, au début ça va pas être possible (en temps élémentaire), mais à la fin, avec "pop last", ça roule en O(1)
last = list.pop()
Et ce n'est pas tout, il y a aussi
if type(first) == list:
aList = first + aList
pour concaténer au début, dont le temps est proportionnel à la somme des tailles. Ceci dans une boucle, ahem.
Bref il s'en suit
que c'est destructif sur la liste reçue en paramètre (shit happens); faudra copier avant si c'est un problème. On n'est (hélas) pas dans le monde merveilleux du "purement fonctionnel"
qu'on produit les résultats à l'envers, et qu'il faudra donc renverser à la fin.
Voici un équivalent de mon 1er code ci-dessous avec l'objet deque.
from collections import deque
def flatten(alist):
flattened_list = []
queue = deque(alist)
while queue:
item = queue.popleft()
if isinstance(item, list):
queue.extendleft(reversed(item))
else:
flattened_list.append(item)
return flattened_list
l = [8, [2, [7, 3], [[10], [5]], [[[999]]], 0], 101]
print(flatten(l))
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Sur les performances : si on cherche les performances,
On ne cherche pas de performances, on cherche simplement à ce qu'au moins le code termine dans une durée acceptable pour une taille raisonnable du problème. La liste que j'ai prise est totalement innocente :
L=[[x] for x in range(10**5)]
michelbillaud a écrit:
De ne pas recourir à la récursivité
De le faire en python :-)
On est sur le forum Python et ne pas choisir la récursivité fait partie du problème dès le départ (relire le message initial).
Pour la récursivité, sur des listes emboîtées de profondeur 200, ce code se montre 10 fois plus lent que mon code utilisant une pile, sans compter le stackOverflow possible en Python.
michelbillaud a écrit:
Et "c'est valide pour le probleme posé" ? Il n'est pourtant écrit nulle part que les listes ne contiennent que des nombres.
Un petit peu de bon sens montre quelle était l'intention.
michelbillaud a écrit:
Enfin, si on compare des performances, on ne compare pas des algorithmes, mais des implémentations. Le choix de la représentation des listes, et le cout des opérations "elementaires".
L'algorithme doit prendre en compte la complexité des opérations sur les structures de données utilisées (ici la liste qui est une structure indépendante du langage) et dans le cas de ton code, tu ne t'es sans doute pas rendu compte que tu copiais une très longue liste à chaque itération.
EDIT
fred1599 a écrit:
Voici un équivalent de mon 1er code ci-dessous avec l'objet deque.
from collections import deque
def flatten(alist):
flattened_list = []
queue = deque(alist)
while queue:
item = queue.popleft()
if isinstance(item, list):
queue.extendleft(reversed(item))
else:
flattened_list.append(item)
return flattened_list
l = [8, [2, [7, 3], [[10], [5]], [[[999]]], 0], 101]
print(flatten(l))
Bien joué, c'était la structure adaptée ici.
Et les performances plutôt meilleure qu'avec la pile.
> L'algorithme doit prendre en compte la complexité des opérations sur les structures de données utilisées (ici la liste qui est une structure indépendante du langage) et dans le cas de ton code, tu ne t'es sans doute pas rendu compte que tu copiais une très longue liste à chaque itération.
Mais bien sur que si. Je ne suis pas exactement un débutant en programmation :-) [j'ai même enseigné ce genre de trucs dans les années 80 - ça ne nous rajeunit pas] et pas encore tout à fait gaga. Enfin pas tout le temps.
L'algorithme que j'ai présenté
est correct (il fournit le résultat voulu)
est très mauvais en terme de complexité (on est d'accord)
et à l'avantage d'être simple (pas de trucs tarabiscotés avec des slices magiques, qui s'avèrent inutiles).
Le but était de présenter UNE PREMIERE APPROCHE, à partir de laquelle on peut ensuite chercher
pourquoi ça ne va pas vite
comment on peut l'améliorer.
Ce qui nécessite d'introduire un truc supplémentaire (en plus de la variable tampon - parce qu'on peut faire sans...) : construire le résultat à l'envers en partant de la fin, et le retourner.
Faut pas sauter les étapes.
PS: Une très jolie solution (absolument horrible en termes de performances) sans variable tampon basée sur l'idée parfaitement intuitive
<< on parcourt la liste "toplevel", quand on tombe sur un élement qui est une liste on insère son contenu à la place". Sinon on passe au suivant >>
# destructive
def horrible(aList):
i = 0
while i < len(aList):
if isinstance(aList[i], list):
aList = aList[ : i] + aList[i] + aList[i+1 : ]
else:
i = i + 1
return aList
comme quoi il faut se méfier des idées parfaitement intuitives qui se présentent.
Ceci dit, c'est un point de départ pour un chemin qui mène à de meilleures solutions, si on se dit qu'on pourrait stocker les résultats trouvés ailleurs, au lieu de les conserver dans aList[: i]
On ne faut pas laisser croire aux débutants qu'on trouve les solutions optimales du premier coup, par un éclair de génie. Ca s'élabore progressivement à partir de trucs pas forcément brillants au départ.
- Edité par michelbillaud 1 février 2023 à 11:12:40
Le pop(0) est fatal pour les performances : plus de 40 secondes pour aplatir une liste de profondeur 1 et de 100000 éléments, ça devrait mettre quelques dixièmes de secondes.
Dommage de parler du code le moins intéressant de tout ceux que je présente... À mon sens les générateurs peuvent sortir leur épingle du jeu.
Je n'ai pas parlé de ton 3e code car la question initiale demandait explicitement un code non récursif. Pour le 2e code, c'est une version que je trouve compliquée (avec ses multiples itérateurs et sa sentinelle, pour le coup on dirait du C voire du code C de Cpython où ils placent des sentinelles un peu partout) du code que j'avais donné avec une pile. En outre, il traite d'un cas plus général que des nombres entiers. Il est toutefois assez rapide. Le fait qu'il soit un générateur est pour moi complètement secondaire, ce que je vois d'abord c'est la nature de l'algorithme.
fred1599 a écrit:
Après l'analyse à outrance... si je veux de la performance, je prends un algo C et je crée mon module python avec cython ou je prends numpy, pandas et ses amis car pour 100000 éléments ça doit valoir le coup de l'utiliser.
Le langage C n'y change rien, ci-dessus, c'était un problème de complexité algorithmique, peut-être avec un algorithme quantique
michelbillaud a écrit:
Critique et construction raisonnée :
La déstructuration par
first, *list = list
a un coût proportionnel à la taille de la liste parce que - à l'intérieur dedans l'implémentation - elle produit un tableau qui est une copie de list, privé du premier élément. Pas de mystère, c'est écrit dans la doc https://wiki.python.org/moin/TimeComplexity
Cela ne documente pas que d, *e =L fait une copie de tous les éléments qui seront dans e (et d'ailleurs ce n'est pas ce qu'il fait, il copie des références vers ces éléments). Et avant ton exemple, je ne suis même pas sûr que j'avais conscience de cette complexité, je le trouve très cachée. Au moins avec un slice on sait qu'on fait une copie de références.
michelbillaud a écrit:
Donc si on veut un algorithme linéaire (est-ce le but de l'exercice ?), on regarde la même page, et on voit que pour retirer un élément, au début ça va pas être possible (en temps élémentaire), mais à la fin, avec "pop last", ça roule en O(1)
last = list.pop()
Et ce n'est pas tout, il y a aussi
if type(first) == list:
aList = first + aList
Absolument. Il faudrait faire une opération en place.
michelbillaud a écrit:
PS: Une très jolie solution (absolument horrible en termes de performances) sans variable tampon basée sur l'idée parfaitement intuitive
<< on parcourt la liste "toplevel", quand on tombe sur un élement qui est une liste on insère son contenu à la place". Sinon on passe au suivant >>
# destructive
def horrible(aList):
i = 0
while i < len(aList):
if isinstance(aList[i], list):
aList = aList[ : i] + aList[i] + aList[i+1 : ]
else:
i = i + 1
return aList
Je ne trouve pas ce code très naturel si on n'est pas un débutant complet : pourquoi remplacer toute la liste alors qu'il suffit d'insérer là où il y a la sous-liste ? C'est comme si pour un tri par sélection je recopiais toute la liste déjà triée à chaque découverte de maximum partiel.
C'est une version que je trouve compliquée du premier code qu'a donné josmiley avec des slices et qui, elle, est relativement efficace en terme de performances en plus. Son autre code est aussi très efficace.
Il s'agit de toutes façons d'insérer à cet endroit là, ou plus exactement de retirer un élément et d'insérer ensuite.
Ce qui change, c'est juste l'expression, les procédés techniques utilisés, plus ou moins sophistiqués. Ce n'estas étonnant qu'on retombe sur des solutions équivalentes.
Ce que le debutant trouvera "naturel", c'est ce qu'il connaît déjà. Ça va dépendre. Par exemple de sa maîtrise des slices à ce moment là (*) Que tu ne trouves pas naturelle telle ou telle facon ça s'explique certainement.
(*) l'enthousiasme pour les slices peut le pousser à en utiliser alors que ce n'est pas apparemment efficace dans les solutions qui sont proposees ici. Alors que la bonne solution, tout le monde sait que c'est d'écrire une extension Python en C :-)
- Edité par michelbillaud 1 février 2023 à 13:50:50
Il s'agit de toutes façons d'insérer à cet endroit là, ou plus exactement de retirer un élément et d'insérer ensuite.
Et en ce sens, je vois ce procédé plus comme une astuce que comme une technique.
fred1599 a écrit:
et une autre avec le générateur [...]
Plus une autre avec générateur,
from collections.abc import Iterable
def flatten(alist):
for x in alist:
if isinstance(x, Iterable) and not isinstance(x, (str, bytes)):
yield from flatten(x)
else:
yield x
l = [8, [2, [7, 3], [[10], [5]], [[[999]]], 0], 101]
print([i for i in flatten(l)])
Bref il y a l'embarras du choix, avec un minimum de temps de recherches, on trouve !
Je ne comprends pas ton enthousiasme à mettre en avant ces codes utilisant des générateurs, c'est juste un design pattern et une façon d'envelopper l'algorithme. Michel Billaud invoquait la récursivité pour atteindre des performances pour ce problème et j'ai donc choisi justement ce générateur pour démentir. En réalité, le générateur ralentit le code d'un facteur énorme, autour de 15. Ci-dessous, le même algorithme mais sans générateur, l'écart est spectaculaire :
from time import perf_counter
def rec_gene(xs):
for x in xs:
if isinstance(x, list):
yield from rec_gene(x)
else:
yield x
def rec_list(L):
R = []
for x in L:
if isinstance(x, list):
R.extend(rec_list(x))
else:
R.append(x)
return R
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
b = perf_counter()
n, p, N = 1000, 900, 1000
L = data(n, p, N)
print("data :", round(perf_counter() - b, 2), "secondes")
b = perf_counter()
R = rec_list(L)
print("rec_list :", round(perf_counter() - b, 2), "secondes")
b = perf_counter()
RR = list(rec_gene(L))
print("rec_gene :", round(perf_counter() - b, 2), "secondes")
# check
print(R == RR)
L'idée (utiliser une liste auxiliaire qui cumule les résultats partiels) correspond à la technique classique du "paramètre tampon" en programmation récursive.
Je ne comprends pas ton enthousiasme à mettre en avant ces codes utilisant des générateurs
Enthousiasme ? Le mot est fort, voir très fort... je présente des codes possibles et répondant à la problématique du PO.
Je pense que l'enthousiaste est celui qui fait du zèle en dépassant les prérogatives du problème, non ?
Je vais pas t'expliquer l'intérêt d'un générateur, je pense que la documentation en parle suffisamment bien, c'est que pour cet exercice, ça ne s'y prête pas forcément. Cependant je n'ai fais aucun test pour y voir un quelconque goulot d'étranglement, juste vérifier que le résultat correspondait au résultat du PO.
Perso, si j'ai ce besoin pour moi, j'aurai vérifier, mais là, ce n'est pas à moi de le faire, c'est au PO. Il n'a déjà pas cherché dans les pléthores de solutions à son problème, alors j'imagine que mesurer et chercher l'algorithme le plus efficace est bien le dernier de ses soucis.
J'en rajoute un autre,
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
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")
Bon je suis à 0,3 s
- Edité par fred1599 1 février 2023 à 16:04:58
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Alors, si tu en as la possibilité, je veux bien que tu m'expliques par quel procédé tu dérécursifies la fonction rec_list ci-dessus.
Si tu arrives à expliciter les raisonnements formels qui prouvent que ta fonction va marcher, tu devrait y arriver.
Voila, en gros, la manière de s'y prendre avec les paramètres tampons. C'est du markdown et vu le nombre de personnes qui ont envie de lire ça, j'ai la flemme de faire mieux :-)
# Enoncé
On veut écrire une fonction qui "applatit" une liste
(les notations sont évidentes, '+' est la concaténation des listes, associative avec un élément neutre, un monoïde quoi) ce qui suffit pour définir complètement la fonction flatten.
d'où il s'en suit qu'on peut écrire `aux` sous la forme
~~~ aux(liste1, liste2) = si liste2 = [] alors liste1 si liste2 = [premier] + suite alors si premier est un atome alors aux(liste1 + [premier], suite) sinon aux(liste1, premier + suite) ~~~
Exercice : Si vous voulez un argument de terminaison, considérez
-taille(atome) = 1
- taille(liste) = somme des tailles des éléments + 1
et comme les appels récursifs sont terminaux, aux se "dérécursifie" sous forme de boucle, en revenant à un paradigme impératif
~~~ tant que liste2 != [] : liste2 se décompose en [premier] + suite si premier est un atome alors liste1 = liste + [premier], liste2 = suite sinon liste2 = premier + suite retourner liste1 ~~~
et flatten s'obtient à partir de aux, en traitant
- d'un côté le cas des données qui sont des atomes - de l'autre le cas des listes en appelant aux([], liste)
- Edité par michelbillaud 1 février 2023 à 16:19:33
Pour ma part, le python que j'aime est explicite, aéré, naturel, compréhensible.
Cette obsession de la performance dénature à mon sens python. Un beau code , c'est notamment un code qui répond au PEP et au zen de python.
Et puis on travaille pas sur des machines 8bits, dont on doit optimiser toutes les ressources.
Je n'adhère pas à cette démarche. Je la pense délétère sur un forum fréquenté souvent par de jeunes débutants.
Lorsque je lis https://openclassrooms.com/forum/sujet/gerer-le-s-du-pluriel , argumenter sur le temps d'exécution d'un truc qui n'est appelé que toutes les secondes, je me dis que c'est de la ....
Bref , sans vouloir offenser personne, j'avais quand même envie de donner mon avis.
Après ce type d'échange peut être intéressant pour une demande d'optimisation de la vitesse d'un code, mais en dehors ce cadre, cette grille de lecture me semble complètement inapproprié
J'aime les bananes, le python, le gnu, le pingouin.
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
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")
Bon je suis à 0,3 s
Bien trouvé, 5 fois plus rapide, faudra que je médite sur ce code.
michelbillaud a écrit:
Alors, si tu en as la possibilité, je veux bien que tu m'expliques par quel procédé tu dérécursifies la fonction rec_list ci-dessus.
Si tu arrives à expliciter les raisonnements formels qui prouvent que ta fonction va marcher, tu devrait y arriver.
OK, merci, je vais prendre le temps de regarder ça. Tu n'aurais pas le code Python auquel conduit ta procédure ? Ne me dis pas que c'est le code que tu as posté en premier !
Pourrait-on automatiser la dérécursification ? Il se dit que certains algos sont très difficiles à dérécursifier, typiquement le tri fusion je crois.
Sinon, tu as une référence pour découvrir et approfondir ce type de question de dérécursification (manuel, site web, vidéos) ? et qui ne m'oblige pas à apprendre un nouveau langage !
> Tu n'aurais pas le code Python auquel conduit ta procédure ? Ne me dis pas que c'est le code que tu as posté en premier !
J'ai pas besoin de le dire.
après, si on part de
aux(liste1, liste2) = flatten(liste1) + liste 2
et en prenant les listes dans le sens liste = début + [dernier]
on tombe sur l'autre version.
(Une grande partie de la programmation, c'est des raisonnements algébriques, une fois qu'on a le bon cadre pour exprimer ce qu'on fait. Dommage que beaucoup s'imaginent que la programmation et les maths n'aient aucun rapport).
> Sinon, tu as une référence pour découvrir et approfondir ce type de question de dérécursification (manuel, site web, vidéos) ? et qui ne m'oblige pas à apprendre un nouveau langage !
La truc général pour passer d'une fonction f(x,y, z...) exprimée de façon récursive terminale à une boucle, c'est tout bêtement de remplacer les appels terminaux f(e1, e2, ...) par des affectations x = e1, y = e2, etc et de revenir au début. Le test des cas de base devient la condition d'arrêt de la boucle.
Il y avait eu beaucoup de travail de fait, à ce sujet, dans les implémentations de Lisp, à l'époque de quand j'étais un peu plus jeune et que la plupart de ceux qui lisent étaient pas nés (comme les poissons).
- Edité par michelbillaud 1 février 2023 à 17:13:46
Bon je me suis amusé à créer mon module Python en C avec cython
# function.pyx
cdef public void flatten_list(list l, list res):
for item in l:
if type(item) == list:
flatten_list(item, res)
else:
res.append(item)
def flatten(list l):
cdef list res = []
flatten_list(l, res)
return res
# setup.py
from distutils.core import setup
from Cython.Build import cythonize
setup(
name='flatten_list',
ext_modules=cythonize("function.pyx"),
)
python setup.py build_ext --inplace
Déplacer votre fichier function[...].so dans build/lib/ dans le répertoire où se trouve le fichier python qui exécutera la fonction de test et modifier pour l'appeler function.so
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
- Edité par fred1599 1 février 2023 à 19:02:40
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard) La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Bon je me suis amusé à cérer mon module Python en C avec cython
# function.pyx
cdef public void flatten_list(list l, list res):
for item in l:
if type(item) == list:
flatten_list(item, res)
else:
res.append(item)
def flatten(list l):
cdef list res = []
flatten_list(l, res)
return res
# setup.py
from distutils.core import setup
from Cython.Build import cythonize
setup(
name='flatten_list',
ext_modules=cythonize("function.pyx"),
)
python setup.py build_ext --inplace
Déplacer votre fichier function[...].so dans build/lib/ dans le répertoire où se trouve le fichier python qui exécutera la fonction de test et modifier pour l'appeler function.so
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
- Edité par fred1599 il y a 5 minutes
Merci de ce code. Je viens de le tester mais sur le jeu de données de plf qui est plus substanciel. J'obtiens un ratio de 8,5. On pourrait s'attendre à mieux, il y a 100 millions d'entiers à extraire et le code C met 1,6 s ce qui est loin d'être négligeable pour du C, ça devrait être fait beaucoup plus rapidement. Ton code Cython en fait n'utilise aucun type autre que du typage Python donc il reste bloqué dans l'API C de Python. D'ailleurs, tu peux le voir en activant les annotations annotate=True dans le setup.py.
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Python c'est bon, mangez-en.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.
Le Tout est souvent plus grand que la somme de ses parties.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
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.
Python c'est bon, mangez-en.
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Découverte Python Doc Tkinter Les chaînes de caractères
Découverte Python Doc Tkinter Les chaînes de caractères
Découverte Python Doc Tkinter Les chaînes de caractères
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Découverte Python Doc Tkinter Les chaînes de caractères
Celui qui trouve sans chercher est celui qui a longtemps cherché sans trouver.(Bachelard)
La connaissance s'acquiert par l'expérience, tout le reste n'est que de l'information.(Einstein)
Découverte Python Doc Tkinter Les chaînes de caractères