Salut 36contre37.
36contre37 a écrit:Voilà, tu as réduit le temps d'exécution.
Pour la simple raison, que l'approche d'Ainelle n'était pas optimale.
36contre37 a écrit:Et il n'y a plus aucune possibilité dans notre exemple de pièces ?
Du point de vue mathématique, je suppose que l'on peut envisager de trouver une fonction algébrique donnant exactement les mêmes nombres.
Dans cet exemple, la cagnotte est composé de 4 jetons, et la probabilité est de 1/2 dans le cas du gain et de la perte.
Il suffit d'indiquer x le nombre de coups et de déterminer f(x) donnant par exemple le nombre de ruine.
36contre37 a écrit:Nous sommes définitivement coincés par les puissances de 2 qui nous poussent au delà des capacités de l'appareil ?
En effet, par l'approche du dénombrement, ,ous sommes coincés.
36contre37 a écrit:Tu dois vouloir dire "foncer tête baissée".
On peut dire ça aussi.
36contre37 a écrit:C'est pareil, non ? Chercher à améliorer, voire optimiser, c'est bien chercher une méthode plus pertinente.
Ce n'est pas pareil du tout.
Optimiser, c'est améliorer les performances d'une méthode qui existe, sans changer le principe de la méthode.
Une solution possible est de changer de processeur pour améliorer la performance.
Une méthode plus pertinente, c'est trouver une nouvelle approche, donnant les même solutions.
C'est le cas entre l'approche Excel d'ainelle basé sur le dénombrement, et mon approche récursive en langage 'C'.
Les deux méthodes ne sont pas pareils car dans mon approche, je n'ai pas envisagé d'étudier toutes les solutions possibles, mais juste celle qui sont optimales.
36contre37 a écrit:Le code dont je te parle avait pulvérisé le record du temps d'exécution. Tu penses bien que la méthode est déjà très pertinente.
Je veux bien vous croire, mais qu'est-ce que vous entendez par "pulvériser le record" ?
Au lieu de mettre 48 heures, il met simplement cinq minutes.
En changeant d'approche, si c'est possible, on peut passer de cinq minutes à cinq secondes.
36contre37 a écrit:Il y avait, paraît-il mais je ne réalise pas trop à quel point, un problème à cause d'utilisation de tables de conversions (lookup tables).
Problème récurrent en informatique, les conversions implictes.
36contre37 a écrit:Cette performance a été améliorée depuis par un autre informaticien "by using a pre-computed perfect hash function instead of a binary search ".
Tu sais ce qu'est une "hash function" ?
Oui !
Quand on veut gérer un tableau, il existe plusieurs méthodes qui permettent de retrouver l'information qui l'on cherche.
Par exemple, en clef j'ai un nom d'une personne et je cherche sa date de naissance. Tous les noms sont différents.
L'approche basique consiste à lire tous les éléments du tableau, en commençant par le premier élément et on s'arrête dès que l'on obtient l’égalité. Sauf si l'on atteint la fin du tableau, et dans ce cas, nous n'avons pas trouvé ce que l'on cherche.
S'il y a 1024 éléments dans le tableau, en moyenne, on fait 512 accès, soit la moitié du nombre d'éléments.
Autre approche, celle par la recherche dichotomique. Il faut au maximum 10 accès pour trouver l'information que l'on cherche car 2^10 = 1024.
Mais il y a encore mieux :
les fonctions de hachage.
Il s'agit de convertir le nom qui est stocké dans le tableau, en une clef qui est unique.
En théorie, elle est unique, mais il arrive parfois que deux noms différents peuvent produire la même clef. On nomme cela une collision !
Autrement dit, on accède à l'information en un seul accès ! D'où une performance plus grande.
36contre37 a écrit:Bref, cela fait pas mal de choses à chercher à comprendre ...
Je comprends car résoudre un problème en informatique demande une gymnastique intellectuelle.
@+