Bonjour à tous,
 
Je suis plutot novice en C et je fais un programme qui a besoin de faire beaucoup appel à de l'aléa pour celà j'utilise la fonction :
 
int EternityIISolver::hasard(int min, int max){
 
return (int) (min + ((float ) rand() / RAND_MAX * (max - min + 1)) );
 
}
 
mais comme j'y fais appel souvent le programme est troop lent.
Y a t il plus rapide ?
Merci

Déjà, est-ce que t'as un réel besoin d'une fonction "vraiment" aléatoire ?
 
En effet, y'a d'autres éléments accessibles sur un PC capables de fournir des éléments suffisament aléatoires pour beaucoup d'application, et qui ne nécessitent pas le moindre calcul.
 
Ensuite, je suis pas trop sûr que tes cast soient super optimisés. Tu nous mélange du int et du float à tout va. Je te conseille de bosser exclusivement en float, et ne caster qu'au retour, ou inversement, caster le plus tôt possible vers du int exclusivement. Mais bon niveau perfs ça changera pas grand chose.

en fait avec cette fonction je prend aléatoirement un entier entre 2 autres.
 
et le problème est que oui j'ai besoin de qqch de bien aléatoire (simulation numérique), d'ou aussi mon pb de perf car j'y fais souvent appel...
 
sinon à quoi tu penses pour d'autres éléments fournissant de l'aléatoire ? l'heure d'execution d'un calcul par ex ?

Y'a plein de choses "plus ou moins aléatoires" dans un programme : l'adresse d'un pointeur que tu viens de créer, décallage de quelques bits du résultat de la dernière génération de nombre aléatoire, etc.
 
Le problème de l'horloge, c'est que si effectivement ça bouge tout le temps, y'a une limitation très contraignante :
- Entre deux appels successifs rapprochés, la valeur est sensiblement la même, donc on va devoir faire une chiée de calculs dessus pour donner l'impression d'avoir une valeur aléatoire
 
Une solution qui donne des nombres assez aléatoires, mais qui au bout d'un moment va produire des séries remarquables :
-> Tu initialise un float[1024] avec des rand()
-> Puis tu fais des calculs débiles dessus à chaque appel de ta fonction rand() perso.
 
Genre tu vas chercher dans ton array la ligne qui est égale à la valeur du dernier appel.
 
Exemple :
 
mesrnd[0] = 3;
mesrnd[1] = 9;
mesrnd[2] = 2;
mesrnd[3] = 5;
 
au premier appel, j'ai eu 0 comme précédente valeur de retour. donc je récupère la ligne d'indice 0 => 3
 
au second appel, j'ai eu 3 comme précédente valeur de retour. donc je récupère la ligne d'indice 3 => 5
 
au troisième appel, j'ai eu 5 comme précédente valeur de retour, donc je récupère la ligne d'indice 5%4 => 9
 
etc.
 
tu peux t'amuser à combiner les résultats ensuite, histoire de ne pas te limiter à 1024 valeurs. y'a plein de solutions toutes simples. d'ailleurs il faudra améliorer un peu le truc, parce que sinon tu finis forcément par boucler sur un nombre limité de valeurs.  
après, faut voir si tu fait des millions d'appels successifs à rand() tu vas évidement vite tourner en rond avec un échantillon limité de valeurs. tu peux ensuite tout à fait décider qu'au bout de N appels à ta fonction, tu régénères ton array de valeurs avec de nouveaux appels réels à rand().
 
un autre truc, rand() ça retourne un nombre float. avec tout plein de chiffres dont tu te moques.
pourquoi les perdre ?
si ton "max" ne dépasse jamais 1000 par exemple, tu peux très facilement recycler la dernière valeur de rand() en la multipliant par 1000 et en faisant un modulo dessus, et ce, 3 ou 4 fois de suite avant d'atteindre la limite de précision du float.
un bon moyen simple de diviser sensiblement les appels à rand().
 
etc.
 
=> Ici, on se reconte que j'ai pas de pot, je tape direct dans une limitation de ce système : je boucle sur deux valeur, ce qui fait me mes valeurs générées vont être répétitives.

foutaise foutaise foutaise
 
Qu'est-ce qui te fait dire que c'est rand() qui rend ton programme lent à part ton "intuition" ?

mais vraiment t'écris n'importe quoi magic, c'est incroyable.

pas grand chose c vrai
 
mais avant que j'introduise cette notion dans le prog ca allait 1000 fois plus vite environ. mais c vrai que j'ai fait plusieurs modifs en meme temps...

