demande d'explication

Fabien LE LEZ

23/05/2009 à 14:07

On Sat, 23 May 2009 10:19:31 +0200, (Bruno Causse):

ou est l'argument?

Dans le corps de std::random_shuffle<>.

http://www.cplusplus.com/reference/algorithm/random_shuffle/

PasDeSpam

23/05/2009 à 15:13

Fabien LE LEZ wrote:

http://www.cplusplus.com/reference/algorithm/random_shuffle/

oui mon ex vient d'ici.

Dans le corps de std::random_shuffle<>.

je ne suis pas tres bon en anglais :( mais c'est ecris ou?

Fabien LE LEZ

23/05/2009 à 15:59

On Sat, 23 May 2009 15:13:00 +0200, (Bruno Causse):

je ne suis pas tres bon en anglais :(

Ben faut apprendre. Commence donc par le commencement !

De toute façon, l'anglais n'a rien à voir ici :

for (i=2; i<n; ++i) swap (first[i],first[rand(i)]);

-> La fonction passée en paramètre ("rand") est appelée avec, comme
paramètre, i.

Sylvain SF

23/05/2009 à 16:44

Bruno Causse a écrit :

j'utilise ce code mais je le comprend pas :(

// random generator function:
ptrdiff_t myrandom (ptrdiff_t i) { return rand()%i;}

une fonction "myrandom" qui prend comme argument un ptrdiff_t et qui
retourne un ptrdiff_t (pas d'argument par defaut)

où "ptrdiff_t" est un int64 ou un int avec tests de compatibilité
sur architecture 64 bits (compilo MS); en gros c'est un int, soit:

int myrandom(int modulus) { return rand() % modulus; }

la function génère donc un nombre aléatoire (rand()) et
retourne ce nombre borné dans [0..modulus[
(on peut déjà s'attendre à ce que ce modulus soit la
dimension d'un tableau).

// pointer object to it:
ptrdiff_t (*p_myrandom)(ptrdiff_t) = myrandom;

je préfère les typedef:

typedef int (*ModularRandomGenerator)(int);
ModularRandomGenerator p_myrandom = myrandom;

son utilisation
random_shuffle (random_position.begin(), random_position.end(),
p_myrandom);

ou est l'argument?

random_position est un vector<?>, c'est "l'argument" (la variable)
sur lequel random_shuffle shufflera (permutera des éléments).

p_myrandom est aussi un argument, qui donne à random_shuffle, la
fonction à utiliser pour obtenir un aléa; cet aléa définissant
l'index (entre 0 et n-1) de l'élément à permuter avec l'élément n
dans la boucle parcourue par random_shuffle.

Sylvain.

PasDeSpam

23/05/2009 à 18:05

Sylvain SF wrote:

p_myrandom est aussi un argument, qui donne à random_shuffle, la
fonction à utiliser pour obtenir un aléa; cet aléa définissant
l'index (entre 0 et n-1) de l'élément à permuter avec l'élément n
dans la boucle parcourue par random_shuffle.

mais bien sur, (la taille du vector) parfois je suis un peu "lourd"

merci c'est clair

Sylvain SF

23/05/2009 à 18:43

Bruno Causse a écrit :

Sylvain SF wrote:

p_myrandom est aussi un argument, qui donne à random_shuffle, la
fonction à utiliser pour obtenir un aléa; cet aléa définissant
l'index (entre 0 et n-1) de l'élément à permuter avec l'élément n
dans la boucle parcourue par random_shuffle.

mais bien sur, (la taille du vector) parfois je suis un peu "lourd"

je n'étais pas certain de quel argument vous parliez dans
"ou est l'argument".

ici je comprends que c'est l'argument de la fonction décrite
par p_myrandom qui vous manquait.

2 remarques:
- ce n'est pas la taille du vector qui est transmis à myrandom mais
l'indice courant; ainsi lors du parcours des éléments du vector,
l'élement i est échangé avec un des éléments de rang 0 à i (non N)
-- et je ne vois pas de forte raison à cela, on pourrait permuter
chaque élément avec n'importe quel autre (et non pas avec un des
éléments précédents).

- si je considère valide l'implémentation P.J. Plauger de <algorithm>,
cet argument transmis à myrandom ne sert strictement à rien, en effet
un modulo i (l'index en cours, Cf point précédent) est appliqué au
retour de cette fonction.

avec la définition donnée de myrandom, random_shuffle swap les
élements i et ((rand()%i)%i) - ce double % ne servant à rien.
ne sachant pas si www.cplusplus.com se veut une référence stricte
ou un simple guide d'exemples, je ne puis juger du caractère erroné
ou non de leur exemple.
par ailleurs la spéc. immédiate (accompagnant l'implémentation)
de random_shuffle étant inexistante, rien ne permet ici d'affirmer
que l'argument reçu par myrandom doit servir à appliquer un modulo
plutôt que toute autre chose, cela pourrait être une graine (seed)
transmis au générateur pour une éventuelle réinitialisation de sa
séquence.

en application, vous pourriez définir:

int modularRandomGenerator(...){
return rand();
}

typedef int (*ModularRandomGenerator)(...);
ModularRandomGenerator p_myrandom = modularRandomGenerator;

std::vector<long> v;
// fill-in v
random_shuffle(v.begin(), v.end(), p_myrandom);

qui fonctionnera à l'identique.

ou plus simple encore: random_shuffle(v.begin(), v.end());

Sylvain.

Bruno Causse a écrit :

Sylvain SF <sylvain@boiteaspam.info> wrote:

p_myrandom est aussi un argument, qui donne à random_shuffle, la
fonction à utiliser pour obtenir un aléa; cet aléa définissant
l'index (entre 0 et n-1) de l'élément à permuter avec l'élément n
dans la boucle parcourue par random_shuffle.

mais bien sur, (la taille du vector) parfois je suis un peu "lourd"

je n'étais pas certain de quel argument vous parliez dans
"ou est l'argument".

ici je comprends que c'est l'argument de la fonction décrite
par p_myrandom qui vous manquait.

2 remarques:
- ce n'est pas la taille du vector qui est transmis à myrandom mais
l'indice courant; ainsi lors du parcours des éléments du vector,
l'élement i est échangé avec un des éléments de rang 0 à i (non N)
-- et je ne vois pas de forte raison à cela, on pourrait permuter
chaque élément avec n'importe quel autre (et non pas avec un des
éléments précédents).

- si je considère valide l'implémentation P.J. Plauger de <algorithm>,
cet argument transmis à myrandom ne sert strictement à rien, en effet
un modulo i (l'index en cours, Cf point précédent) est appliqué au
retour de cette fonction.

avec la définition donnée de myrandom, random_shuffle swap les
élements i et ((rand()%i)%i) - ce double % ne servant à rien.
ne sachant pas si www.cplusplus.com se veut une référence stricte
ou un simple guide d'exemples, je ne puis juger du caractère erroné
ou non de leur exemple.
par ailleurs la spéc. immédiate (accompagnant l'implémentation)
de random_shuffle étant inexistante, rien ne permet ici d'affirmer
que l'argument reçu par myrandom doit servir à appliquer un modulo
plutôt que toute autre chose, cela pourrait être une graine (seed)
transmis au générateur pour une éventuelle réinitialisation de sa
séquence.

en application, vous pourriez définir:

int modularRandomGenerator(...){
return rand();
}

typedef int (*ModularRandomGenerator)(...);
ModularRandomGenerator p_myrandom = modularRandomGenerator;

std::vector<long> v;
// fill-in v
random_shuffle(v.begin(), v.end(), p_myrandom);

qui fonctionnera à l'identique.

ou plus simple encore: random_shuffle(v.begin(), v.end());

Sylvain.

Vous avez filtré cet utilisateur ! Consultez son message

Bruno Causse a écrit :

Sylvain SF wrote:

p_myrandom est aussi un argument, qui donne à random_shuffle, la
fonction à utiliser pour obtenir un aléa; cet aléa définissant
l'index (entre 0 et n-1) de l'élément à permuter avec l'élément n
dans la boucle parcourue par random_shuffle.

mais bien sur, (la taille du vector) parfois je suis un peu "lourd"

je n'étais pas certain de quel argument vous parliez dans
"ou est l'argument".

ici je comprends que c'est l'argument de la fonction décrite
par p_myrandom qui vous manquait.

2 remarques:
- ce n'est pas la taille du vector qui est transmis à myrandom mais
l'indice courant; ainsi lors du parcours des éléments du vector,
l'élement i est échangé avec un des éléments de rang 0 à i (non N)
-- et je ne vois pas de forte raison à cela, on pourrait permuter
chaque élément avec n'importe quel autre (et non pas avec un des
éléments précédents).

- si je considère valide l'implémentation P.J. Plauger de <algorithm>,
cet argument transmis à myrandom ne sert strictement à rien, en effet
un modulo i (l'index en cours, Cf point précédent) est appliqué au
retour de cette fonction.

avec la définition donnée de myrandom, random_shuffle swap les
élements i et ((rand()%i)%i) - ce double % ne servant à rien.
ne sachant pas si www.cplusplus.com se veut une référence stricte
ou un simple guide d'exemples, je ne puis juger du caractère erroné
ou non de leur exemple.
par ailleurs la spéc. immédiate (accompagnant l'implémentation)
de random_shuffle étant inexistante, rien ne permet ici d'affirmer
que l'argument reçu par myrandom doit servir à appliquer un modulo
plutôt que toute autre chose, cela pourrait être une graine (seed)
transmis au générateur pour une éventuelle réinitialisation de sa
séquence.

en application, vous pourriez définir:

int modularRandomGenerator(...){
return rand();
}

typedef int (*ModularRandomGenerator)(...);
ModularRandomGenerator p_myrandom = modularRandomGenerator;

std::vector<long> v;
// fill-in v
random_shuffle(v.begin(), v.end(), p_myrandom);

qui fonctionnera à l'identique.

ou plus simple encore: random_shuffle(v.begin(), v.end());

Sylvain.

Sylvain SF

23/05/2009 à 22:11

Sylvain SF a écrit :

- si je considère valide l'implémentation P.J. Plauger de <algorithm>,
cet argument transmis à myrandom ne sert strictement à rien

en fait si, quand même.

ce point illustre d'ailleurs bien 2 trucs plutôt agaçant de la STL:

1: <http://www.cplusplus.com/reference/algorithm/random_shuffle/>
prétends illustrer le bon usage de la STL (enfin que pense qu'il
souhaite s'inscrire dans cette démarche) et utilise un affreux
typedef implicite:

<quote>
// random generator function:
ptrdiff_t myrandom(ptrdiff_t i) { return rand() % i;}
// pointer object to it:
ptrdiff_t (*p_myrandom)(ptrdiff_t) = myrandom;
</quote>

pour faire
random_shuffle(myvector.begin(), myvector.end(), p_myrandom);

le bon usage de la STL voudrait plutôt:

ptrdiff_t myrandom(ptrdiff_t i) { return rand()%i; }

random_shuffle(myvector.begin(), myvector.end(),
pointer_to_unary_function<int, int>(myrandom));

où pointer_to_unary_function vérifiera correctement la
définition et refuserait mon int modularRandomGenerator(...).

2: selon <http://www.sgi.com/tech/stl/RandomNumberGenerator.html>
le contrat d'une fonction /Random Number Generator/ est de retourner
un nombre compris entre 0 et l'argument reçu.

pourquoi alors l'implémentation de random_shuffle (celle de Plauger)
perd son temps à refaire un modulo sur le nombre retourné ?
qu'est-ce que ce système où on fixe un contrat et on opère comme
s'il n'était pas respecté ? où est le bon sens et la charge du
respect du contrat ? et non, je refuse d'emblée le "c'est plus
sur" ainsi, "2 tests valent mieux qu'un" et autres enfantillages.

Sylvain.

James Kanze

24/05/2009 à 10:26

On May 23, 10:11 pm, Sylvain SF wrote:

Sylvain SF a écrit :
> - si je considère valide l'implémentation P.J. Plauger de
> <algorithm>, cet argument transmis à myrandom ne sert
> strictement à rien

en fait si, quand même.

ce point illustre d'ailleurs bien 2 trucs plutôt agaçant de la STL:

1:
<http://www.cplusplus.com/reference/algorithm/random_shuffle/>
prétends illustrer le bon usage de la STL (enfin que pense
qu'il souhaite s'inscrire dans cette démarche) et utilise un
affreux typedef implicite:

<quote>
// random generator function:
ptrdiff_t myrandom(ptrdiff_t i) { return rand() % i;}
// pointer object to it:
ptrdiff_t (*p_myrandom)(ptrdiff_t) = myrandom;
</quote>

pour faire
random_shuffle(myvector.begin(), myvector.end(), p_myrandom);

le bon usage de la STL voudrait plutôt:

ptrdiff_t myrandom(ptrdiff_t i) { return rand()%i; }

random_shuffle(myvector.begin(), myvector.end(),
pointer_to_unary_function<int, int>(myrandom));

Pourquoi ?

D'abord, la STL a été conçu de façon qu'on puisse utiliser les
fonctions (c-à-d les pointeurs à des fonctions) pratiquement
partout où on peut utiliser les objets fonctionnels. En fait, la
philosophie est plutôt l'inverse : les algorithmes prennent une
fonction, que grace aux templates on peut remplacer par un objet
fonctionnel quelconque.

Il est parfois conseillé d'utiliser les objets fonctionnels pour
des raisons de vitesse (d'exécution). Si le compilateur sait la
fonction qui doit être appelée, il peut la générer en ligne.
Mais pour que ce soit efficace, il faudrait que la fonction
appelée soit determinée par le type, sans autres indirections.
Il s'en suit que l'idiome plus ou moins classique serait :

struct MyRandom
{
ptrdiff_t operator()( ptrdiff_t i )
{
return rand() % i ;
}
} ;

// ...
random_shuffle( v.begin(), v.end(), MyRandom() ) ;

Sinon, on s'en passerait du typedef en général. Même avec la
fonction,
random_shuffle( v.begin(), v.end(), myRandom ) ;
suffit largement, et est plus idiomatique.

où pointer_to_unary_function vérifiera correctement la
définition et refuserait mon int modularRandomGenerator(...).

Ce qui introduit un contraint sans intérêt. (Voir ci-dessus, sur
l'utilisation de rand().)

2: selon <http://www.sgi.com/tech/stl/RandomNumberGenerator.html>
le contrat d'une fonction /Random Number Generator/ est de retourner
un nombre compris entre 0 et l'argument reçu.

pourquoi alors l'implémentation de random_shuffle (celle de
Plauger) perd son temps à refaire un modulo sur le nombre
retourné ?

C'est probablement lié à l'histoire.

qu'est-ce que ce système où on fixe un contrat et
on opère comme s'il n'était pas respecté ?

Est-ce que le contrat a toujours été tel ? Je verrais bien un
cas où la première version n'avait pas le paramètre, et que
quand on l'a ajouté, on a oublié à supprimer le modulo.

où est le bon sens et la charge du respect du contrat ? et
non, je refuse d'emblée le "c'est plus sur" ainsi, "2 tests
valent mieux qu'un" et autres enfantillages.

Cet argument vaudrait s'il y avait un assert. Autrement non.

Une dernière remarque : rand() n'est pas un bon choix ici comme
fonction de génération aléatoire. Selon la norme, rand() renvoie
une valeur entre 0 et RAND_MAX, et RAND_MAX n'est pas forcément
supérieur à 32767. Alors, pour peut que le tableau devient un
peu grand... (Et évidemment, un simple modulo n'est pas
suffisant pour limiter la portée non plus.)

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

On May 23, 10:11 pm, Sylvain SF <sylv...@boiteaspam.info> wrote:

Sylvain SF a écrit :
> - si je considère valide l'implémentation P.J. Plauger de
> <algorithm>, cet argument transmis à myrandom ne sert
> strictement à rien

en fait si, quand même.

ce point illustre d'ailleurs bien 2 trucs plutôt agaçant de la STL:

1:
<http://www.cplusplus.com/reference/algorithm/random_shuffle/>
prétends illustrer le bon usage de la STL (enfin que pense
qu'il souhaite s'inscrire dans cette démarche) et utilise un
affreux typedef implicite:

<quote>
// random generator function:
ptrdiff_t myrandom(ptrdiff_t i) { return rand() % i;}
// pointer object to it:
ptrdiff_t (*p_myrandom)(ptrdiff_t) = myrandom;
</quote>

pour faire
random_shuffle(myvector.begin(), myvector.end(), p_myrandom);

le bon usage de la STL voudrait plutôt:

ptrdiff_t myrandom(ptrdiff_t i) { return rand()%i; }

random_shuffle(myvector.begin(), myvector.end(),
pointer_to_unary_function<int, int>(myrandom));

Pourquoi ?

D'abord, la STL a été conçu de façon qu'on puisse utiliser les
fonctions (c-à-d les pointeurs à des fonctions) pratiquement
partout où on peut utiliser les objets fonctionnels. En fait, la
philosophie est plutôt l'inverse : les algorithmes prennent une
fonction, que grace aux templates on peut remplacer par un objet
fonctionnel quelconque.

Il est parfois conseillé d'utiliser les objets fonctionnels pour
des raisons de vitesse (d'exécution). Si le compilateur sait la
fonction qui doit être appelée, il peut la générer en ligne.
Mais pour que ce soit efficace, il faudrait que la fonction
appelée soit determinée par le type, sans autres indirections.
Il s'en suit que l'idiome plus ou moins classique serait :

struct MyRandom
{
ptrdiff_t operator()( ptrdiff_t i )
{
return rand() % i ;
}
} ;

// ...
random_shuffle( v.begin(), v.end(), MyRandom() ) ;

Sinon, on s'en passerait du typedef en général. Même avec la
fonction,
random_shuffle( v.begin(), v.end(), myRandom ) ;
suffit largement, et est plus idiomatique.

où pointer_to_unary_function vérifiera correctement la
définition et refuserait mon int modularRandomGenerator(...).

Ce qui introduit un contraint sans intérêt. (Voir ci-dessus, sur
l'utilisation de rand().)

2: selon <http://www.sgi.com/tech/stl/RandomNumberGenerator.html>
le contrat d'une fonction /Random Number Generator/ est de retourner
un nombre compris entre 0 et l'argument reçu.

pourquoi alors l'implémentation de random_shuffle (celle de
Plauger) perd son temps à refaire un modulo sur le nombre
retourné ?

C'est probablement lié à l'histoire.

qu'est-ce que ce système où on fixe un contrat et
on opère comme s'il n'était pas respecté ?

Est-ce que le contrat a toujours été tel ? Je verrais bien un
cas où la première version n'avait pas le paramètre, et que
quand on l'a ajouté, on a oublié à supprimer le modulo.

où est le bon sens et la charge du respect du contrat ? et
non, je refuse d'emblée le "c'est plus sur" ainsi, "2 tests
valent mieux qu'un" et autres enfantillages.

Cet argument vaudrait s'il y avait un assert. Autrement non.

Une dernière remarque : rand() n'est pas un bon choix ici comme
fonction de génération aléatoire. Selon la norme, rand() renvoie
une valeur entre 0 et RAND_MAX, et RAND_MAX n'est pas forcément
supérieur à 32767. Alors, pour peut que le tableau devient un
peu grand... (Et évidemment, un simple modulo n'est pas
suffisant pour limiter la portée non plus.)

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Vous avez filtré cet utilisateur ! Consultez son message

On May 23, 10:11 pm, Sylvain SF wrote:

Sylvain SF a écrit :
> - si je considère valide l'implémentation P.J. Plauger de
> <algorithm>, cet argument transmis à myrandom ne sert
> strictement à rien

en fait si, quand même.

ce point illustre d'ailleurs bien 2 trucs plutôt agaçant de la STL:

1:
<http://www.cplusplus.com/reference/algorithm/random_shuffle/>
prétends illustrer le bon usage de la STL (enfin que pense
qu'il souhaite s'inscrire dans cette démarche) et utilise un
affreux typedef implicite:

<quote>
// random generator function:
ptrdiff_t myrandom(ptrdiff_t i) { return rand() % i;}
// pointer object to it:
ptrdiff_t (*p_myrandom)(ptrdiff_t) = myrandom;
</quote>

pour faire
random_shuffle(myvector.begin(), myvector.end(), p_myrandom);

le bon usage de la STL voudrait plutôt:

ptrdiff_t myrandom(ptrdiff_t i) { return rand()%i; }

random_shuffle(myvector.begin(), myvector.end(),
pointer_to_unary_function<int, int>(myrandom));

Pourquoi ?

D'abord, la STL a été conçu de façon qu'on puisse utiliser les
fonctions (c-à-d les pointeurs à des fonctions) pratiquement
partout où on peut utiliser les objets fonctionnels. En fait, la
philosophie est plutôt l'inverse : les algorithmes prennent une
fonction, que grace aux templates on peut remplacer par un objet
fonctionnel quelconque.

Il est parfois conseillé d'utiliser les objets fonctionnels pour
des raisons de vitesse (d'exécution). Si le compilateur sait la
fonction qui doit être appelée, il peut la générer en ligne.
Mais pour que ce soit efficace, il faudrait que la fonction
appelée soit determinée par le type, sans autres indirections.
Il s'en suit que l'idiome plus ou moins classique serait :

struct MyRandom
{
ptrdiff_t operator()( ptrdiff_t i )
{
return rand() % i ;
}
} ;

// ...
random_shuffle( v.begin(), v.end(), MyRandom() ) ;

Sinon, on s'en passerait du typedef en général. Même avec la
fonction,
random_shuffle( v.begin(), v.end(), myRandom ) ;
suffit largement, et est plus idiomatique.

où pointer_to_unary_function vérifiera correctement la
définition et refuserait mon int modularRandomGenerator(...).

Ce qui introduit un contraint sans intérêt. (Voir ci-dessus, sur
l'utilisation de rand().)

2: selon <http://www.sgi.com/tech/stl/RandomNumberGenerator.html>
le contrat d'une fonction /Random Number Generator/ est de retourner
un nombre compris entre 0 et l'argument reçu.

pourquoi alors l'implémentation de random_shuffle (celle de
Plauger) perd son temps à refaire un modulo sur le nombre
retourné ?

C'est probablement lié à l'histoire.

qu'est-ce que ce système où on fixe un contrat et
on opère comme s'il n'était pas respecté ?

Est-ce que le contrat a toujours été tel ? Je verrais bien un
cas où la première version n'avait pas le paramètre, et que
quand on l'a ajouté, on a oublié à supprimer le modulo.

où est le bon sens et la charge du respect du contrat ? et
non, je refuse d'emblée le "c'est plus sur" ainsi, "2 tests
valent mieux qu'un" et autres enfantillages.

Cet argument vaudrait s'il y avait un assert. Autrement non.

Une dernière remarque : rand() n'est pas un bon choix ici comme
fonction de génération aléatoire. Selon la norme, rand() renvoie
une valeur entre 0 et RAND_MAX, et RAND_MAX n'est pas forcément
supérieur à 32767. Alors, pour peut que le tableau devient un
peu grand... (Et évidemment, un simple modulo n'est pas
suffisant pour limiter la portée non plus.)

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

James Kanze

24/05/2009 à 10:36

On May 23, 6:43 pm, Sylvain SF wrote:

Bruno Causse a écrit :

2 remarques:
- ce n'est pas la taille du vector qui est transmis à myrandom mais
l'indice courant; ainsi lors du parcours des éléments du vector,
l'élement i est échangé avec un des éléments de rang 0 à i (non N)
-- et je ne vois pas de forte raison à cela, on pourrait permuter
chaque élément avec n'importe quel autre (et non pas avec un des
éléments précédents).

Pour avoir une distribution aléatoire. Si à chaque fois tu
échanges un élément avec n'importe quel autre, tu vas avoir n^n
différents mélanges. Or, il y a exactement n! ordres possible.
Au moins que n! est facteur de n^n (ce qui n'est pas possible),
il y aurait certains ordres qui ressortent plus que d'autres.

[...]

Par ailleurs la spéc. immédiate (accompagnant
l'implémentation) de random_shuffle étant inexistante, rien
ne permet ici d'affirmer que l'argument reçu par myrandom
doit servir à appliquer un modulo plutôt que toute autre
chose, cela pourrait être une graine (seed) transmis au
générateur pour une éventuelle réinitialisation de sa
séquence.

La norme précise bien le contrat de la fonction.

en application, vous pourriez définir:

int modularRandomGenerator(...){
return rand();
}

Et tu aurais un comportement indéfini. (Mais évidemment, comme
j'ai dit ailleurs, si tu utilises rand(), tu as déjà un
comportement dégénéré. La norme exige que la valeur de rétour
soit une valeur choisie aléatoirement dans la portée [0 ; n[.
Or, si n est supérieur à RAND_MAX, ce ne serait pas le cas.)

typedef int (*ModularRandomGenerator)(...);
ModularRandomGenerator p_myrandom = modularRandomGenerator;

std::vector<long> v;
// fill-in v
random_shuffle(v.begin(), v.end(), p_myrandom);

qui fonctionnera à l'identique.

ou plus simple encore: random_shuffle(v.begin(), v.end());

Qui ne marche pas correctement avec toutes les implémentations
(g++, par exemple).

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

On May 23, 6:43 pm, Sylvain SF <sylv...@boiteaspam.info> wrote:

Bruno Causse a écrit :

2 remarques:
- ce n'est pas la taille du vector qui est transmis à myrandom mais
l'indice courant; ainsi lors du parcours des éléments du vector,
l'élement i est échangé avec un des éléments de rang 0 à i (non N)
-- et je ne vois pas de forte raison à cela, on pourrait permuter
chaque élément avec n'importe quel autre (et non pas avec un des
éléments précédents).

Pour avoir une distribution aléatoire. Si à chaque fois tu
échanges un élément avec n'importe quel autre, tu vas avoir n^n
différents mélanges. Or, il y a exactement n! ordres possible.
Au moins que n! est facteur de n^n (ce qui n'est pas possible),
il y aurait certains ordres qui ressortent plus que d'autres.

[...]

Par ailleurs la spéc. immédiate (accompagnant
l'implémentation) de random_shuffle étant inexistante, rien
ne permet ici d'affirmer que l'argument reçu par myrandom
doit servir à appliquer un modulo plutôt que toute autre
chose, cela pourrait être une graine (seed) transmis au
générateur pour une éventuelle réinitialisation de sa
séquence.

La norme précise bien le contrat de la fonction.

en application, vous pourriez définir:

int modularRandomGenerator(...){
return rand();
}

Et tu aurais un comportement indéfini. (Mais évidemment, comme
j'ai dit ailleurs, si tu utilises rand(), tu as déjà un
comportement dégénéré. La norme exige que la valeur de rétour
soit une valeur choisie aléatoirement dans la portée [0 ; n[.
Or, si n est supérieur à RAND_MAX, ce ne serait pas le cas.)

typedef int (*ModularRandomGenerator)(...);
ModularRandomGenerator p_myrandom = modularRandomGenerator;

std::vector<long> v;
// fill-in v
random_shuffle(v.begin(), v.end(), p_myrandom);

qui fonctionnera à l'identique.

ou plus simple encore: random_shuffle(v.begin(), v.end());

Qui ne marche pas correctement avec toutes les implémentations
(g++, par exemple).

--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Vous avez filtré cet utilisateur ! Consultez son message

On May 23, 6:43 pm, Sylvain SF wrote:

Bruno Causse a écrit :

2 remarques:
- ce n'est pas la taille du vector qui est transmis à myrandom mais
l'indice courant; ainsi lors du parcours des éléments du vector,
l'élement i est échangé avec un des éléments de rang 0 à i (non N)
-- et je ne vois pas de forte raison à cela, on pourrait permuter
chaque élément avec n'importe quel autre (et non pas avec un des
éléments précédents).

Pour avoir une distribution aléatoire. Si à chaque fois tu
échanges un élément avec n'importe quel autre, tu vas avoir n^n
différents mélanges. Or, il y a exactement n! ordres possible.
Au moins que n! est facteur de n^n (ce qui n'est pas possible),
il y aurait certains ordres qui ressortent plus que d'autres.

[...]

Par ailleurs la spéc. immédiate (accompagnant
l'implémentation) de random_shuffle étant inexistante, rien
ne permet ici d'affirmer que l'argument reçu par myrandom
doit servir à appliquer un modulo plutôt que toute autre
chose, cela pourrait être une graine (seed) transmis au
générateur pour une éventuelle réinitialisation de sa
séquence.

La norme précise bien le contrat de la fonction.

en application, vous pourriez définir:

int modularRandomGenerator(...){
return rand();
}

Et tu aurais un comportement indéfini. (Mais évidemment, comme
j'ai dit ailleurs, si tu utilises rand(), tu as déjà un
comportement dégénéré. La norme exige que la valeur de rétour
soit une valeur choisie aléatoirement dans la portée [0 ; n[.
Or, si n est supérieur à RAND_MAX, ce ne serait pas le cas.)

typedef int (*ModularRandomGenerator)(...);
ModularRandomGenerator p_myrandom = modularRandomGenerator;

std::vector<long> v;
// fill-in v
random_shuffle(v.begin(), v.end(), p_myrandom);

qui fonctionnera à l'identique.

ou plus simple encore: random_shuffle(v.begin(), v.end());

Qui ne marche pas correctement avec toutes les implémentations
(g++, par exemple).

--
James Kanze (GABI Software) email:
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Richard Delorme

24/05/2009 à 17:52

James Kanze a écrit :

2 remarques:
- ce n'est pas la taille du vector qui est transmis à myrandom mais
l'indice courant; ainsi lors du parcours des éléments du vector,
l'élement i est échangé avec un des éléments de rang 0 à i (non N)
-- et je ne vois pas de forte raison à cela, on pourrait permuter
chaque élément avec n'importe quel autre (et non pas avec un des
éléments précédents).

Pour avoir une distribution aléatoire. Si à chaque fois tu
échanges un élément avec n'importe quel autre, tu vas avoir n^n
différents mélanges. Or, il y a exactement n! ordres possible.
Au moins que n! est facteur de n^n (ce qui n'est pas possible),
il y aurait certains ordres qui ressortent plus que d'autres.

On peut appliquer le même raisonnement à rand() % n; qui ne retourne un
nombre (pseudo-)aléatoire entre [0, n[, que si (RAND_MAX + 1) est un
multiple de n. Dans le cas extrème ou n vaut RAND_MAX, 0 a deux fois
plus de chance d'être tiré qu'un nombre parmi 1 à RAND_MAX - 1.

--
Richard

demande d'explication

10 réponses

Veuillez sélectionner un problème