PROBLEME DU LOGARITHME DISCRET
verdy_p
Messages postés
202
Date d'inscription
vendredi 27 janvier 2006
Statut
Membre
Dernière intervention
29 janvier 2019
-
20 mai 2013 à 06:19
Marwen - 16 avril 2015 à 20:43
Marwen - 16 avril 2015 à 20:43
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/55157-probleme-du-logarithme-discret
https://codes-sources.commentcamarche.net/source/55157-probleme-du-logarithme-discret
16 avril 2015 à 20:43
Merci en avance
2 juin 2013 à 16:09
Merci et cordialement de faire avancer l'informatique.
citation
"Les codes Gouvernet le mondes par ricochet les informaticiens contiennent le monde"
20 mai 2013 à 06:19
if ((tab[ind_inf]).a < temoin.a)
devrait plutôt être:
if ((tab[ind_inf]).a <= temoin.a)
Tout bonnement parce que cela assure la "stabilité" du tri, et cela évite aussi de procéder à l'échange quand le témoin est égal à la valeur testée de l'intervalle (ce qui est vrai dès le début puisque au départ ind_inf==0 et c'est déjà la position du témoin.
Ensuite pas la peine de comparer cette position de départ : on sait que c'est déjà le témoin, la boucle devrait donc commencer à la position suivante donc remplacer:
ind_inf = 0;
par
ind_inf = 1;
Pas d'inquiétude : c'est suivi du test while() permettant de sortir de la boucle tout de suite (et on sait déjà à l'entrée de la fonction que taille > 1 donc que le témoin en position [0] est toujours présent dans l'intervalle ainsi que le suivant [1] à comparer.
Ce qui amène à une autre optimisation puisqu'on sait alors qu'il est inutile de tester au début de la boucle, mais uniquement à la fin avec:
do{...}while(ind_inf <= ind_sup);
au lieu de:
while(ind_inf <= ind_sup){...}
(en effet le premier test est déjà fait sur if(taille>1)...
Enfin pourquoi garder dans la boucle "temoin.a" via une variable de structure Couple quand temoin pourrait directement contenir la valeur comparée ?
Finalement tu n'optimises pas la récursion terminale (le langage C ne l'optimise pas automatiquement comme pour les langages fonctionnels) : normalement on utilise une boucle pour le faire. Mais ici on a deux récursions, et la récursion terminale devrait être sur la longueur d'intervalle la plus longue afin que son remplacement par une boucle réduise le plus possible les autres récursions (qui ne persisteront que sur la récussion la plus courte des deux, donc nécessiront moins d'espace annexe en pile d'appel).
Pour un tri optimal en fait dans ton algo, un meilleur candidat est le "tri de Tim" (TimSort) qui est dorénavant celui par défaut dans Perl, Java, OpenJDK, Android, etc... car il est stable, est O(n.log n) pratiquement tout le temps même dans le pire cas, et quasi linéaire en O(n) pour les cas pratiques, et optimal en terme de localité (réduction du swap, maximisation de l'efficacité des caches, réduction des I/O si tri externe, ou si la mémoire de travail est non volatile mais utilise des cellules Flash dont les cycles d'écriture doivent être réduits en maximum, réduction de l'énergie consommée, etc...). Le Timsort est un hybeide entre un tri par fusion (Mergesort), et un tri par insertion et il s'avère même en pratique plus rapide que le "tri rapide", ùême s'il demande un peu de mémoire de travail (mais en fait moins que pour les récursions du tri rapide). Le Timsort fonctionne aussi bien pour trier des vecteurs que des listes chainées.