Algorithme utilisant les octets.

Ce salon est tout spécialement réservé aux nouveaux membres qui souhaitent se présenter et faire des connaissances ...vous avez une expérience dans le monde des casinos, recherchez des conseils, adressez-vous à notre communauté de joueurs et de passionnés.

Algorithme utilisant les octets.

Message non lupar 36contre37 » Sam Mar 03, 2018 12:02 pm

Artemus24 a écrit:J'ai simplement reproduit le même algorithme, donc c'est normal que le résultat soit le même.

Pas tout à fait.
J'ai dû, de mon côté, bidouillé pour dresser la liste des possibilités.
Tu disposes, en tant qu'informaticien et programmeur, d'outils plus sophistiqués qui permettent d'optimiser grandement les algorithmes.
C'est le cas ici où tu as employé astucieusement le bitset.
Cela t'a même permis de faire l'économie de l'affichage de cette liste.
Peux-tu nous donner, stp, la syntaxe qu'il faudrait utiliser pour dresser la liste des 32 possibilités avec 5 lancers par exemple?
36contre37
Googlejack
Googlejack
 
Messages: 1993
Jackpoints: 33480
Donner
Inscription: Ven Fév 27, 2015 9:23 am


Re: Algorithme utilisant les octets.

Message non lupar Artemus24 » Dim Mar 04, 2018 9:53 am

Salut 36contre37.

Voici l'exécution du programme 'C++' avec affichage des résultats intermédiaires :

Code: Tout sélectionner
11111    cumul = 9
11110    cumul = 7
11101    cumul = 7
11100    cumul = 5
11011    cumul = 7
11010    cumul = 5
11001    cumul = 5
11000    cumul = 3
10111    cumul = 7
10110    cumul = 5
10101    cumul = 5
10100    cumul = 3
10011    cumul = 5
10010    cumul = 3
10001    cumul = 3
10000    cumul = 1
01111    cumul = 7
01110    cumul = 5
01101    cumul = 5
01100    cumul = 3
01011    cumul = 5
01010    cumul = 3
01001    cumul = 3
01000    cumul = 1
00111    cumul = 5
00110    cumul = 3
00101    cumul = 3
00100    cumul = 1
00011    cumul = 3
00010    cumul = 1
00001    cumul = 0
00000    cumul = 0
Nb = 5  max = 32 Ruine = 2 Rapport = 0.0625
Appuyez sur une touche pour continuer...


36contre37 a écrit:Peux-tu nous donner, stp, la syntaxe qu'il faudrait utiliser pour dresser la liste des 32 possibilités avec 5 lancers par exemple?

Je ne comprends pas ce que vous entendez par syntaxe ?
Dans mon exemple, j'ai juste comptabilisé le nombre de fois où le cumul est <=0 pour déterminer le nombre de "ruine".
Pour la probabilité, c'est le rapport entre ce nombre de ruine divisé par le nombre total de possibiliés.

Et voici le source du programme 'C++' en question :

Code: Tout sélectionner
#include <iostream>
#include <bitset>
#include <cmath>

using namespace std;

/********************************/
/*                              */
/*                              */
/*                              */
/********************************/

int main()
{
   const int   nb  = 5;
   const int   max = pow(2, nb);

   int         cum, nbre = 0;
   string      elem;

   for (int i=max-1; i>=0; i--)
   {
      elem = bitset<nb>(i).to_string();
      cum = 4;

      for (int j=0; j<nb; j++)
      {
         if (elem[j] == '0')      { if (cum > 0) cum--; }
         else               { if (cum > 0) cum++; }

      cout << elem[j];
      }

      cout << "    cumul = " << cum << endl;
      if (cum <= 0)   nbre++;
   }

   cout << "Nb = " << nb << "  max = " << max << " Ruine = " << nbre << " Rapport = " << (double)nbre/(double)max << endl;
   return 0;
}


@+
Artemus24
Modérateur
Modérateur
 
Messages: 4010
Photos: 0
Jackpoints: 61390
Donner
Inscription: Jeu Mar 24, 2011 8:27 am

Re: Algorithme utilisant les octets.

Message non lupar 36contre37 » Dim Mar 04, 2018 10:55 am

Artemus24 a écrit:Dans mon exemple, j'ai juste comptabilisé le nombre de fois où le cumul est <=0 pour déterminer le nombre de "ruine".
Pour la probabilité, c'est le rapport entre ce nombre de ruine divisé par le nombre total de possibiliés.

ça, je l'ai bien compris.
Je parlais de l'affichage de la liste des possibilités.
Artemus24 a écrit:Et voici le source du programme 'C++' en question :

Ok, je viens de comprendre pourquoi l'affichage ne se faisait pas dans ton premier code
C'est parce que tu avais "grisé" cout << elem[j] pour faire l'économie de l'affichage justement.
Artemus24 a écrit:Je ne comprends pas ce que vous entendez par syntaxe ?

La syntaxe, c'est les règles qui gèrent la phrase que ce soit dans notre langue (le français) ou un langage informatique.
C'est la façon dont les mots se combinent pour former des phrases.
Par exemple, j'ai remarqué que tu faisais des fautes de syntaxe en employant le pronom "dont".

