Tri Externe - Algorithme de Tri de Fichiers - PDF

TRI EXTERNE Trier un fichier de N blocs M buffers en MC 2 étapes : - Fragmentation (une seule phase)- - MultiFusions (plusieurs phases) - Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 1 ...

TRI EXTERNE Trier un fichier de N blocs M buffers en MC 2 étapes : - Fragmentation (une seule phase)- - MultiFusions (plusieurs phases) - Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 1  Fragmentation Fichier initial (non trié) de taille N blocs 1 2 3 … M M+1 M+2 …. …. … …. …. …. ….. …. … N-2 N-1 N Coût de la fragmentation : N lectures M buffers en MC N écritures Algo de tri interne 1 2 3 ….. M 1 2 3 … M 1 2 3 … M 1 2 3 … M 1 2 3 … M [N/M] Fragments triés, de taille M blocs chacun Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 2  Après la fragmentation, on obtient [N/M] Fragments triés 1 2 3..… M Frag_1 C’est le début de la 2e étape : Frag_2 plusieurs phases de Multi-Fusion Frag_3 seront nécessaires pour arriver à un seul fragment trié (Le résultat final du tri) Frag_[N/M] Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 3  Multi-Fusion : Phase 1 anciens fragments nouveaux fragments M-1 buf d'entrées 1 buf de Fusion du 1er gr de M-1 Fragments 1er sortie groupe MC 2eme groupe 3eme groupe Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 4  Multi-Fusion : Phase 1 anciens fragments nouveaux fragments Fusion du 1er gr de M-1 Fragments 1er groupe M-1 buf d'entrées 1 buf de Fusion du 2e gr de M-1 Fragments 2eme sortie groupe MC 3eme groupe Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 5  Multi-Fusion : Phase 1 anciens fragments nouveaux fragments Fusion du 1er gr de M-1 Fragments 1er groupe Fusion du 2e gr de M-1 Fragments 2eme groupe M-1 buf d'entrées 3eme 1 buf de Fusion du 3e gr de M-1 Fragments groupe sortie MC Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 6  Multi-Fusion : Phase 2 anciens fragments nouveaux fragments Fragment [N/M]+1 M-1 buf d'entrées Fragment [N/M]+2 1 buf de sortie MC Fragment [N/M]+3 Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 7  Première étape du Tri = 1 phase de fragmentation Deuxième étape du Tri = k phases de multi-fusion phase_1 phase_2 phase_3 Fichier en entrée de Fichier en sortie N blocs (trié) de N blocs A chaque phase le nb de fragments est divisé par M-1 Nb de phases = logM-1[N/M] Fragmentation Multi-Fusion chaque phase, coûte 2N accès Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 8 Coût total du Tri Externe = 2N ( 1 + logM-1[N/M] ) → O (N log N) Fragmentation Multi-fusion (2N accès) ( 2N * logM-1[N/M] accès) phase_1 phase_2... phase_k ( k = logM-1[N/M] ) Fichier en Fichier en sortie entrée de (trié) de N blocs N blocs Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 9  Fusion multiple de k fichiers triés en utilisant k+1 buffers en MC NumBloc k+1 buffers en MC e = 10 … … … 120 50 10 imin = 1 F 165 70 15 buf 200 25 10 NumEnr 105 15 N1...... 3 2 1 25 buf 100 NumEnr F … … … 592 455 100 657 500 110 110 691 588 450 450 N2...... 3 2 1 buf 20 NumEnr 30 F 590 240 20 90 1 fichier en sortie … … … 592 465 30 816 534 90 … NumBloc[k+1] N3...... 3 2 1 buf[k] 105 NumEnr[k] 373 NumBloc 420 k fichiers … … … … en entrée buf[k+1] 10 NumEnr[k+1] 1 2 3 F[k+1] F[k] … … … 490 430 105 522 465 373 700 483 420 Nk...... 3 2 1 NumBloc[k] Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 10  Fusion multiple de k fichiers triés en utilisant k+1 buffers en MC NumBloc k+1 buffers en MC e = 15 … … … 120 50 10 imin = 1 F 165 70 15 buf 200 105 25 10 15 NumEnr N1...... 3 2 1 25 buf 100 NumEnr F … … … 592 455 100 657 500 110 110 691 588 450 450 N2...... 3 2 1 buf 20 NumEnr 30 F 590 240 20 90 1 fichier en sortie … … … 592 465 30 816 534 90 … NumBloc[k+1] N3...... 3 2 1 buf[k] 105 NumEnr[k] 373 NumBloc 420 k fichiers … … … … en entrée buf[k+1] 10 15 1 2 3 NumEnr[k+1] F[k+1] F[k] … … … 490 430 105 522 465 373 700 483 420 Nk...... 3 2 1 NumBloc[k] Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 11  Fusion multiple de k fichiers triés en utilisant k+1 buffers en MC NumBloc k+1 buffers en MC e = 20 … … … 120 50 10 imin = 3 F 165 70 15 buf 200 105 25 10 15 N1...... 3 2 1 25 NumEnr buf 100 NumEnr F … … … 592 455 100 657 500 110 110 691 588 450 450 N2...... 3 2 1 buf 20 NumEnr 30 F 590 240 20 90 1 fichier en sortie … … … 592 465 30 816 534 90 … NumBloc[k+1] N3...... 3 2 1 buf[k] 105 NumEnr[k] 373 10 NumBloc 420 k fichiers 15 … … … … 20 en entrée buf[k+1] 10 15 1 2 3 20 F[k+1] NumEnr[k+1] F[k] … … … 490 430 105 522 465 373 700 483 420 Nk...... 3 2 1 NumBloc[k] Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 12  Fusion multiple de k fichiers triés en utilisant k+1 buffers en MC NumBloc k+1 buffers en MC e = 25 … … … 120 50 10 imin = 1 F 165 70 15 buf 200 105 25 10 15 N1...... 3 2 1 25 NumEnr buf 100 NumEnr F … … … 592 455 100 657 500 110 110 691 588 450 450 N2...... 3 2 1 buf 20 30 NumEnr F 590 240 20 90 1 fichier en sortie … … … 592 465 30 816 534 90 … NumBloc[k+1] N3...... 3 2 1 buf[k] 105 NumEnr[k] 373 10 NumBloc 420 k fichiers 15 … … … … 20 en entrée buf[k+1] 25 NumEnr[k+1] 1 2 3 F[k+1] F[k] … … … 490 430 105 522 465 373 700 483 420 Nk...... 3 2 1 NumBloc[k] Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 13  Fusion multiple de k fichiers triés en utilisant k+1 buffers en MC NumBloc k+1 buffers en MC e = 30 … … … 120 50 10 imin = 1 F 165 70 15 buf 200 105 25 50 NumEnr 70 N1...... 3 2 1 105 buf 100 NumEnr F … … … 592 455 100 657 500 110 110 691 588 450 450 N2...... 3 2 1 buf 20 30 NumEnr F 590 240 20 90 1 fichier en sortie … … … 592 465 30 816 534 90 … NumBloc[k+1] N3...... 3 2 1 buf[k] 105 NumEnr[k] 373 10 NumBloc 420 k fichiers 15 … … … … 20 en entrée buf[k+1] 25 30 1 2 3 NumEnr[k+1] F[k+1] F[k] … … … 490 430 105 522 465 373 700 483 420 Nk...... 3 2 1 NumBloc[k] Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 14  Fusion multiple de k fichiers triés en utilisant k+1 buffers en MC NumBloc k+1 buffers en MC e = 110 … … … 120 50 10 imin = 2 F 165 70 15 buf 200 25 120 NumEnr 105 165 N1...... 3 2 1 200 buf 100 F … … … 592 455 100 657 500 110 110 NumEnr 691 588 450 450 N2...... 3 2 1 buf 240 NumEnr 465 F 590 240 20 534 1 fichier en sortie … … … 592 465 30 816 534 90 … NumBloc[k+1] N3...... 3 2 1 F[k+1] buf[k] 105 373 NumEnr[k] 25 70 NumBloc 10 420 k fichiers 15 30 90 … … … … 20 50 105 en entrée buf[k+1] 100 105 1 2 3 NumEnr[k+1] F[k] … … … 490 430 105 522 465 373 700 483 420 Nk...... 3 2 1 NumBloc[k] Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 15 Tri_Externe En entrée : E un fichier non trié formé par N blocs En sortie : S un fichier trié formé par N blocs i = 1 ; j = 1 ; k = 1 ; CreerFile (FIFO ) TQ (i ≤ N ) SI ( j ≤ M ) LireBloc( E, i, buf[ i ] ) ; i++ ; j++ // Remplir les M buffers à partir du fichier E SINON fragk = Tri_interne( buf, 1, M ) // tri en MC du contenu de buf[ 1.. M ] Enfiler( fragk , FIFO ) ; k++ ; j = 1 // et écriture en MS du résultat : fragk FSI FTQ // traitement du dernier fragment fragk = Tri_interne( buf, 1, j-1 ) // tri en MC du contenu de buf[ 1.. j-1 ] Enfiler( fragk , FIFO ) // et écriture en MS du résultat : fragk TQ ( la file FIFO contient plus d’un élément ) // retirer de la file les M-1 premiers fragments (ou moins, s’il reste moins de M fragments) Defiler_groupe( M-1, r1, r2, … rj , FIFO ) // r1, r2, … rj : les j fragments défilés k++ fragk = FusionMultiple( r1, r2, … rj ) // Fusion du groupe de fragments défilés Enfiler( fragk, FIFO ) // et Enfiler le résultat fragk FTQ Defiler( S , FIFO ) Hidouci W.K. / Algo. Tri Externe / Opérations de haut niveau / SFSD / ESI 16