c'est bizarre, parceque c'est pourtant ce qu'il me semble avoir lu à propos de jeux vidéos : ils travaillent souvent à partir de tables figées de nombres aléatoires, plutôt que d'en régénérer de nouveaux à chaque fois... je vois donc pas ce qu'il y a comme problème dans la solution que j'indique.
 
après, que rand() ne soit effectivement pas une source de relentissement, fort possible. mais je ne vois pas en quoi ça me ferait dire n'importe quoi.
 
bref, t'es bien gentil, mais vas-y, pour une fois, dis-un truc constructif au lieu de dire "foutaise". explique. t'es ici pour ça mon bonhomme.

Commence par trouver ce qui consomme vraiment du temps, avec un outil de préférence. Le rand de base, c'est l'implémentation de générateur de nombres pseudo-aléatoires la plus quiche qui soit: ça doit pas coûter plus qu'un appel de fonction et un modulo, autrement dit peanuts. Aucune raison donc d'incriminer d'emblée ta fonction hasard.

Par ailleurs, attention à ton implémentation : il faut que min < max pour que ça fonctionne bien et que (max - min) < RAND_MAX pour que tu aies un semblant de qualité.
edit: et que si (min + 1) == max, ça retournera toujours min. Donc un autre petit +1 au diviseur devrait arranger les choses il me semble.

n'importe quoi. Tu fais quoi dans cette cat C ? pourquoi tu dis d'optimiser les casts pour ensuite dire que ça n'apporte pas de performance ? Le mieux c'est ton

qui montre bien que tu n'as rien compris du tout à ce dont on parle -- Boulou utilise la meilleure méthode qui soit avec rand -- que tu ne connais même pas le prototype de rand() fonction de la bibliothèque standard.

autant pour moi, en effet rand() renvoie un int.
 
sauf que là je vois pas trop l'utilité de passer par float si c'est pour retourner un int au final...
 
j'imagine quand même que RAND_MAX est suffisament grand non ?
alors une division entière, pour retourner un nombre entier, c'est pas trop la mort...
 
mise à part le risque de reduire de façon imperceptible l'homogénéité des résultat, je ne vois pas en quoi le passage par float pourrait être mieux.
 
m'enfin bon, ce que j'en dit...

tu en dis de la merde ...
 
c'est le 10^9 topic sur le sujet, on a deja debattu 10 fois que c'était la seul façon propre de faire du rand.
 
stp pour notre santé mental, repart dans la cat C#

Oui, d'ailleurs parfois RAND_MAX vaut 2147483647, ce qui veut dire que ta division entiere renvoie toujours 0. Donc je crois que t'as une vision assez personnelle de l'imperceptibilite...
 

bah le prochain coup répondez plus tôt, qu'est-ce que vous voulez que je vous dise
m'enfin au moins, je sais maintenant qu'en C++ faut faire comme ça et pas autrement. par contre, pourquoi, je saurai jamais, mais je crois qu'il ne faut pas espérer des gens qui peuplent cette cat la moindre explication de toute façon, jamais vu encore. de la critique, de la critique, toujours de la critique, mais jamais "parceque".

à la différence près que je comptais faire la multiplication avant de faire cette division...
mais là effectivement on se retrouve avec un dépassement de capacité, donc ça n'arrange rien
 
ceci dit, si on sait que RAND_MAX est toujours une valeur très élevée par rapport à la plage max-min, je ne vois pas ce qui empêche de faire ceci :
 
return rand()%(max-min)+min;
 
on perd vraiment peu en homogénéité si max-min est suffisament petit par rapport à RAND_MAX. pour la plupart des cas, en tout cas, moi je me conteterais de la fiabilité de ce générateur de nombre aléatoire.

Avec une moyenne de conneries par post superieure a 1 comment veux tu ne pas recevoir de critiques? Le principe d'un forum c'est pas de raconter des trucs errones en attendant que les autres nous sortent de notre erreur. Ou du moins, pas quand on repond a une demande d'aide...
 
Et pour te repondre :  
- toutes les techniques de generation de nombres aleatoires que tu proposes sont bien jolies mais n'ont aucun fondement mathematique. Quand tu veux tirer une vingtaine de valeurs pour le fun ca peut suffire... mais si tu veux en tirer plusieurs millions et faire des statistiques sur ce que ton programme a calcule en partant de ces valeurs, tu vas te rendre compte des limites de ta methode, parce que tu vas commencer a voir apparaitre un biais. Autrement dit les valeurs que tu vas tirer ne sont pas equiprobables.... jusqu'a preuve du contraire.
 
- quand tu travailles sur des nombres entiers, les instructions utilisees sont celles des nombres entiers. Donc division entiere, entre autres. Il ne faut pas non plus que le resultat d'un calcul intermediaire "deborde".

