Je recherche une methode "optimisee" (minimum de memoire et de temps)
d'inversion d'un tableau. J'avoue j'ai deja vu ca en cours d'algoje crois
mais ca fait un petit bout de temps maintenant.
Pour simplifier cela revient a ce ke mon tableau = {0,1,2,3,4,5} devienne
{5,4,3,2,1,0}.
A dire vrai je vais effectuer cette operation sur des blocs memoires mais
comme ca revient au meme ....
après, tu peux effectivement faire cela sur place, genre (en langage C puisqu'on est sur le groupe) :
for(i = 0 ; i < n / 2 ; i ++) { void * tmp;
J'ai raté une subtilité là. C'est quoi ce void* ? C'était pas un tableau d'entier ?
le type n'était pas précisé (vu que ce n'était pas une question sur le langage C), c'était peut-être des Int java (pointeurs sur entiers alloués)
tmp = tab[i]; tab[i] = tab[n - i - 1]; tab[n - i - 1] = tmp; }
après, appeler cela de l'optimisation, je trouve ça un peu gros.
Disons que j'ai du mal à voir comment optimiser le renversement d'un tableau. On a un algo trivial en O(N), et je vois mal comment arriver à moins. Si on veut faire de la micro optimisation (éviter l'addition implicite dans tab[i] et le cacul 'n-i'), on doit pouvoir faire:
int tmp; for(deb=tab, end=tab+n;deb<tab;deb++, tab--){ tmp=*deb; *deb=*end; *end=tmp; } Mais je suis même pas sur qu'on gagne quoi que ce soit de mesurable.
clair ! imagine que le compilateur s'amuse à détecter cela et fasse ta transformation. Et même, je pense que la soustraction (n - i) doit être négligeable devant le stockage de l'entier (* deb = end; * end = tmp;), même si cela peut se faire en cache.
-- DINH V. Hoa,
"ça arrache tout !" -- CG
DINH Viêt Hoà wrote:
après, tu peux effectivement faire cela sur place, genre (en langage C
puisqu'on est sur le groupe) :
for(i = 0 ; i < n / 2 ; i ++) {
void * tmp;
J'ai raté une subtilité là. C'est quoi ce void* ?
C'était pas un tableau d'entier ?
le type n'était pas précisé (vu que ce n'était pas une question sur le
langage C), c'était peut-être des Int java (pointeurs sur entiers alloués)
tmp = tab[i];
tab[i] = tab[n - i - 1];
tab[n - i - 1] = tmp;
}
après, appeler cela de l'optimisation, je trouve ça un peu gros.
Disons que j'ai du mal à voir comment optimiser le renversement
d'un tableau. On a un algo trivial en O(N), et je vois mal comment
arriver à moins.
Si on veut faire de la micro optimisation (éviter l'addition
implicite dans tab[i] et le cacul 'n-i'), on doit pouvoir
faire:
int tmp;
for(deb=tab, end=tab+n;deb<tab;deb++, tab--){
tmp=*deb;
*deb=*end;
*end=tmp;
}
Mais je suis même pas sur qu'on gagne quoi que ce soit de mesurable.
clair ! imagine que le compilateur s'amuse à détecter cela et fasse ta
transformation. Et même, je pense que la soustraction (n - i) doit être
négligeable devant le stockage de l'entier (* deb = end; * end = tmp;),
même si cela peut se faire en cache.
après, tu peux effectivement faire cela sur place, genre (en langage C puisqu'on est sur le groupe) :
for(i = 0 ; i < n / 2 ; i ++) { void * tmp;
J'ai raté une subtilité là. C'est quoi ce void* ? C'était pas un tableau d'entier ?
le type n'était pas précisé (vu que ce n'était pas une question sur le langage C), c'était peut-être des Int java (pointeurs sur entiers alloués)
tmp = tab[i]; tab[i] = tab[n - i - 1]; tab[n - i - 1] = tmp; }
après, appeler cela de l'optimisation, je trouve ça un peu gros.
Disons que j'ai du mal à voir comment optimiser le renversement d'un tableau. On a un algo trivial en O(N), et je vois mal comment arriver à moins. Si on veut faire de la micro optimisation (éviter l'addition implicite dans tab[i] et le cacul 'n-i'), on doit pouvoir faire:
int tmp; for(deb=tab, end=tab+n;deb<tab;deb++, tab--){ tmp=*deb; *deb=*end; *end=tmp; } Mais je suis même pas sur qu'on gagne quoi que ce soit de mesurable.
clair ! imagine que le compilateur s'amuse à détecter cela et fasse ta transformation. Et même, je pense que la soustraction (n - i) doit être négligeable devant le stockage de l'entier (* deb = end; * end = tmp;), même si cela peut se faire en cache.
-- DINH V. Hoa,
"ça arrache tout !" -- CG
DINH Viêt Hoà
Va falloir que tu expliques sur quelle machine réelle l'économie d'une variable de type entier permet de considérer que l'ajout de 3 opérations arithmétiques entières par itération de boucle constitue une optimisation.
je crois que c'est ce que je sous-entendai :)
-- DINH V. Hoa,
"ça arrache tout !" -- CG
Va falloir que tu expliques sur quelle machine réelle
l'économie d'une variable de type entier permet de considérer
que l'ajout de 3 opérations arithmétiques entières par itération
de boucle constitue une optimisation.
Va falloir que tu expliques sur quelle machine réelle l'économie d'une variable de type entier permet de considérer que l'ajout de 3 opérations arithmétiques entières par itération de boucle constitue une optimisation.
je crois que c'est ce que je sous-entendai :)
-- DINH V. Hoa,
"ça arrache tout !" -- CG
Marc Boyer
DINH Viêt Hoà wrote:
Va falloir que tu expliques sur quelle machine réelle l'économie d'une variable de type entier permet de considérer que l'ajout de 3 opérations arithmétiques entières par itération de boucle constitue une optimisation.
je crois que c'est ce que je sous-entendai :)
Mais j'étais pas sur, à la lecture de sa réponse, que l'OP est compris ton sous-entendu.
Marc Boyer -- Lying for having sex or lying for making war? Trust US presidents :-(
DINH Viêt Hoà wrote:
Va falloir que tu expliques sur quelle machine réelle
l'économie d'une variable de type entier permet de considérer
que l'ajout de 3 opérations arithmétiques entières par itération
de boucle constitue une optimisation.
je crois que c'est ce que je sous-entendai :)
Mais j'étais pas sur, à la lecture de sa réponse, que
l'OP est compris ton sous-entendu.
Marc Boyer
--
Lying for having sex or lying for making war? Trust US presidents :-(
Va falloir que tu expliques sur quelle machine réelle l'économie d'une variable de type entier permet de considérer que l'ajout de 3 opérations arithmétiques entières par itération de boucle constitue une optimisation.
je crois que c'est ce que je sous-entendai :)
Mais j'étais pas sur, à la lecture de sa réponse, que l'OP est compris ton sous-entendu.
Marc Boyer -- Lying for having sex or lying for making war? Trust US presidents :-(
Marc Boyer
DINH Viêt Hoà wrote:
DINH Viêt Hoà wrote:
après, tu peux effectivement faire cela sur place, genre (en langage C puisqu'on est sur le groupe) :
for(i = 0 ; i < n / 2 ; i ++) { void * tmp;
J'ai raté une subtilité là. C'est quoi ce void* ? C'était pas un tableau d'entier ?
le type n'était pas précisé (vu que ce n'était pas une question sur le langage C), c'était peut-être des Int java (pointeurs sur entiers alloués)
OK, j'ai lu trop rapidement le message initial, je croyais qu'on parlais d'entier.
Disons que j'ai du mal à voir comment optimiser le renversement d'un tableau. On a un algo trivial en O(N), et je vois mal comment arriver à moins. Si on veut faire de la micro optimisation (éviter l'addition implicite dans tab[i] et le cacul 'n-i'), on doit pouvoir faire:
int tmp; for(deb=tab, end=tab+n;deb<tab;deb++, tab--){ tmp=*deb; *deb=*end; *end=tmp; } Mais je suis même pas sur qu'on gagne quoi que ce soit de mesurable.
clair ! imagine que le compilateur s'amuse à détecter cela et fasse ta transformation.
Oui, j'ai cru comprendre que certains compilateurs répandus faisaient ça tout seuls comme des grands.
Et même, je pense que la soustraction (n - i) doit être négligeable devant le stockage de l'entier (* deb = end; * end = tmp;), même si cela peut se faire en cache.
Ca fait un bout de temps que j'ai renonçé à deviner ou sont les goulots dans les processeurs modernes. Je raisonne en algorithmique, je conçois un code maintenable, puis ensuite, si on se plaint de perfs, je regarde de plus prêt.
Marc Boyer -- Lying for having sex or lying for making war? Trust US presidents :-(
DINH Viêt Hoà wrote:
DINH Viêt Hoà wrote:
après, tu peux effectivement faire cela sur place, genre (en langage C
puisqu'on est sur le groupe) :
for(i = 0 ; i < n / 2 ; i ++) {
void * tmp;
J'ai raté une subtilité là. C'est quoi ce void* ?
C'était pas un tableau d'entier ?
le type n'était pas précisé (vu que ce n'était pas une question sur le
langage C), c'était peut-être des Int java (pointeurs sur entiers alloués)
OK, j'ai lu trop rapidement le message initial, je croyais qu'on
parlais d'entier.
Disons que j'ai du mal à voir comment optimiser le renversement
d'un tableau. On a un algo trivial en O(N), et je vois mal comment
arriver à moins.
Si on veut faire de la micro optimisation (éviter l'addition
implicite dans tab[i] et le cacul 'n-i'), on doit pouvoir
faire:
int tmp;
for(deb=tab, end=tab+n;deb<tab;deb++, tab--){
tmp=*deb;
*deb=*end;
*end=tmp;
}
Mais je suis même pas sur qu'on gagne quoi que ce soit de mesurable.
clair ! imagine que le compilateur s'amuse à détecter cela et fasse ta
transformation.
Oui, j'ai cru comprendre que certains compilateurs répandus faisaient
ça tout seuls comme des grands.
Et même, je pense que la soustraction (n - i) doit être
négligeable devant le stockage de l'entier (* deb = end; * end = tmp;),
même si cela peut se faire en cache.
Ca fait un bout de temps que j'ai renonçé à deviner ou sont les
goulots dans les processeurs modernes. Je raisonne en algorithmique,
je conçois un code maintenable, puis ensuite, si on se plaint
de perfs, je regarde de plus prêt.
Marc Boyer
--
Lying for having sex or lying for making war? Trust US presidents :-(
après, tu peux effectivement faire cela sur place, genre (en langage C puisqu'on est sur le groupe) :
for(i = 0 ; i < n / 2 ; i ++) { void * tmp;
J'ai raté une subtilité là. C'est quoi ce void* ? C'était pas un tableau d'entier ?
le type n'était pas précisé (vu que ce n'était pas une question sur le langage C), c'était peut-être des Int java (pointeurs sur entiers alloués)
OK, j'ai lu trop rapidement le message initial, je croyais qu'on parlais d'entier.
Disons que j'ai du mal à voir comment optimiser le renversement d'un tableau. On a un algo trivial en O(N), et je vois mal comment arriver à moins. Si on veut faire de la micro optimisation (éviter l'addition implicite dans tab[i] et le cacul 'n-i'), on doit pouvoir faire:
int tmp; for(deb=tab, end=tab+n;deb<tab;deb++, tab--){ tmp=*deb; *deb=*end; *end=tmp; } Mais je suis même pas sur qu'on gagne quoi que ce soit de mesurable.
clair ! imagine que le compilateur s'amuse à détecter cela et fasse ta transformation.
Oui, j'ai cru comprendre que certains compilateurs répandus faisaient ça tout seuls comme des grands.
Et même, je pense que la soustraction (n - i) doit être négligeable devant le stockage de l'entier (* deb = end; * end = tmp;), même si cela peut se faire en cache.
Ca fait un bout de temps que j'ai renonçé à deviner ou sont les goulots dans les processeurs modernes. Je raisonne en algorithmique, je conçois un code maintenable, puis ensuite, si on se plaint de perfs, je regarde de plus prêt.
Marc Boyer -- Lying for having sex or lying for making war? Trust US presidents :-(
