Optimisation de requêtes - exercice de tri externe

Cette formation présente les fondements des bases de données relationnelles et enseigne l’écriture de requêtes SQL.

Modérateurs : Équipe sillages.info, Benjamin NGUYEN

COLELLA
Messages : 9
Enregistré le : jeu. 9 août 2018 07:07

Optimisation de requêtes - exercice de tri externe

Messagepar COLELLA » lun. 20 août 2018 13:20

Bonjour,

Je n'ai pas compris dans la séquence 5 - Optimisation de requêtes, concernant l'exercice de tri externe :

"Supposons qu'on souhaite trier un fichier de 75 000 pages de 4 Ko (soit une taille totale de 307 Mo). Donnez le nombre de lectures et d'écritures (en terme de pages de 4Ko) lorsqu'on dispose d'une mémoire de 307Mo. Idem lorsqu'on dispose d'une mémoire de 2 Mo, puis de 1Mo."

RAM = 307Mo
Il faut lire l'ensemble des 75 000 pages, puis trier le tout en mémoire (puisqu'on a suffisamment de place), puis écrire le résultat (75 000 pages).

Bilan : 75 000 lectures, et 75 000 écritures.

J'ai compris, OK.

RAM = 2Mo
1-on lit et on trie les 75 000 pages.

2-on effectue un tri fusion, sachant qu'on peut garder en mémoire 2048/4 =512 pages, et donc on peut les fusionner 256 par 256. Le nombre de paquets à fusionner au premier niveau est donc 75 000 / 256 = 293, et le nombre de niveaux est donc l'arrondi à l'entier supérieur de log2(293) soit 9. On lira et écrire donc 9 fois l'ensemble de données, en plus de la lecture initiale.

Le coût total est donc de 750 000 lectures et 750 000 écritures !

Je n'ai pas compris comment on obtient 2048.
Je n'ai pas compris quelle opération était effectuée : log(2) ou log (293) ou log(2)*293 ? Dans tous les cas, je ne trouve pas 9.


RAM = 1Mo
On fait le même calcul sachant qu'on peut garder en mémoire 256 pages, donc on ne peut les fusionner que 128 par 128 et donc qu'on a 586 paquets initiaux, et qu'on devra donc effectuer 10 rounds.

Le coût total est donc de 825 000 lectures et 825 000 écritures.

Je ne comprends pas comment l'on obtient 256 pages, ni 586, ni 825 000..

Je vous remercie par avance pour votre aide et reste à votre écoute,

Anna C.

Astrid Allemandou
Messages : 12
Enregistré le : sam. 22 déc. 2018 15:21

Re: Optimisation de requêtes - exercice de tri externe

Messagepar Astrid Allemandou » mer. 2 janv. 2019 16:56

1 Kb (kilobyte) = 1000 b
mais 1 Ko = 1024 octets !
Pareil pour passer des kilo aux mega.
Donc 2 Mo = 2 * 1024 Ko = 2048 Ko.

On utilise ici le logarithme binaire (log_2). On écrit : log_2(293) (le 2 est en indice). Pour refaire ce calcul avec une calculatrice d'ordinateur, il faut faire log(293) divisé par log(2). Il faut taper : 293, log, ÷, 2, log, =. On obtient environ 8,19.

Une page pèse 4 Ko. Pour savoir combien de pages on peut avoir en mémoire, on divise donc la taille de la mémoire par 4. Et pour pouvoir en fusionner 2, il faut avoir les deux en mémoire en même temps, donc on va avoir des paquets qui font la moitié du résultat précédent.

Si on a des paquets de 128 pages, et qu'on a 75 000 pages au total, on a donc 75 000/128 ~ 586 paquets.

Le "niveau de fusion" est défini par log_2(N) où N est le nombre de paquets, donc ici log_2(586) qu'on arrondit à l'entier supérieur : 10.

Enfin, d'après le cours, le coût total de ce tri est le niveau de fusion multiplié par le coût d'une lecture écriture (+ la lecture initiale) : 10 * 75000 + 75000 = 825000.

Mais je n'aurais jamais deviné ceci seule sans la réponse ! Ces exercices mériteraient un bon paquet d'indications, pour ceux qui sont novices en informatique.


Retourner vers « Bases de données relationnelles »

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 1 invité