Je te demandais donc comment il fallait employer le mot "bitset" pour obtenir les 32 possibilités.
Si ma syntaxe est mauvaise, ma phrase n'est pas comprise et l'exécution du programme ne me donne pas de résultat ou ne me donne pas le résultat escompté. Maintenant que l'affichage apparaît, je comprends que la bonne syntaxe était :
elem = bitset<nb>(i).to_string();
Je ne comprends pas vraiment pourquoi il faut écrire:
<nb>(i).to_string() pour créer le bitset mais je dois convenir que c'est la bonne syntaxe.
Merci Artemus .
36contre37
Googlejack
Googlejack
 
Messages: 1993
Jackpoints: 33480
Donner
Inscription: Ven Fév 27, 2015 9:23 am

Re: Algorithme utilisant les octets.

Message non lupar Artemus24 » Lun Mar 05, 2018 5:56 pm

Salut 36contre37.

36contre37 a écrit:Je parlais de l'affichage de la liste des possibilités.

Vous vouliez savoir comment se faisait l'affichage des différentes possibilités.
Les lignes où se font l'affichage sont en commentaire dans le source. Je parle de ces lignes :

Code: Tout sélectionner
//   cout << elem[j];
}
//   cout << "    cumul = " << cum << endl;

Une ligne en commentaire en 'C++' commence par '//'.

Le premier affichage (cout) donne la chaine de caractères. Par exemple : "00111" pour le nombre 7.
La second affichage donne le cumul : "cumul = 5" avec "0" pour -1 et "1" pour +1.

36contre37 a écrit:Je te demandais donc comment il fallait employer le mot "bitset" pour obtenir les 32 possibilités.

Bitset est une fonction avec des paramètres à passer.
Il y a deux paramètres, la taille du tableau de bits, et la variable à convertir.

La syntaxe de l'instruction "bitset" est la suivante :

Code: Tout sélectionner
elem = bitset<nb>(i).to_string();

--> elem est une variable de type chaîne de caractères. Autrement dit, c'est un tableau de caractères commençant à l'indice 0.
--> <nb> : c'est la largeur en caractères de l'affichage. Par exemple si j'indique 5, j'aurai cinq bits.
--> (i) : c'est la valeur numérique (integer) que je désire convertir.
--> .to_string() : c'est une fonction qui va transformer mon bitset en chaîne de caractères.

La syntaxe que j'ai utilisé n'est pas à l'identique de ce qui est proposé dans le lien ci-après :
--> http://guillaume.belz.free.fr/doku.php?id=bitset

@+
Artemus24
Modérateur
Modérateur
 
Messages: 4010
Photos: 0
Jackpoints: 61390
Donner
Inscription: Jeu Mar 24, 2011 8:27 am

Re: Algorithme utilisant les octets.

Message non lupar 36contre37 » Lun Mar 05, 2018 6:41 pm

Artemus24 a écrit:La syntaxe est:
elem = bitset<nb>(i).to_string()
--> elem est une variable de type chaîne de caractères. Autrement dit, c'est un tableau de caractères commençant à l'indice 0.
--> <nb> : c'est la largeur en caractères de l'affichage. Par exemple si j'indique 5, j'aurai cinq bits.
--> (i) : c'est la valeur numérique (integer) que je désire convertir.
--> .to_string() : c'est une fonction qui va transformer mon bitset en chaîne de caractères.
La syntaxe que j'ai utilisé n'est pas à l'identique de ce qui est proposé dans le lien ci-après :
--> http://guillaume.belz.free.fr/doku.php?id=bitset

Voilà, c'est exactement ce que je demandais quand je te parlais de syntaxe (J'avais compris le reste).
Merci.
36contre37
Googlejack
Googlejack
 
Messages: 1993
Jackpoints: 33480
Donner
Inscription: Ven Fév 27, 2015 9:23 am

Re: Algorithme utilisant les octets.

Message non lupar 36contre37 » Mar Mar 06, 2018 5:05 am

Ok, autrement dit, bitset permet d'écrire un nombre en base 2.
Par exemple bitset<5>(27).to_string() permet d'écrire le nombre 27 en base 2 (dans une chaîne de 5 caractères).
Et on obtient 11011.

Artemus, as-tu déjà utilisé le bitwise ?
36contre37
Googlejack
Googlejack
 
Messages: 1993
Jackpoints: 33480
Donner
Inscription: Ven Fév 27, 2015 9:23 am

Re: Algorithme utilisant les octets.

Message non lupar Artemus24 » Mar Mar 06, 2018 11:54 am

Salut 36contre37.

Que désirez-vous faire exactement comme opération sur les bits ?

@+
Artemus24
Modérateur
Modérateur
 
Messages: 4010
Photos: 0
Jackpoints: 61390
Donner
Inscription: Jeu Mar 24, 2011 8:27 am

Re: Algorithme utilisant les octets.

Message non lupar 36contre37 » Mar Mar 06, 2018 12:31 pm