Effectivement, si max-min est petit par rapport a RAND_MAX, c'est acceptable. Ton truc est juste, mais ca repond pas au probleme.  

Ca, je suis bien d'accord, mais j'ai jamais déboulé en disant que j'avais la science infuse. Je ne lui ai jamais dit "fait ça", j'ai juste suggéré des idées, qui sont d'ailleurs pour la plupart algoritmiques, pas du tout spécifiques au langage (notamment initialiser à l'avance un array de valeurs aléatoires, et mettre en place une solution simple pour les relire de façon pseudo aléatoire, y'a absolument pas l'ombre d'une contrainte de langage dans la suggestion.
Et je reste convaincu que pour un besoin d'optimisation important, si l'équiprobalibité des valeurs aléatoires n'est pas critique, c'est une solution comme une autre, et qui est utilisée à ma connaissance.
 

Effectivement, et c'est pour cette rason que dès mon premier post, ma première phrase a été :

J'ai ensuite donné chacune de mes suggestions en indiquant que je partais du principe que la réponse était "non". Et autant effectivement dans certains cas, cette équiprocité est critique, autant bien souvent on s'en fout comme de l'an 40, on pourrait aussi bien faire un cos() sur l'heure actuelle.
 

Oui, et effectivement, ma première suggesion de division entière est complètement fausse, car le risque de dépassement de capacité est bien trop élevé, je me suis rendu compte de mon erreur dans le RER tout à l'heure
Par contre, ma dernière solution, si effectivement ne donne pas des résultat équiprobables à 100% fonctionne, et pour max-min << RAND_MAX offre un niveau d'équiprobabilité à peine dégradé (seules les valeurs de rand() > RAND_MAX - RAND_MAX%(max-min) vont générer des valeurs non équiprobables, ce qui peut facilement être négligeable pour min-max suffisament petit et RAND_MAX suffisament grand. Ou alors je suis complètement à l'ouest, mais je ne vois pas.

Je pense d'ailleurs à un truc...
 

int hasard(int min, int max)
{
     int rnd = rand();
     if (rnd > RAND_MAX - RAND_MAX%(max-min)) return hasard(min, max);
     return rnd%(max-min)+min;
}

 
Ca doit donner un résultat équiprobable ça si je ne m'abuse.
Mais bon, là je suis bien d'accord que ça a toutes ses chances d'être bien plus lent que le passage par un float du post initial...

Mathematiquement ca me semble correct. Sauf pour le cas degenere ou min=max ... qui peut arriver lors d'une simulation. Et bien sur le cas ou max-min est superieur a RAND_MAX ...

Une fonction rand très rapide et excellente est le Mersenne Twister.

  je vais regarder de ce coté là (merci google )

mais tu utilises de toutes façons déjà un génerateur congruentiel linéaire, qui comme l'a dit Taz est l'un des trucs les plus performants qu'on puisse faire (je suppute que sur ton environnement, ça doit être une bête multiplication, une addition, et un masque binaire car RAND_MAX+1 doit être une puissance de 2). Tu utilises quoi comme OS/compilo ?
 

Mais c'est bien ça le problème.

sur quels éléments tu bases ton "imperceptible" ?

Tout a fait pourri comme expliqué partout sur le net, puisque ça constite à n'utiliser que quelques bits de poids faibles.

C'est pourri, c'est documenté partout, jusque dans la manpage.

Et qu'est-ce que ça change ?
Puisque rand() retourne des valeurs équiprobables, qu'on n'utilise un nombre reduits de bits ou tous les bits, ça ne change rien à l'équiprobailité de du résultat.
 
Quant à la méthode en passant par un float pour faire une division, ça revient au même, puisqu'on utilise ici que les bits de poids fort quand on repasse à une valeur entière (on perds toute l'information décimale).
 
Ca n'a pas de sens ta remarque.
Le seul cas où effectivement c'est justifié, c'est si les résultats de rand() sont équiprobables, mais que chaque entier de l'interval de [0,RAND_MAX] n'a pas de chance équiprobable d'être retourné. A ce moment, c'est la fonction rand() qui doit être écartée complètement, pas du tout la méthode que je propose.

 
Exemple :
 
Si RAND_MAX = 10^9
Et max-min = 10^3
 
