Forum

Reprise du message précédent

Bonjour,
J'ai commencé à l'écrire en C et je pense qu'en utilisant des fonctions en racket et pas en C, tu triches un peu. En effet, on ne fait aucun postulat dans le code C. Or on sait qu'un nombre pair ne peut être premier vu qu'il est divisible par 2.
Voilà le code C réécrit correctement :

J'ai supprimé l'appel à la fonction. Deux if sont plus rapides que les appels surtout lorsqu'il y a 250000 appels.

Nouvelle idée. Deuxième version, plus rapide, j'ai inliné la fonction :


Voici la comparaison de ma seconde version avec différentes optimisations :

• -O0 : real 0m3,860s
  user 0m3,860s
  sys 0m0,000s
• -O1 : real 0m2,995s
  user 0m2,995s
  sys 0m0,000s
• -O2 : real 0m3,012s
  user 0m3,012s
  sys 0m0,000s
• -O3 real 0m3,023s
  user 0m3,023s
  sys 0m0,000s
  

Il semble ici que le -O1 soit suffisant. Mais optimisé le code n'est pas négligeable.

Si tu souhaites faire une comparaison correcte, tu dois écrire l'algorithme toi-même pas utiliser une fonction déjà implémentée et optimisée en racket.

Voilà une version optimisée de l'algorithme pour ceux que ça intéresse de comparer :

Le résultat :

La division /2 peut dans certain cas être plus long qu'une rotation de bit à droite >>1
Normalement avec l'optimisation, la variable dans la condition venant de l'argument devrait ne pas se faire re-vérifier, mais en cas de doute, tu peux la faire à l'extérieur du for.

Pour supprimer les paires :

Je ne maitrise pas du tout le principe des bits donc je ne l'utilise jamais même si je sais que c'est plus rapide.


Je pense qu'un for(i=...,...,i+2) comme dans le code en Fortran sera plus rapide que de rajouter une condition if.

oui tu as tout à fais raison. Mais il faut compter 1 et 2 dans les nombres premiers.

1 n'st pas premier par définition . Dans le code Fortran, on triche en faisant partir le conteur à 1 puisque l'on sait que 2 est premier.

Voici la version Python :



Avantage FORTRAN
C'est plus performant que d'établir la liste des nombres premiers et de la dénombrer, mais la différence n'est pas si flagrante.

Édité par Papoteur Le 09/01/2022 à 09h10

Ce que montre ce test, c'est qu'il est très important de soigner son algorithme si on veut de la performance. On peut obtenir la même chose en mille fois plus de temps si on s'y prend mal.
L'algorithme qui est mis en œuvre dans le premier cas en Python est :

eh bien je suis content que ce sujet vous passionne;
ça met un peu d'animation sur le forum, tout en montrant que l'informatique, c'est pas forcément des problèmes mais que ça peu être fun!

en C, j'aurai cru que le fait de supprimer l'appel de fonction aurait eu plus d'effet; ça améliore un peu, mais pas tant que ça;
en tout cas, ça bouscule les idées reçus sur l'efficacité du C;
on découvre que ça reste le fortran, sur ce genre de calcul, qui reste indétrônable;
on comprend mieux pourquoi les physiciens y sont tellement attaché;

j'ai essayé d'implémenter en racket, la version optimisée en fortran; comme ça il ne restera plus qu'à faire celle en C puisqu'on a celle en python de Papoteur pour avoir une vision d'ensemble, du même algo;



mais, c'est pas génial au niveau exécution, ça reste beaucoup plus lent que la version fonctionnelle du début en 1 seule ligne
j'ai fait plusieurs run, c'est entre 750 et 800 millisecondes;
mais, je ne fais pas appel à une librairie spéciale;
c'est mieux pour la cohérence de la comparaison.
mais je ne pense pas que la différence entre les deux vienne uniquement de cette librairie, du simple prédicat "prime?";
dans l'ensemble, c'est la méthode fonctionnelle qui s'avère être efficace en elle-même.

Édité par marc-andré Le 09/01/2022 à 15h03

Il est difficile de dire si le Fortran est sur ce cas beaucoup plus rapide. Je ne pense pas pouvoir beaucoup plus l'optimisé alors qu'il y a encore de la marge en C. On peut utiliser les opérateurs bit à bit comme le fait Jybz. On peut aussi utiliser le mot clef likely dans le if. Cela va dire au compilateur qu'il y a plus de chance de tomber sur le prédicat. En effet, sur tous les nombres, il y a plus de chances de tomber sur un non-diviseur que sur un diviseur. On va donc améliorer l'optimisation au niveau de la compilation.

Le plus rapide semble d'être d'inliner la fonction. En faisant ça, elle va être intégrée dans le main lors de la compilation.

tu as corrigé, j'avais trouvé bizarre car tu avais un temps plus long avec cette méthode!

en fait, en racket c'est pareil, c'est beaucoup plus efficace de dénombrer la liste des nombres premiers que de les compter comme en fortran;
c'est assez contre intuitif mais c'est ainsi;
ce qui coûte, c'est les assignations et le fait de gérer des variables;
dans la version impérative en racket, on est obligé de gérer, le compteur, le diviseur et d'égrener chaque numéro;
cela donne chaque fois des "let" imbriqués;
et l'assignation c'est "set!" le ! pour indiquer un effet de bord, source de tous les problèmes en informatique
avec la méthode fonctionnelle, il n'y a pas tous ces problèmes, il n'y a pas de source de bug, c'est une seule ligne de code;
c'est le miracle des "continuations"; on ne sait pas ce qui se passe sous le chapeau, la liste produite par "filter" est simplement dénombrée par "length";
c'est pratique à écrire, mais ce qui est surprenant, c'est que ça soit aussi beaucoup plus efficace;
en résumé, sur mon ordi :
la méthode fonctionnelle
en typed/racket : entre 250 et 300 millisecondes;
la même en racket, environ 450 millisecondes;
on voit clairement l'overhead de 50% entre typed ou pas;
et la version impérative optimisée (soit disant) ci dessus, entre 750 et 800;

PS j'ai essayé de mettre le code dans "citation", c'est mieux je pense, mais on perd l'indentation et la coloration syntaxique, du coup, c'est pas très lisible;
j'ai toujours du mal avec ces machins;
c'est quoi le truc à utiliser pour coller du code sur ce service?

Utiiser [ code]...[ \code] au lieu de [ quote][ /quote]

OK mais il n'y a pas une icône pour le faire?

poursuite de l'investigation;
mesure de l'impact du prédicat "prime?" dans la performance;
en fait Yuusha a raison, il est important;
ultime version en racket



et sur plusieurs run, ça se situe entre 300 milliseconde;
donc, la performance vient essentiellement de lui;

mais avoir des librairies efficaces, ça fait partie des critères pour estimer un langage;
ici c'est le cas

et en plus, ça marche pas!
c'est vraiment une peine ces machins qu'on sait jamais comment s'en servir

et c'est d'autant plus vicieux que j'avais fait une prévisualisation et que ça avait l'air d'être bon et au final rien!

en fait si ça marche, je ne comprends pas ce qui c'est passé
merci et excuses pour ce message

Édité par marc-andré Le 09/01/2022 à 14h36

En fait, il n'y a aucune espace, je les ai rajouté pour ne pas être interpreté.
Oui il y a un bouton, il faut développé la barre-menu tout à droite.