Artemus24 a écrit:Que désirez-vous faire exactement comme opération sur les bits ?

N'étant pas informaticien, je bidouille des programmes avec un nombre limité d'outils.
Je suis donc, en général, obligé d' utiliser la "force brute".
Pour des problèmes simples, comme l'étude de 10 lancers dans l'exemple précédent, ce n'est pas trop gênant.
Mais comme tu l'as montré avec le bitset, l'emploi d'outils plus sophistiqués améliore l'esthétique d'une part mais avant tout optimise l'exécution.
Je suis un peu étonné cependant, dans cet exemple, que l'exécution devienne si lente dès que le nombre de lancers approche la trentaine.
Tu ne connais pas d'autres moyens d'optimiser ?

Pour répondre précisément à ta question, je me suis intéressé à un beau problème de programmation en relation avec notre centre d'intérêt.
C'est le problème de la comparaison de mains de poker (5 cartes pour commencer).
J'ai un code en force brute. C'est bien beau mais pour des utilisations un peu pointues du sujet, il devient vite trop chronophage, voire inopérant.
J'ai donc fait des recherches sur internet.

Des informaticiens se sont évidemment penchés sur la question, se sont défiés dans une course à l'optimisation en employant le bitwise.
J'ai un code, qui détint un temps le record du monde, je pourrais m'en contenter mais, par curiosité, il ne me déplairait pas de chercher à mieux le comprendre, voire à l'adapter pour d'éventuels prolongements personnels.

Je crois qu'il y a plusieurs informaticiens ici.
C'est un sujet qui pourrait intéresser?
Je l'ai étudié et mis de côté, il y a déjà plusieurs années.
Il faudrait donc que je commence par le déterrer et le dépoussiérer.
36contre37
Googlejack
Googlejack
 
Messages: 1993
Jackpoints: 33480
Donner
Inscription: Ven Fév 27, 2015 9:23 am

Re: Algorithme utilisant les octets.

Message non lupar Artemus24 » Mar Mar 06, 2018 1:24 pm

Salut 36contre37.

36contre37 a écrit:Tu ne connais pas d'autres moyens d'optimiser ?

Il s'agit de faire du dénombrement. De ce fait, plus vous augmentez le nombre de possibilités et plus le temps d'exécution devient long.

La question sera alors de raisonner différemment pour accélérer l'obtention du résultat recherché.
Quand je me suis intéressé à la piquemouche, ainelle me disait qu'il utilisait Excel et qu'il le faisait tourner depuis au moins six mois, sans obtenir un quelconque résultat.
Déjà avec les explications de Jean Comtat, je ne comprenais pas bien comment la piquemouche fonctionnait. Pourquoi ? Parce que l'exemple était faux !
Mais avec les explications d'Ainelle, j'ai pu concevoir un programme basé sur la récursivité.
Ce qui fait qu'en quelques secondes, j'obtenais le résultat optimal attendu.

36contre37 a écrit:Des informaticiens se sont évidemment penchés sur la question, se sont défiés dans une course à l'optimisation en employant le bitwise.

Le bitwise permet de faire des opérations, genre "AND" et "OR" sur des binaires.
Au lieu de partir tête bêche dans une optimisation, il faudrait se poser la question si cette méthode est la plus pertinente.

@+
Artemus24
Modérateur
Modérateur
 
Messages: 4010
Photos: 0
Jackpoints: 61390
Donner
Inscription: Jeu Mar 24, 2011 8:27 am

Re: Algorithme utilisant les octets.

Message non lupar 36contre37 » Mar Mar 06, 2018 5:14 pm

Artemus24 a écrit:j'ai pu concevoir un programme basé sur la récursivité.
Ce qui fait qu'en quelques secondes, j'obtenais le résultat optimal attendu.

Voilà, tu as réduit le temps d'exécution .
Et il n'y a plus aucune possibilité dans notre exemple de pièces ?
Nous sommes définitivement coincés par les puissances de 2 qui nous poussent au delà des capacités de l'appareil ?

Artemus24 a écrit:Au lieu de partir tête bêche
Tu dois vouloir dire "foncer tête baissée".
Artemus24 a écrit:dans une optimisation, il faudrait se poser la question si cette méthode est la plus pertinente.

C'est pareil, non ? Chercher à améliorer, voire optimiser, c'est bien chercher une méthode plus pertinente.

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.
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) .

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" ?
Bref, cela fait pas mal de choses à chercher à comprendre ...
36contre37
Googlejack
Googlejack
 
Messages: 1993
Jackpoints: 33480
Donner
Inscription: Ven Fév 27, 2015 9:23 am

Re: Algorithme utilisant les octets.

Message non lupar Artemus24 » Mer Mar 07, 2018 5:06 am

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.

@+
Artemus24
Modérateur
Modérateur
 
Messages: 4010
Photos: 0
Jackpoints: 61390
Donner
Inscription: Jeu Mar 24, 2011 8:27 am


Retourner vers Bar du forum : présentation, discussions diverses ...




 


  • Articles en relation
    Réponses
    Vus
    Dernier message

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 9 invités

  • Partenaires
cron