Alors la pollution porte sur moins de 1/10^6 des valeurs retournées (et encore si max-min - RAND_MAX%(min-max) est proche de max-min, alors même lors du tirage de valeurs dans l'interval pollué, cette pollution est relativement faible, puisque peu de valeurs de max-min sont écartées par la dernière plage).
Mise à part pour un besoin de valeurs absolument aléatoires, ça peut tout à fait être acceptable comme niveau d'erreur.

 
J'utilise XP et visual studio 2005. la fonction que j'utilise est dans mon 1er post, elle utilise la fonction rand()
Est ce qu'utiliser cette méthode améliorera les choses: http://www-personal.umich.edu/~wag [...] ister.html ?
Il dit sur son site que le  MersenneTwister est plus performant que le rand standard

Imaginons que ton générateur aléatoire donne tour à tour des nombres pairs, puis des nombres impairs (après tout, ce n'est ni équiprobable comme tu le dis, ni garanti que les résultats sont indépendants). Si tu veux faire une simulation de lancer de pièce, tu ferais un modulo 2 (pour récupérer le bit le plus faible), ou tu diviserais par RAND_MAX/2 ?  
 

Nan, je demandais pour te conseiller un profiler. Pour ton environnement, je te recommande d'installer une version d'éval de DevPartner, et de regarder où est-ce que ton code prend vraiment du temps.
Apparemment avec DevPartner Performance Analysis Community Edition, tu as 45 jours gratuits.
 
 
 

ok je vais regarder ca (au passage j'ai déjà repéré qq fuites mémoires... ca doit pas aider )
 
sinon que penses tu de la méthode Mersenne Twister ? j'ai l'impression que je peux gagner là dessus.
 
 

à jamais, j'en ai trop marre de Magic

J'adore la mentalité pourrie de Taz. (tu n'es pas tout seul, ils vont sûrement te défendre)
 
Dans tous les threads que j'ai vu tu te donnes des airs vraiment supérieurs avec des commentaires tels que : "tu dis n'importe quoi", "t'y connais rien" ou encore "casse toi". Mais tu n'apportes aucune réponse, ou alors pas directement.
 
Magic donne effectivement une mauvaise solution, mais il fait l'effort d'en donner une. Si tu n'es pas d'accord, dire "Je ne suis pas d'accord, je pense plutôt que..." est bien plus efficace qu'un "t'y connais rien gros naze"...
Je ne dis pas que tu es mauvais (j'en sais rien, peut-être, de toute façon "bon" est tellement relatif) mais t'as une de ces images quand on te lit... on se dit "tiens, ce gars il doit faire un boulot de merde et il déverse son peu de savoir sur les débutants pour se défrustrer".
 
Maintenant, si t'es capable de répondre à ce message par autre chose qu'un "mais si t'es pas content dégage !", on aura fait un grand pas en avant

Merci de ne pas faire la police et/ou à s'en prendre directement à un forumeur. Si tu as des choses à dire à quelqu'un en particulier, fais-le en MP.
 

 
Non, MagicBuzz est spécialisé dans le n'importe quoi dès qu'il met les pieds dans les cats C et C++.

stop les gars, merci de revenir au sujet svp
 
je vous tiens au courant de mes prochaines modifs (Mersenne Twister + DevPartner pour voir ou ca bloque)

 
tu connais mal MagicBuzz

 
En disant ceci, tu fais ce que tu me reproches de faire : un poil paradoxal
 
Effectivement MagicBuzz donne peut-être (pourquoi je dis "peut-être" ?) des réponses "pourries".  Je n'ai absolument rien de personnel contre Taz. C'était l'art et la manière de lui répondre qui était mise en cause. Qu'on dise qu'il a "tort" pas de problème, mais avant tout faut aider le mec qui a posé la question. Ça sert à quoi de dire "Je sais, toi tu sais pas" si on ne donne pas la réponse ? Surtout sur un sujet aussi "trivial" : c'est pas un exploit de savoir, alors autant aider ceux qui débutent.  Sinon c'est nuisible pour l'ambiance du forum, et ça c'est quand même dommage.
 
Et Boulou, oui, tiens-nous au courant. Pour ma part je suis convaincu que le ralentissement a peu de chances de venir de ta méthode. Ou alors tu nous as pas dit un truc.

Oui, sauf que toi tu n'es pas moderateur...

Je suis passé à SMFT : http://www.math.sci.hiroshima-u.ac [...] index.html
une version amélioré du Mersenne Twister et j'ai vu une bonne différence
par contre je pense que je peux encore amélioré mon prog, voici maintenant ma fonction hasard :

comme vous pouvez le voir j'initialise la seed à chaque fois que je lance la fonction hasard : j'ai essayé de mettre le init_gen_rand(time(NULL));  à un endroit du programme pour y faire appel moins souvent mais ca plante...
 
auriez vous une idée ?  
merci

bah, au debut de ton main, ou plus proprement dans une fonctino d'init générale, ou encore avec un test sur un variable static dasn ta fonction hasard