Listing du fichier progie8.php
00001 Pour ne pas voir les numéros de ligne, ajoutez &nl=non à la suite du nom du fichier. |
Retour à la page principale de
(gH)
Listing du fichier progie8.php
00001<?php
00002 # # (gH) -_- progie8.php ; TimeStamp (unix) : 16 Février 2015 vers 21:27
00003
00004 error_reporting(E_ALL | E_NOTICE | E_STRICT) ;
00005
00006 include_once("std7.php") ;
00007 include_once("progi.php") ;
00008 include_once("statuno7.php") ;
00009
00010 $R = s_span("R","gbleuf") ;
00011 $numSerie = 8 ;
00012 debutPageExercices($numSerie) ;
00013
00014 ## -------------------------------------------------------------------------------------------
00015
00016 p("texte") ;
00017 echo "" ;
00018 finp() ;
00019
00020 debutSection() ;
00021
00022 $tableauDesRubriques = array() ;
00023 $idr = 0 ;
00024
00025 $idr++; $tableauDesRubriques[$idr] = "Code lisible et debug" ;
00026 $idr++; $tableauDesRubriques[$idr] = "Optimisation" ;
00027 $idr++; $tableauDesRubriques[$idr] = "Vitesses d'exécution" ;
00028 $idr++; $tableauDesRubriques[$idr] = "Positions du maximum et gestion de la mémoire" ;
00029 $idr++; $tableauDesRubriques[$idr] = "Tris et \"big data\"" ;
00030
00031 $tdmCRLM = new tdm($tableauDesRubriques) ;
00032 $tdmCRLM->titre() ;
00033 $tdmCRLM->menu("oui","oui","nou") ;
00034
00035 afficherSolutions($numSerie) ;
00036
00037 finSection() ;
00038
00039 debutSection() ;
00040 $numExo = 0 ;
00041
00042 ## -------------------------------------------------------------------------------------------
00043
00044 $tdmCRLM->afficheRubrique("oui") ; $numExo++ ; # Code lisible et debug
00045
00046 ## -------------------------------------------------------------------------------------------
00047
00048 blockquote() ;
00049
00050 blockquote() ;
00051
00052 p("texte") ;
00053 echo "A-t-on besoin de la fonction ".hrrr("debug")." pour trouver pourquoi le code suivant ne fonctionne pas, \n" ;
00054 echo "sachant qu'on cherche à renvoyer la chaine de caractères passée en paramètre \n" ;
00055 echo "avec la lettre initiale en majuscule et toute le reste en minuscules ? \n" ;
00056 finp() ;
00057
00058 pre_fichier("maju01.r","cadre") ;
00059
00060 finblockquote() ;
00061
00062 solution($numExo,$numSerie) ;
00063
00064 p("texte") ;
00065 echo "Sans doute que non. Ce code est mal écrit. \n" ;
00066 echo "Vu qu'il y a une seule instruction dans le code proposé, \n" ;
00067 echo "".noir("debug()")." ne peut rien pour nous. Démonstration : \n" ;
00068 finp() ;
00069
00070 pre_fichier("maju01.txt","cadre") ;
00071
00072 p("texte") ;
00073 echo "Pour que le déboggage soit efficace, \n" ;
00074 echo "il vaudrait mieux décomposer chacune \n" ;
00075 echo "des actions, avec quelque chose comme \n" ;
00076 finp() ;
00077
00078 pre_fichier("maju02.r","cadre") ;
00079
00080 p("texte") ;
00081 echo "pour se rendre compte que les indices sont faux. \n" ;
00082 echo "Avec le nouveau code proposé, on peut tester chaque appel de fonction séparément \n" ;
00083 echo "et en déduire que la variable nommée ".noir("initiale")." ne contient pas la bonne valeur, en \n" ;
00084 echo "utilisant cette fois ".noir("debug()").". On peut alors corriger les indices pour ".noir("initiale")." \n" ;
00085 echo "et pour ".noir("resteDeChaine")." qui étaient faux (mais qui ne généraient pas d'erreur) : \n" ;
00086 finp() ;
00087
00088 pre_fichier("maju03.r","cadre") ;
00089
00090 finsolution() ;
00091
00092 finblockquote() ;
00093
00094 ## -------------------------------------------------------------------------------------------
00095
00096 $tdmCRLM->afficheRubrique("oui") ; $numExo++ ; # Optimisation
00097
00098 ## -------------------------------------------------------------------------------------------
00099
00100 blockquote() ;
00101
00102 blockquote() ;
00103
00104 p("texte") ;
00105 echo "On dispose d'une fonction mathématique ".noir("f")." et on voudrait calculer sa valeur \n" ;
00106 echo "en ".noir("n")." points répartis uniformément sur l'intervalle ".noir("[a,b]")." à l'aide d'une boucle. \n" ;
00107 echo "On propose la formule suivante pour \n" ;
00108 echo "calculer la position de chacun des points ".noir("x".sub("i")).", pour ".noir("i")." de 1 à ".noir("n").", " ;
00109 echo " sachant que ".noir("x".sub("1"))."=".noir("a")." et ".noir("x".sub("n"))."=".noir("b")." : \n" ;
00110 finp() ;
00111
00112 #%
00113 #$$x_i = a + (b-a)\times \frac{(i-1)}{(n-1)}$$
00114 #%
00115
00116 $img = "formule.png" ;
00117 p() ;
00118 nbsp(20) ;
00119 echo href($img,img($img,"",300)) ;
00120 finp() ;
00121
00122 p("texte") ;
00123 echo "On veut par exemple tester ce calcul avec ".noir("f(x)=x+1")." sur l'intervalle ".noir("[0,1]")." \n" ;
00124 echo "avec ".noir("n=100")." points. \n" ;
00125 finp() ;
00126
00127 p("texte") ;
00128 echo "Quel serait le code optimisé pour cette boucle ? \n" ;
00129 finp() ;
00130
00131 p("texte") ;
00132 echo "Peut-on effectuer le calcul sans boucle ? \n" ;
00133 finp() ;
00134
00135 finblockquote() ;
00136
00137 solution($numExo,$numSerie) ;
00138
00139 p("texte") ;
00140 echo "La formule fournie pour calculer chacun des ".noir("x".sub("i"))." est tout à fait correcte mathématiquement. \n" ;
00141 echo "Sa programmation naïve ne pose aucun problème : \n" ;
00142 finp() ;
00143
00144 pre_fichier("xi01.r","cadre") ;
00145
00146 p("texte") ;
00147 echo "Une première optimisation de la boucle consiste à sortir les \"constantes\" de la boucle \n" ;
00148 echo "et à initialiser le vecteur de sortie, soit le code : \n" ;
00149 finp() ;
00150
00151 pre_fichier("xi02.r","cadre") ;
00152
00153 p("texte") ;
00154 echo "Une deuxième optimisation consiste à remarquer que les ".noir("x".sub("i"))." sont en progression arithmétique, \n" ;
00155 echo "donc il suffit de rajouter le pas ".noir("h")." de la progression pour passer d'un point à l'autre : \n" ;
00156 finp() ;
00157
00158 pre_fichier("xi03.r","cadre") ;
00159
00160 p("texte") ;
00161 echo "Bien sûr le calcul vectoriel permet de se passer de boucle : \n" ;
00162 finp() ;
00163
00164 pre_fichier("xi04.r","cadre") ;
00165
00166 p("texte") ;
00167 echo "Et enfin, on peut se demander si la fonction ".hrrr("seq")." ne pourrait pas suffire : \n" ;
00168 finp() ;
00169
00170 pre_fichier("xi05.r","cadre") ;
00171
00172 p("texte") ;
00173 echo "Le jeu en vaut-il la chandelle ? Vérifions-le avec la fonction ".noir("microbenchmark()")." : \n" ;
00174 finp() ;
00175
00176 pre_fichier("xiperf.txt","cadre") ;
00177
00178 p("texte") ;
00179 echo "Le résultat est sans appel : la solution 4, basée sur ".noir("1:n")." est de loin la plus performante, \n" ;
00180 echo "puisqu'elle est près de 40 fois plus rapide que la solution naïve, en moyenne comme en médiane. \n" ;
00181 echo "La solution 5 qui utilise la fonction ".noir("seq()")." \n" ;
00182 echo "n'est sans doute pas adaptée ici, même si elle est assez rapide. \n" ;
00183 finp() ;
00184
00185 p("texte") ;
00186 echo "Peut-on encore optimiser ? Oui, sans doute, mais à condition de tester des cas particuliers. \n" ;
00187 echo "Par exemple, on peut remarquer que si ".noir("a")." est égal à 0 alors il n'y pas d'addition à faire. \n" ;
00188 echo "De même, si ".noir("f")." est une fonction constante, on n'a pas besoin de calculer les ".noir("x".sub("i"))." \n" ;
00189 finp() ;
00190
00191 p("texte") ;
00192 echo "Au passage, vous pourriez vous demander pourquoi nous n'avons pas mis le calcul des ".noir("f(x".sub("i").")")." dans \n" ;
00193 echo "les fonctions. La réponse est simple : ce qu'on doit comparer est la génération des ".noir("x".sub("i")).". \n" ;
00194 echo "Après avoir vérifié que les fonctions renvoient les mêmes \n" ;
00195 echo "vecteurs, \n" ;
00196 echo "les calculs des ".noir("f(x".sub("i").")")." prendront autant de temps. Les inclure dans les fonctions ajouterait \n" ;
00197 echo "les durées de calcul des ".noir("f(x".sub("i").")")." qui peuvent être beaucoup plus importantes que celles des générations des ".noir("x".sub("i"))."\n" ;
00198 echo "et masquer ainsi les durées de génération. \n" ;
00199 finp() ;
00200
00201 p("texte") ;
00202 echo "Vous vous rappelez sans doute comment tester que deux vecteurs sont égaux, mais voici quand même \n" ;
00203 echo "ce qu'il faut écrire et ce qu'il ne faut pas écrire pour le tester : \n" ;
00204 finp() ;
00205
00206 pre_fichier("xiegaux.r","cadre") ;
00207
00208 pre_fichier("compxi.sor","cadrejaune") ;
00209
00210 finsolution() ;
00211
00212 finblockquote() ;
00213
00214 ## -------------------------------------------------------------------------------------------
00215
00216 $tdmCRLM->afficheRubrique("oui") ; $numExo++ ; # Vitesses d'exécution
00217
00218 ## -------------------------------------------------------------------------------------------
00219
00220 blockquote() ;
00221
00222 blockquote() ;
00223
00224 p("texte") ;
00225 echo "Peut-on vraiment affirmer que le code ".noir("mot %in% vec")." est vraiment plus \n" ;
00226 echo "rapide que le code ".noir("grep(mot,vec)")." ? \n" ;
00227 finp() ;
00228
00229 p("texte") ;
00230 echo "Et que ".noir("any(v>0)")." est vraiment plus \n" ;
00231 echo "rapide que le code ".noir("sum(v>0)>0")." ? \n" ;
00232 finp() ;
00233
00234 p("texte") ;
00235 echo "Faut-il \"sortir\" les calculs dans les écritures des bornes des boucles ? Ainsi, \n" ;
00236 echo "faut-il écrire les boucles ".bleu("POUR")." et ".bleu("TANT QUE")." sous la forme \n" ;
00237 finp() ;
00238
00239 pre_fichier("sortir1.txt","cadre") ;
00240
00241 p("texte") ;
00242 echo "plutôt que de les écrire \n" ;
00243 finp() ;
00244
00245 pre_fichier("sortir2.txt","cadre") ;
00246
00247 p("texte") ;
00248 echo "Peut-on encore optimiser le code suivant qui calcule le \n" ;
00249 echo "maximum d'un vecteur, son nombre d'occurrences et toutes ses positions ? \n" ;
00250 finp() ;
00251
00252 pre_fichier("max08.r","cadre") ;
00253
00254 p("texte") ;
00255 echo " Que faire si finalement $R est lent, non dans les fonctions de base mais dans une " ;
00256 echo " fonction utilisateur ?" ;
00257 finp() ;
00258
00259
00260 finblockquote() ;
00261
00262 solution($numExo,$numSerie) ;
00263
00264 p("texte") ;
00265 echo "Il est certainement difficile de démontrer mathématiquement qu'une expression \n" ;
00266 echo "s'exécute vraiment plus rapidement qu'une autre, sauf à être capable de calculer \n" ;
00267 echo "la complexité des algorithmes sous-jacents. Par contre, avec suffisamment \n" ;
00268 echo "d'exemples, on doit pouvoir se convaincre de la rapidité de tel ou tel code. \n" ;
00269 finp() ;
00270
00271 p("texte") ;
00272 echo "En ce qui concerne la détection de la présence d'un mot dans une liste, il semblerait bien que \n" ;
00273 echo "l'expression ".noir("mot %in% vec")." est vraiment plus \n" ;
00274 echo "rapide que le code ".noir("grep(mot,vec)").", même si ajouter le paramètre ".noir("fixed=TRUE")." \n" ;
00275 echo "diminue très sensiblement la durée d'exécution. Pour mémoire, mettre ".noir("fixed=TRUE")." \n" ;
00276 echo "comme paramètre dans l'appel de ".noir("grep")." prévient $R qu'on cherche une chaine \n" ;
00277 echo "de caractères et non pas une expression régulière, ce qui est plus simple \n" ;
00278 echo "à réaliser et donc plus rapide à exécuter : \n" ;
00279 finp() ;
00280
00281 pre_fichier("vite1.txt","cadre") ;
00282
00283 p("texte") ;
00284 echo "En ce qui concerne la deuxième question sur la présence d'au moins un élément positif dans un vecteur, \n" ;
00285 echo "le code suivant qui utilise trois expressions vectorielles donne des résultats d'exécution différents suivant la position \n" ;
00286 echo "des valeurs positives dans le vecteur : \n" ;
00287 finp() ;
00288
00289 pre_fichier("vite2a.txt","cadre") ;
00290
00291 p("texte") ;
00292 echo "Par exemple, avec deux cas extrêmes où la seule valeur positive est située en début ou en fin d'un vecteur de 100 000 éléments, \n" ;
00293 echo "ce n'est pas la même expression vectorielle qui est plus efficace : \n" ;
00294 finp() ;
00295
00296 pre_fichier("vite2b.txt","cadre") ;
00297
00298 p("texte") ;
00299 echo "On pourrait penser écrire notre propre boucle tant que de détection du premier élément positif dans le vecteur, \n" ;
00300 echo "comme dans le code suivant : \n" ;
00301 finp() ;
00302
00303 pre_fichier("vite3.r","cadre") ;
00304
00305 p("texte") ;
00306 echo "Pour nos cas extrêmes, les résultats sont extrêmes aussi : \n" ;
00307 finp() ;
00308
00309 pre_fichier("vite4.txt","cadre") ;
00310
00311 p("texte") ;
00312 echo "Il faut donc en retenir qu'optimiser du code suppose parfois qu'on connait ou qu'on est capable de \"deviner\" la distribution \n" ;
00313 echo "des données, ce qui n'est pas une mince affaire. \n" ;
00314 finp() ;
00315
00316 p("texte") ;
00317 echo "La réponse à la troisième question concernant les conditions de sortie de boucle est un peu plus simple : il faut mettre les \n" ;
00318 echo "calculs constants à l'extérieur des boucles. Il faut donc prendre l'habitude d'écrire \n" ;
00319 finp() ;
00320
00321 pre_fichier("vite5a.r","cadre") ;
00322
00323 p("texte") ;
00324 echo "plutôt que \n" ;
00325 finp() ;
00326
00327 pre_fichier("vite5b.r","cadre") ;
00328
00329 p("texte") ;
00330 echo "car même si le gain n'est pas très important, il est non négligeable, même sur cet exemple simple : \n" ;
00331 finp() ;
00332
00333 pre_fichier("vite5.txt","cadre") ;
00334
00335 p("texte") ;
00336 echo "Pour finir cet exercice, il est facile de voir qu'on peut encore optimiser le code proposé \n" ;
00337 echo "puisque l'expression vectorielle ".noir("V==maxV")." est utilisée deux fois et donc calculée deux fois. \n" ;
00338 finp() ;
00339
00340 p("texte") ;
00341 echo "Si on ne calcule qu'une seule fois cette expression, \n" ;
00342 echo "on dispose d'un code qui peut être jusqu'à deux fois plus rapide : \n" ;
00343 finp() ;
00344
00345 pre_fichier("max09.txt","cadre") ;
00346
00347 p("texte") ;
00348 echo " Si au final, après une étude de complexité de l'algorithme, " ;
00349 echo " $R est lent dans une de vos fonctions, une solution possible consiste à interfacer un programme C++ depuis $R ou, " ;
00350 echo " dans l'autre sens, appeler $R depuis un programme C++. Les packages " ;
00351 echo hrrp("Rcpp") ;
00352 echo " et " ;
00353 echo hrrp("RInside") ;
00354 echo " sont prévus pour cela. On pourra consulter le site " ;
00355 echo href("http://www.rcpp.org/","rcpp.org") ;
00356 echo " et les livres suivants :" ;
00357 finp() ;
00358
00359 p() ;
00360 nbsp(5) ;
00361 $img = "retcpp.png" ;
00362 echo href($img,img($img,"",800)) ;
00363 finp() ;
00364
00365 $urlTV = "https://cran.r-project.org/web/views/" ;
00366 $urlHPC = "https://cran.r-project.org/web/views/HighPerformanceComputing.html" ;
00367 $urlML = "https://cran.r-project.org/web/views/MachineLearning.html" ;
00368
00369 p("texte") ;
00370 echo "Il ne faut pas oublier non plus que $R dispose, dans ses fameuses " ;
00371 echo href($urlTV,em("Task Views")).", " ;
00372 echo " d'une entrée ".href($urlHPC,"HPC") ;
00373 echo " et d'une entrée ".href($urlML,"ML") ;
00374 echo "." ;
00375 finp() ;
00376
00377 finsolution() ;
00378
00379 finblockquote() ;
00380
00381 ## -------------------------------------------------------------------------------------------
00382
00383 $tdmCRLM->afficheRubrique("oui") ; $numExo++ ; # Positions du maximum et gestion de la mémoire
00384
00385 ## -------------------------------------------------------------------------------------------
00386
00387 blockquote() ;
00388
00389 blockquote() ;
00390
00391 p("texte") ;
00392 echo "On veut trouver les 5 premières positions du maximum dans un très grand vecteur d'entiers. \n" ;
00393 echo "Est-ce un problème ? \n" ;
00394 finp() ;
00395
00396 p("texte") ;
00397 echo "Et si maintenant on veut stocker toutes les positions du maximum, comment faire \n" ;
00398 echo "sachant qu'il peut y avoir potentiellement très peu de positions ou au contraire \n" ;
00399 echo "un très grand nombre d'occurrences de ce maximum ? \n" ;
00400 finp() ;
00401
00402 finblockquote() ;
00403
00404 solution($numExo,$numSerie) ;
00405
00406 p("texte") ;
00407 echo "Le mieux est sans doute de commencer par une solution naïve et de tester sa \n" ;
00408 echo "vitesse d'exécution, soit le code : \n" ;
00409 finp() ;
00410
00411 pre_fichier("5posmax01.r","cadre") ;
00412
00413 p("texte") ;
00414 echo "Si c'est effectivement trop lent, on peut envisager un parcours du vecteur \n" ;
00415 echo "à l'aide d'une boucle tant que et sortir dès qu'on a trouvé les 5 premières positions du maximum : \n" ;
00416 finp() ;
00417
00418 pre_fichier("5posmax02.r","cadre") ;
00419
00420 p("texte") ;
00421 echo "Il est sans doute possible d'encore optimiser à l'aide de méta-connaissances. \n" ;
00422 echo "Par exemple si on sait que le vecteur dans lequel dans on recherche le \n" ;
00423 echo "maximum est issu d'une méthode qui converge vers des grandes valeurs, on pourrait \n" ;
00424 echo "commencer la recherche par la fin en initialisant l'indice courant de recherche ".noir("indc")." avec \n" ;
00425 echo "la longueur ".noir("lngv")." du vecteur \n" ;
00426 echo "au lieu de ".noir("1")." \n" ;
00427 echo "et remonter vers le début du vecteur, donc en mettant ".noir("(indc>=1)")." \n" ;
00428 echo "comme deuxième test dans la condition de bouclage du TANT QUE \n" ;
00429 echo "et en décrémentant ".noir("indc")." : \n" ;
00430 finp() ;
00431
00432 pre_fichier("5posmax03.txt","cadre") ;
00433
00434 p("texte") ;
00435 echo "Si au contraire on sait que la méthode est perturbée ou relativement stationnaire \n" ;
00436 echo "au début et en fin, on pourrait commencer à partir du milieu du vecteur et parcourir \n" ;
00437 echo "alternativement à gauche et à droite de cette position de départ, ou commencer \n" ;
00438 echo "avec une position aléatoire \"pas trop proche\" des bords... \n" ;
00439 finp() ;
00440
00441 p("texte") ;
00442 echo "Une deuxième difficulté consiste à choisir des exemples pour tester la vitesse d'exécution des trois solutions \n" ;
00443 echo "présentées. Ainsi, vaut-il mieux générer \n" ;
00444 echo "".noir("leVecteur")." à l'aide de l'expression ".noir("round(runif(n=10**w,min=0,max=100))")." \n" ;
00445 echo "ou avec ".noir("rbinom(n=10**w,size=50,prob=p)")." ? Et avec quelle valeur de ".noir("w")." et ".noir("p")." ? \n" ;
00446 echo "Serait-ce mieux d'utiliser une autre distribution, comment et pourquoi ? \n" ;
00447 finp() ;
00448
00449 p("texte") ;
00450 echo "En ce qui concerne toutes les positions du maximum, le problème est un peu plus compliqué \n" ;
00451 echo "puisqu'on ne connait pas la taille du résultat. On a déjà vu que concaténer une valeur à \n" ;
00452 echo "un vecteur est très lent, en d'autres termes, il faut éviter d'écrire \n" ;
00453 finp() ;
00454
00455 pre_fichier("posmax01.r","cadre") ;
00456
00457 p("texte") ;
00458 echo "au profit d'une écriture en mémoire dans un vecteur de taille définie à l'avance soit \n" ;
00459 finp() ;
00460
00461 pre_fichier("posmax02.r","cadre") ;
00462
00463 p("texte") ;
00464 echo "Comme on ne peut pas prédire à l'avance la taille du résultat, si on doit absolument passer par une boucle ".bleu("POUR").", \n" ;
00465 echo "l'optimisation consiste à ne PAS changer la taille du vecteur résultat TROP SOUVENT. \n" ;
00466 echo "Donc au lieu de changer cette cette taille à chaque passage dans la boucle lorsqu'on trouve une nouvelle fois le maximum, \n" ;
00467 echo "il faut astuctieusement changer cette taille ".em("de temps en temps").", quand la taille courante ne suffit plus. \n" ;
00468 echo "Si (par sondage, expertise, test...) on connait en gros l'augmentation souhaitée de la taille, \n" ;
00469 echo "on peut en profiter pour ne pas trop augmenter à chaque fois la taille ; \n" ;
00470 echo "sinon on peut choisir de la doubler. Voici ce que cela donnerait sur exemple où nous avons décidé d'utiliser une \n" ;
00471 echo "taille de ".noir("n1 <- 5")." éléments au départ et de rajouter ".noir("n2 <- 7")." élements à chaque fois qu'il y en a besoin. \n" ;
00472 echo "Ces valeurs sont ici arbitraires et ne servent qu'à la démonstration. De \"vraies\" valeurs seraient plutot de l'ordre de \n" ;
00473 echo "d'une grande puissance de 10 puisqu'il faudrait déjà que l'expression vectorielle ".noir("which(V==maxV)")." ne soit pas \n" ;
00474 echo "efficace... \n" ;
00475 finp() ;
00476
00477 p("texte") ;
00478 echo "Une remarque : si on augmente de temps en temps la taille du vecteur de résultats avec de ".noir("NA").", il ne faut pas oublier \n" ;
00479 echo "de retirer à la fin ceux qui n'ont pas été remplacés par une vraie position du maximum. C'est bien sûr ce que nou avons \n" ;
00480 echo "fait dans le code suivant : \n" ;
00481 finp() ;
00482
00483 pre_fichier("posmax03.r","cadre") ;
00484
00485 p("texte") ;
00486 echo "Voici ce qu'on obtient sur un exemple : \n" ;
00487 finp() ;
00488
00489 pre_fichier("posmax03.txt","cadre") ;
00490
00491 finsolution() ;
00492
00493 finblockquote() ;
00494
00495 ## -------------------------------------------------------------------------------------------
00496
00497 $tdmCRLM->afficheRubrique("oui") ; $numExo++ ; # Tris et \"big data\"
00498
00499 ## -------------------------------------------------------------------------------------------
00500
00501 blockquote() ;
00502
00503 blockquote() ;
00504
00505 p("texte") ;
00506 echo "On dispose d'un fichier issu de la bioinformatique dont la taille est \n" ;
00507 echo "environ 4 Go. \n" ;
00508 finp() ;
00509
00510 p("texte") ;
00511 echo "Comment faire pour trier les lignes de ce fichier sachant que \n" ;
00512 echo "la mémoire de l'ordinateur est seulement de 2 Go \n" ;
00513 echo "et qu'on veut les cinq premières lignes triées ? \n" ;
00514 finp() ;
00515
00516 p("texte") ;
00517 echo "En fait, on ne s'intéresse qu'aux cinq lignes les plus longues de ce fichier. \n" ;
00518 echo "Faut-il le trier par ordre de taille de ligne et n'en garder que les cinq premières \n" ;
00519 echo "lignes ou peut-on écrire un algorithme plus efficace ? \n" ;
00520 finp() ;
00521
00522 p("texte") ;
00523 echo "Peut-on vraiment affirmer que le code ".noir("sort(V,dec=TRUE)")." est vraiment plus \n" ;
00524 echo "rapide que le code ".noir("rev(sort(V))")." pour trier par ordre décroissant ? \n" ;
00525 finp() ;
00526
00527 finblockquote() ;
00528
00529 solution($numExo,$numSerie) ;
00530
00531 p("texte") ;
00532 echo "Ah, la bioinformatique et ses gros fichiers ! \n" ;
00533 finp() ;
00534
00535 p("texte") ;
00536 echo "On commence ici à entrer dans des problèmes plus délicats et c'est pourquoi ce sera \n" ;
00537 echo "le dernier exercice de cette section. \n" ;
00538 finp() ;
00539
00540 p("texte") ;
00541 echo "Cet exercice peut être classé dans la catégorie ".em("exercices de la mort qui tue")." car \n" ;
00542 echo "il est à la fois chronophage et \"prise de tête\". Voici par exemple ce qu'il serait si simple \n" ;
00543 echo "d'exécuter si on avait assez de mémoire : \n" ;
00544 finp() ;
00545
00546 #% le "vrai" fichier est trilignes.r dans le répertoire Metaseed/Genomes.
00547 # % 63 401 430 lues dans genomes.fasta
00548
00549 pre_fichier("sortlines.r","cadre") ;
00550
00551 p("texte") ;
00552 echo "Dans ce cas, \n" ;
00553 echo "pour notre fichier de test, dont la taille est d'environ 3,9 giga-octets, la lecture \n" ;
00554 echo "des 63,4 millions de lignes prend environ 5 minutes et le tri 20 minutes -- l'ordinateur \n" ;
00555 echo "utilisé ici \n" ;
00556 echo "est relativement assez puissant et, surtout, il a 32 giga-octets de mémoire. Il est clair \n" ;
00557 echo "qu'avec une machine plus limitée en mémoire, cela va prendre encore plus de temps. \n" ;
00558 finp() ;
00559
00560 p("texte") ;
00561 echo "Nous avons essayé d'exécuter le même code sur une machine ".em("Windows")." avec effectivement \n" ;
00562 echo "2 giga-octets de mémoire. En mode session traditionnelle, $R ne se \"plaint\" pas \n" ;
00563 echo "mais n'affiche rien. Le prompt réapparait au bout de quelques minutes mais plus rien ne fonctionne : \n" ;
00564 echo "à chaque nouvelle instruction exécutée, $R répond de façon ".em("sybilline")." : \n" ;
00565 finp() ;
00566
00567 pre_fichier("sortlines01.txt","cadre") ;
00568
00569 p("texte") ;
00570 echo "Avec $rstudio, ce n'est guère mieux. Au bout de quelques minutes aussi apparait le message \n" ;
00571 echo "cette fois un peu plus explicite : \n" ;
00572 finp() ;
00573
00574 pre_fichier("sortlines02.txt","cadre") ;
00575
00576 p("texte") ;
00577 echo "Pour mettre au point le script qui effectue la lecture et le tri, ".b("il ne faut surtout pas")." \n" ;
00578 echo b("utiliser le gros fichier")." car mettre 30 minutes ou plus à chaque essai se révèlera catastrophique \n" ;
00579 echo "en temps. Comme souvent dans ce genre de programmation, il faut écrire et affiner le script sur \n" ;
00580 echo "un petit jeu d'essai avant de tester sans doute une et une seule fois l'exécution sur le gros fichier. \n" ;
00581 finp() ;
00582
00583 p("texte") ;
00584 echo "Puisqu'on ne peut pas charger le fichier des données en mémoire, il faut le \n" ;
00585 echo "scinder en plusieurs petits fichiers puis faire un tri-fusion de ces petits fichiers. \n" ;
00586 echo "Par exemple, 3,9 Go divisés par trois donne 1,3 Go qui est inférieur à la taille de \n" ;
00587 echo "la mémoire de la machine. \n" ;
00588 finp() ;
00589
00590 p("texte") ;
00591 echo "Un tri-fusion consiste à trier chacun de deux fichiers obtenus, disons A et B \n" ;
00592 echo "puis à fusionner les fichiers triés. \n" ;
00593 echo "Pour cela, on lit au fur et à mesure dans chacun des deux fichiers triés, une ligne à \n" ;
00594 echo "la fois, ce qui ne prend presque rien en mémoire, pour écrire dans le fichier \n" ;
00595 echo "résultat C. Voici un exemple élémentaire d'exécution avec 3 lignes dans A \n" ;
00596 echo "et deux lignes dans B. \n" ;
00597 finp() ;
00598
00599 p("texte") ;
00600 echo "Suppons que le contenu des fichiers soit : \n" ;
00601 finp() ;
00602
00603 pre_fichier("trifusAB.txt","cadre") ;
00604
00605 p("texte") ;
00606 echo "Alors l'exécution du tri-fusion des fichiers A et B se fait en 5 étapes :" ;
00607 finp() ;
00608
00609 pre_fichier("trifus1.txt","cadre") ;
00610
00611 p("texte") ;
00612 echo "Après réflexion, nous n'avons sans doute pas besoin d'effectuer un tri-fusion de l'ensemble des fichiers \n" ;
00613 echo "puisqu'on s'intéresse seulement aux cinq premières lignes. On doit pouvoir se contenter de trier chaque partie \n" ;
00614 echo "de fichier lu et de ne conserver que les cinq premières lignes de chaque partie pour tout trier ensuite. \n" ;
00615 finp() ;
00616
00617 p("texte") ;
00618 echo "Voici donc ce qu'on va utiliser comme méthode : \n" ;
00619 finp() ;
00620
00621 ol() ;
00622
00623 debutli() ; p() ;
00624 echo "déterminer le nombre ".b("n")." de lignes du fichier ; \n" ;
00625 finp() ; finli() ;
00626
00627 debutli() ; p() ;
00628 echo "lire la première moitié du fichier, trier et garder les 5 premières lignes ; \n" ;
00629 finp() ; finli() ;
00630
00631 debutli() ; p() ;
00632 echo "lire la seconde moitié du fichier, trier et garder les 5 premières lignes ; \n" ;
00633 finp() ; finli() ;
00634
00635 debutli() ; p() ;
00636 echo "fusionner les deux séries de 5 lignes, trier et ne retenir que les les 5 premières lignes. \n" ;
00637 finp() ; finli() ;
00638
00639 finol() ;
00640
00641 p("texte") ;
00642 echo "Une première difficulté surgit avec la détermination du nombre de lignes en tout dans le gros fichier \n" ;
00643 echo "et dans la lecture de chacune des parties : la fonction standard ".noir("readLines()")." n'est pas prévue pour cela. \n" ;
00644 finp() ;
00645
00646 p("texte") ;
00647 echo "En effet, pour trouver le nombre de lignes du gros fichier initial, il n'est pas possible d'utiliser \n" ;
00648 echo "la fonction de base ".noir("readLines()")." car elle met en mémoire toutes les lignes du fichier. \n" ;
00649 echo "Il faut utiliser la fonction ".noir("determine_nlines()")." du package ".hrrp("LaF")." dont le titre complet est \n" ;
00650 echo bleu("Fast access to large ASCII files").". De même pour lire les lignes ".noir("n".sub("1"))." à ".noir("n".sub("2"))." d'un fichier, \n" ;
00651 echo "il faut passer par la fonction \n" ;
00652 echo " ".noir("n.readLines()")." du package ".hrrp("reader")." \n" ;
00653 echo "dont le titre complet est ".bleu("Suite of Functions to Flexibly Read Data from Files").". \n" ;
00654 finp() ;
00655
00656 p("texte") ;
00657 echo "Nous écrivons la fonction ".noir("prem5(fichier)")." suivante pour automatiser les étapes 2 et 3 \n" ;
00658 echo "qui sont identiques, aux numéros de lignes à lire près : \n" ;
00659 finp() ;
00660
00661 pre_fichier("prem5.r","cadre") ;
00662
00663 p("texte") ;
00664 echo "Dans la mesure où l'exécution prend beaucoup de temps, il est prudent de mettre un affichage dès qu'une étape \n" ;
00665 echo "est réalisée. De plus, au niveau de chaque instruction, disons par exemple ".noir("nbl <- determine_nlines(fichier)").", \n" ;
00666 echo "dans une phase préliminaire, il est prudent d'afficher la durée d'exécution de l'instruction à l'aide la fonction \n" ;
00667 echo " ".noir("duree()")." des exercices de la séance 5, afin d'avoir une idée précise de la durée de chaque étape, soit le code : \n" ;
00668 finp() ;
00669
00670 pre_fichier("insdure.r","cadre") ;
00671
00672 p("texte") ;
00673 echo "Une fois mis au moins et testé sur plusieurs fichiers, \n" ;
00674 echo "le code qui implémente notre méthode est le suivant : \n" ;
00675 finp() ;
00676
00677 pre_fichier("trifus2.r","cadre") ;
00678
00679 /*
00680 p("texte") ;
00681 echo "Les temps d'exécution sont... \n" ;
00682 finp() ;
00683 */
00684
00685 #pre_fichier("trifus2.txt","cadre") ; ==> trouver le résultat et le rajouter
00686
00687 p("texte") ;
00688 echo "Pour en terminer avec cet exercice, on peut sans doute affirmer que le code ".noir("sort(V,dec=TRUE)")." est vraiment plus \n" ;
00689 echo "rapide que le code ".noir("rev(sort(V))").", avec un gain d'environ 10 % comme on peut s'en rendre \n" ;
00690 echo "compte à l'aide nombreux exemples. Ainsi : \n" ;
00691 finp() ;
00692
00693 pre_fichier("sortrev.txt","cadre") ;
00694
00695 $img = "sortrev.png" ;
00696 p() ;
00697 nbsp(4) ;
00698 echo href($img,img($img,"",600)) ;
00699 finp() ;
00700
00701
00702 finsolution() ;
00703
00704 finblockquote() ;
00705
00706 ## -------------------------------------------------------------------------------------------
00707
00708 finPageExercices($numSerie) ; # contient finSection() et finPage() ; la fonction est dans progi.php
00709 ?>
Pour ne pas voir les numéros de ligne, ajoutez &nl=non à la suite du nom du fichier.