hm, pour la fusion, tu vas avoir en effet besoin de deux compteurs. mais faire deux boucle for n'est pas une bonne idée.
tu dois avec une boucle tant que tu as des éléments à ajouter. à chaque tour de boucle tu ajoute soit un élement à la liste final; et tu augmente le compteur de la liste dont viens l'élément que tu viens d'ajouter à la liste final. si les deux listes de bases sont triés; la liste final l'est aussi. tu programme un tri fusion ?
def tris(tab):
for i in range(len(tab)):
for j in range(len(tab) - 1):
if tab[ j + 1 ] < tab[ j ]:
unautre = tab[ j ]
tab[ j ] = tab[ j + 1 ]
tab[ j + 1 ] = unautre
return tab
def fusion(lstA, lstB):
lstC = []
for i in lstA:
lstC.append(i)
for i in lstB:
lstC.append(i)
return tris(lstC) #retourne par la fonction tris
tableau1 = [4,6,8,2]
tableau2 = [3,1,5,7]
print(fusion(tableau1, tableau2))
l'approche classique en algo est peut être plus simple sous forme récursive. L'idée est :
si l'une des deux listes est vide alors on renvoie l'autre ; le cas de deux listes vides n'est pas problématique car le résultat de la fusion est une liste vide
sinon on a deux listes triées qui ont chacune au moins un élément : la tête de liste la plus petite des deux têtes est transférée à la liste résultat, la queue du résultat étant la fusion du reste des listes
Cela pourrait en gros donner comme implémentation :
Si tu veux simplement concaténer tes deux listes puis les trier, la réponse est :
sorted( liste1 + liste2 )
Si tu veux implémenter un tri fusion, alors il faut que tes deux listes d'origine soient triées. Le tri fusion n'est pas l'algo le plus rapide pour trier des petites quantités de données, mais il est très utile pour trier des quantités de données en utilisant peu de RAM. L'algo est le suivant :
- Si on utilise le tri fusion, c'est que les données ne tiennent pas en RAM, donc on part d'un fichier qui contient les données à trier.
- En lisant le fichier, on découpe les données en blocs d'une taille raisonnable suivant la quantité de RAM disponible. On trie chaque bloc avec un algo adapté genre qsort, ou en utilisant la fonction de tri de python.
- On écrit chaque bloc dans un fichier temporaire.
- Ensuite on fait un tri fusion pour regrouper les blocs 2 par 2 en blocs triés 2x plus gros.
- On continue jusqu'à avoir tout regroupé en un seul gros fichier trié.
Voici un algo du tri fusion à l'arrache (non garanti) qui prend 2 sources de données (ici des itérateurs) et retourne le résultat sous forme d'un générateur.
def mergesort( A, B ):
A = iter(A)
B = iter(B)
# parcourt les deux itérateurs sources simultanément
try:
b = B.next()
for a in A:
if a <= b:
yield a
else:
while b <= a:
yield b
b = B.next()
else:
# le for s'est terminé donc A est vide donc on finit b
for b in B:
yield b
except StopIteration:
# b.next() a lancé l'exception donc B est vide donc on finit A
for a in A:
yield a
print list( mergesort( (1,2,3), () ))
print list( mergesort( (1,2,3), (4,5) ))
print list( mergesort( (4,5),(1,2,3) ))
print list( mergesort( (4,5,6),(1,2,3) ))
print list( mergesort( (1,3,5),(1,2,3) ))
Vois-tu un moyen de le faire encore plus python3esque ?
def mergesort( A, B ):
A = iter(A)
B = iter(B)
# parcourt les deux itérateurs sources simultanément
try:
b = next(B)
except StopIteration:
yield from A
return
try:
for a in A:
if a <= b:
yield a
else:
while b <= a:
yield b
b = next(B)
else:
# le for s'est terminé donc A est vide donc on finit b
yield b
yield from B
except StopIteration:
# b.next() a lancé l'exception donc B est vide donc on finit A
yield a
yield from A
Est ce que tu peux expliquer le code ? sa me semble très compliqué ? Notamment, pourquoi est ce que tu ne fais pas a=next(A) après le yield a alors que tu le fais pour B ?
Parce que j'ai mis un "for" sur A, donc chaque tour du "for" ramène le prochain élément de A...
Le principe du tri fusion est de parcourir les deux listes en même temps et de prendre le bon élément dans chaque liste, pour avoir un résultat dans l'ordre. La difficulté ici est que ce serait plus pratique de pouvoir regarder le prochain élément avant de faire next()...
Si tu veux le faire avec des listes et des indices, alors ça devient plus simple, mais ce n'est plus dans l'esprit "mergesort" qui consiste à pouvoir trier des données de grande taille :
def mergesort( A, B ):
a = b = 0
while True:
if a >= len(A):
yield from B[b:]
return
if b >= len(B):
yield from A[a:]
return
if A[a] <= B[b]:
yield A[a]
a += 1
else:
yield B[b]
b += 1
...mais le truc le plus clair serait :
from collections import deque
def mergesort( A, B ):
A = deque(A)
B = deque(B)
try:
while True:
if A[0] <= B[0]:
yield A.popleft()
else:
yield B.popleft()
# quand une deque est vide :
except IndexError:
if A:
yield from A
else:
yield from B
(le cheat mode, c'est qu'on peut regarder l'élément qui va sortir de la queue sans le sortir)
- Edité par Lord Casque Noir 29 décembre 2016 à 18:58:03
def mergesort( A, B ):
Al = iter(A)
Bl = iter(B)
a = next(Al)
b = next(Bl)
while(1):
if a < b :
yield a
try :
a = next(Al)
except StopIteration:
yield b
for b in Bl:
yield b
return
else :
yield b
try:
b = next(Bl)
except StopIteration:
yield a
for a in Al:
yield a
return
Ca ne marche pas si l'une des liste est vide à la base. mais je préfère traiter A et B de façon symétrique. ( c'est pour sa que j'aurai tendance aussi à préférer ton dernier code )
Tout d'abord je tiens à vous remercier pour votre aide.
@nolimitech : merci c'était exactement ça que je voulais faire !
@PicoDev & Lord Casque Noir : merci pour vos explications, mais je suis encore trop débutant je vais me contenter de ce que nolimitech nous a partagé, je trouve son code super facile !
@edouard22: j'aimerais bien savoir refaire le même exercice avec une boucle while , cette fois-ci et non une for j'ai essayé j'y suis vraiment presque...Cependant il manque certains chiffres...
def tris(tab):
for i in range(len(tab)):
for j in range(len(tab) - 1):
if tab[ j + 1 ] < tab[ j ]:
unautre = tab[ j ]
tab[ j ] = tab[ j + 1 ]
tab[ j + 1 ] = unautre
return tab
def fusion():
tableau1 = [1,3,5,2]
tableau2 = [4,6,8,7]
tableau3 = []
i = 0
j = 0
while i < (len(tableau1)) and j < (len(tableau2)):
if tableau1[i] < tableau2[j]:
tableau3.append(tableau1[i])
i = i + 1
else:
tableau3.append(tableau2[j])
j = j + 1
if j == (len(tableau2)):
print(tableau3)
return tris(tableau3)
print(fusion())
En faites tu as deux choix : sois tu tri les deux tableaux, puis tu les fusionnes en conservant le tri. soit tu les fusionne puis tu tri. j'ai tendance à préférer la premiere solution : il est beaucoup plus simple de trier des tableau de petite taille puis de les fusionner que de trier un tableau de grande taille après les voir fusionner.
Ta fonction de fusion est presque bonne, il ne manque qu'une chose. ajouter les éléments restant :
def fusion(A,B):
C = []
i = 0
j = 0
while i < len(A) and j < len(B) :
if A[i] < B[j]:
C.append(A[i])
i = i + 1
else:
C.append(B[j])
j = j + 1
# Un des tableau est vide
while i < len(A) : # si A est vide, cette boucle n'est pas exécuté.
C.append(A[i])
i = i + 1
while j < len(B) : # si B est vide, cette boucle n'est pas exécuté.
C.append(B[j])
j = j + 1
return C
et pour le tri, je te propose :
def tri_fusion(A):
if len(A)<=1 :
return A
if len(A)==2 :
if (A[0]< A[1] ):
return A
return [A[1],A[0]]
return fusion( tri_fusion(A[:len(A)//2]) , tri_fusion(A[len(A)//2 : ]) )
def tri_fusion_2(A,B):
if A==[]:
return B
if B==[]:
return A
return fusion( tri_fusion(A) , tri_fusion(B) )
ps : ta biographie est intéressante Lord casque Noir
Avant d'aller plus loin, si c'est un exercice, c'est super.
Sauf que si vous faites cela, parce que vous saviez pas qu'il existait des fonctions déjà fait, pour ce genre de chose, c'est une autre paire de manche.
lstA = [2,4,6,8]
lstB = [1,3,5,7]
lstC = lstA + lstB #Vous venez de fusionner deux listes
lstC = sorted(lstC) #Vous venez de triez la liste (si ce sont des chiffres)
Avant d'aller plus loin, si c'est un exercice, c'est super.
Sauf que si vous faites cela, parce que vous saviez pas qu'il existait des fonctions déjà fait, pour ce genre de chose, c'est une autre paire de manche.
lstA = [2,4,6,8]
lstB = [1,3,5,7]
lstC = lstA + lstB #Vous venez de fusionner deux listes
lstC = sorted(lstC) #Vous venez de triez la liste (si ce sont des chiffres)
Sauf que tu ne prends pas du tout en compte la particularité de tes donnés de base : ils sont déjà triés ! Lorsque les donnés que tu manipule sont remarquable : elle sont trié, il sagit d'une matrice diagonale/ triangulaire; ton algorithme doit en tenir compte afin d'être le plus optimal possible.
Sorted c'est bien mais tu ne sais pas quel algorithme est utilisé, ni si il vas pouvoir utiliser la propriété remarquable de tes donnés. Par exemple : utiliser un quick sort sur des donnés trié est très mauvais. Alors pourquoi ne pas les fusionner en gardant le trie ?
Après effectivement, heapq.merge est meilleur (mais je ne connaissais pas )
C'est donc l'heure de faire un benchmark (en plus, il restait des bugs dans mon premier mergesort, LOL) :
#! /bin/env python3
# -*- coding: utf-8 -*-
import time
def mergesort_iter( A, B ):
A = iter(A)
B = iter(B)
# parcourt les deux itérateurs sources simultanément
try:
a = next(A)
except StopIteration:
yield from B
return
try:
b = next(B)
except StopIteration:
yield a
yield from A
return
while True:
if a <= b:
try:
yield a
a = next(A)
except StopIteration:
yield b
yield from B
return
else:
try:
yield b
b = next(B)
except StopIteration:
yield a
yield from A
return
def mergesort_list( A, B ):
a = b = 0
while True:
if a >= len(A):
yield from B[b:]
return
if b >= len(B):
yield from A[a:]
return
if A[a] <= B[b]:
yield A[a]
a += 1
else:
yield B[b]
b += 1
from collections import deque
def mergesort_deque( A, B ):
A = deque(A)
B = deque(B)
try:
while True:
if A[0] <= B[0]:
yield A.popleft()
else:
yield B.popleft()
# quand une deque est vide :
except IndexError:
if A:
yield from A
else:
yield from B
import heapq
def mergesort_heapq( A, B ):
return heapq.merge( A, B )
def mergesort_pysort( A, B ):
return sorted(A+B)
import numpy as np
def bench():
A = B = list( range( 1000000 ))
# cas spécial pour numpy
arr = np.arange(len(A),dtype=np.int32)
t = time.time()
np.sort( np.hstack(( arr,arr )) )
t = time.time()-t
print( "%2.03f %s" % (t,"numpy"))
for f in mergesort_pysort, mergesort_iter, mergesort_deque, mergesort_heapq, mergesort_list, :
t = time.time()
for _ in f(A,B):
pass
t = time.time()-t
print( "%2.03f %s" % (t,f.__name__))
def test_mergesort( A,B ):
A = list(A)
B = list(B)
assert sorted(A) == A
assert sorted(B) == B
test = sorted(A+B)
for f in mergesort_pysort, mergesort_iter, mergesort_deque, mergesort_heapq, mergesort_list:
res = list(f( A, B ))
print( A, B, test, res )
assert test == res
test_mergesort( (1,2,3), () )
test_mergesort( (1,2,3), () )
test_mergesort( (1,2,3), (4,5) )
test_mergesort( (4,5),(1,2,3) )
test_mergesort( (4,5,6),(1,2,3) )
test_mergesort( (1,3,5),(1,2,3) )
test_mergesort( (1,2,3),(1,2,3) )
bench()
Oui c'est l'idée, là il détecte que la liste contient 2 sous-listes triées et donc il fait... une fusion. Donc en fait il ne fait pas grand chose, pour le timsort c'est quasiment le meilleur cas possible !
> Perso, je serais toujours impressionné par les performance de numpy 
Oui c'est l'idée, là il détecte que la liste contient 2 sous-listes triées et donc il fait... une fusion. Donc en fait il ne fait pas grand chose, pour le timsort c'est quasiment le meilleur cas possible !
> Perso, je serais toujours impressionné par les performance de numpy 
N'est-ce pas !
Dailleurs, avec numpy on peut choisir l'algorithme utilisé. Par défaut c'est un quicksort ! Comment peut il être aussi efficace ? j'ai rajouté les test avec le merge sort/ heapsort :
Numpy sait que l'array ne contient que des entiers, alors que le python pur utilise la fonction de comparaison générique qui gère tous les types donc t'as pas mal de temps de perdu à cause de ça. La généricité a un coût...
Faudrait-il encore connaître les contraintes du problème. Car si le problème est plutôt la quantité de RAM que la rapidité, le choix sera différent.
Et sans réelle contrainte, la solution la plus lisible sera préférée. Ainsi la solution de Lord Casque Noir et nolimitech est certainement le meilleur premier choix. sorted(liste1 + liste2)
C'est ce qui donnera le moins de maux de têtes à maintenir dans le futur.
Mon exemple, était simplement, à titre d'information. Bien sûre, qu'il manquait des données.
Combien de fois, j'ai perdu du temps à créer un programme, simplement parce que j'essayais de créer une fonction simple, qui était déjà inclus, dans une des bibliothèques standard .
Merci Dan737 de me comprendre, haha
Merci pour le benchMark Lord Casque Noir.
Trier && Fusionner deux listes
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
entwanne — @entwanne — Un zeste de Python — La POO en Python — Notions de Python avancées — Les secrets d'un code pythonique