Petit problème d'optimisation...

Antoine Leca

30/05/2007 à 18:45

En news:465b6fdc$0$3630$,
Charlie Gordon va escriure:

"Antoine Leca" a écrit dans le message de
news: f3714j$afd$
En news:f36acg$tkk$, Laurent Deniau écrivit:
Je suis pas certain que le dernier
switch() d'Antoine soit plus rapide parce qu'on a perdu la linearite
des labels ce qui risque de se traduire par autant de tests que de
cases, et donc sous optimal par rapport a la dichotomie explicite.

Mon idée (mais je n'ai pas testé) c'est que ce switch est plein,
donc le compilateur va le remplacer par un goto calculé, en principe
plus rapide qu'une cascade de 3 tests.

Ton switch est tout sauf plein : les case values ne sont pas
contiguës, loin s'en faut, il a de fortes chances d'être compilé
comme une suite de tests (quand meme dichotomiques avec un bon
compilo).

Euh ?

Je réduis à 3 au lieu de 8 pour m'économiser, et cela se réduit à

switch( trame & 0xF ) {
case 0x7:
/* on a trouvé, il y a exactement 3 bits */
return ...;
case 0xF:
/* il y a au moins 4 bits à droite */
...
break;
case 0x3:
case 0xB:
/* on a trouvé, il y a exactement 2 bits */
return ...;
case 0x1: case 0x5:
case 0x9: case 0xD:
/* on a trouvé, il y a exactement 1 bit */
return ...;
case 0x0: case 0x2: case 0x4: case 0x6:
case 0x8: case 0xA: case 0xC: case 0xE:
/* on a trouvé, il y a exactement 0 bit */
return ...;
default: /* BOUM */
}

Pour moi, c'est un switch plein (il y a tous les cas possibles).
Effectivement les cas ne sont pas contigus, mais c'est bien là que réside
l'avantage d'un goto calculé ce me semble ; maintenant, si c'est un handicap
insurmontable pour ton compilo que de détecter la convexité ici... faut
p'têt changer de compilo, non ?

Le code de Pascal Bourguignon est très instructif en la matière

Oui. Je dois dire que j'ai lu son article après avoir posté le mien, mais
qu'il m'a impressionné.
Maintenant, cela illustre deux approches très différentes (et généralement
complémentaires) de l'optimisation : l'une est de chercher à optimiser à
fond l'algorithme actuel, économiser le quart de cycle là où c'est possible
; l'autre est de repenser le problème en cherchant un autre algorithme.

bitcount et atoi sont mes tests favoris lors d'un entretien
d'embauche pour un programmeur, j'ai un musée des horreurs où la
collection se renouvelle régulièrement, il est rare que j'aie
l'opportunité de faire analyser le bitcount par addition parallèle
qu'utilise PB (ce serait sadique), et jusqu'à présent personne ne l'a
proposé d'emblée (ce serait génial).

Mouais. ÀMHA, celui qui te le propose d'emblée, ce n'est pas un génie (car
il n'aurait en fait rien à faire dans ton entretien, désolé mais c'est comme
cela), mais plutôt quelqu'un qui a planché sur le sujet dans son contrat
précédent.

Par contre, dorénavant, celui qui est capable de te ressortir cela si tu lui
laisses 1 heure (et une station avec accès internet) pour résoudre le
problème, celui-là est intéressant parce que cela veut dire qu'il est
capable de savoir utiliser *efficacement* Google groups :-)))

Antoine

En news:465b6fdc$0$3630$426a74cc@news.free.fr,
Charlie Gordon va escriure:

"Antoine Leca" <root@localhost.invalid> a écrit dans le message de
news: f3714j$afd$1@shakotay.alphanet.ch...

En news:f36acg$tkk$1@cernne03.cern.ch, Laurent Deniau écrivit:

Je suis pas certain que le dernier
switch() d'Antoine soit plus rapide parce qu'on a perdu la linearite
des labels ce qui risque de se traduire par autant de tests que de
cases, et donc sous optimal par rapport a la dichotomie explicite.

Mon idée (mais je n'ai pas testé) c'est que ce switch est plein,
donc le compilateur va le remplacer par un goto calculé, en principe
plus rapide qu'une cascade de 3 tests.

Ton switch est tout sauf plein : les case values ne sont pas
contiguës, loin s'en faut, il a de fortes chances d'être compilé
comme une suite de tests (quand meme dichotomiques avec un bon
compilo).

Euh ?

Je réduis à 3 au lieu de 8 pour m'économiser, et cela se réduit à

switch( trame & 0xF ) {
case 0x7:
/* on a trouvé, il y a exactement 3 bits */
return ...;
case 0xF:
/* il y a au moins 4 bits à droite */
...
break;
case 0x3:
case 0xB:
/* on a trouvé, il y a exactement 2 bits */
return ...;
case 0x1: case 0x5:
case 0x9: case 0xD:
/* on a trouvé, il y a exactement 1 bit */
return ...;
case 0x0: case 0x2: case 0x4: case 0x6:
case 0x8: case 0xA: case 0xC: case 0xE:
/* on a trouvé, il y a exactement 0 bit */
return ...;
default: /* BOUM */
}

Pour moi, c'est un switch plein (il y a tous les cas possibles).
Effectivement les cas ne sont pas contigus, mais c'est bien là que réside
l'avantage d'un goto calculé ce me semble ; maintenant, si c'est un handicap
insurmontable pour ton compilo que de détecter la convexité ici... faut
p'têt changer de compilo, non ?

Le code de Pascal Bourguignon est très instructif en la matière

Oui. Je dois dire que j'ai lu son article après avoir posté le mien, mais
qu'il m'a impressionné.
Maintenant, cela illustre deux approches très différentes (et généralement
complémentaires) de l'optimisation : l'une est de chercher à optimiser à
fond l'algorithme actuel, économiser le quart de cycle là où c'est possible
; l'autre est de repenser le problème en cherchant un autre algorithme.

bitcount et atoi sont mes tests favoris lors d'un entretien
d'embauche pour un programmeur, j'ai un musée des horreurs où la
collection se renouvelle régulièrement, il est rare que j'aie
l'opportunité de faire analyser le bitcount par addition parallèle
qu'utilise PB (ce serait sadique), et jusqu'à présent personne ne l'a
proposé d'emblée (ce serait génial).

Mouais. ÀMHA, celui qui te le propose d'emblée, ce n'est pas un génie (car
il n'aurait en fait rien à faire dans ton entretien, désolé mais c'est comme
cela), mais plutôt quelqu'un qui a planché sur le sujet dans son contrat
précédent.

Par contre, dorénavant, celui qui est capable de te ressortir cela si tu lui
laisses 1 heure (et une station avec accès internet) pour résoudre le
problème, celui-là est intéressant parce que cela veut dire qu'il est
capable de savoir utiliser *efficacement* Google groups :-)))

Antoine

Vous avez filtré cet utilisateur ! Consultez son message

En news:465b6fdc$0$3630$,
Charlie Gordon va escriure:

"Antoine Leca" a écrit dans le message de
news: f3714j$afd$
En news:f36acg$tkk$, Laurent Deniau écrivit:
Je suis pas certain que le dernier
switch() d'Antoine soit plus rapide parce qu'on a perdu la linearite
des labels ce qui risque de se traduire par autant de tests que de
cases, et donc sous optimal par rapport a la dichotomie explicite.

Mon idée (mais je n'ai pas testé) c'est que ce switch est plein,
donc le compilateur va le remplacer par un goto calculé, en principe
plus rapide qu'une cascade de 3 tests.

Ton switch est tout sauf plein : les case values ne sont pas
contiguës, loin s'en faut, il a de fortes chances d'être compilé
comme une suite de tests (quand meme dichotomiques avec un bon
compilo).

Euh ?

Je réduis à 3 au lieu de 8 pour m'économiser, et cela se réduit à

switch( trame & 0xF ) {
case 0x7:
/* on a trouvé, il y a exactement 3 bits */
return ...;
case 0xF:
/* il y a au moins 4 bits à droite */
...
break;
case 0x3:
case 0xB:
/* on a trouvé, il y a exactement 2 bits */
return ...;
case 0x1: case 0x5:
case 0x9: case 0xD:
/* on a trouvé, il y a exactement 1 bit */
return ...;
case 0x0: case 0x2: case 0x4: case 0x6:
case 0x8: case 0xA: case 0xC: case 0xE:
/* on a trouvé, il y a exactement 0 bit */
return ...;
default: /* BOUM */
}

Pour moi, c'est un switch plein (il y a tous les cas possibles).
Effectivement les cas ne sont pas contigus, mais c'est bien là que réside
l'avantage d'un goto calculé ce me semble ; maintenant, si c'est un handicap
insurmontable pour ton compilo que de détecter la convexité ici... faut
p'têt changer de compilo, non ?

Le code de Pascal Bourguignon est très instructif en la matière

Oui. Je dois dire que j'ai lu son article après avoir posté le mien, mais
qu'il m'a impressionné.
Maintenant, cela illustre deux approches très différentes (et généralement
complémentaires) de l'optimisation : l'une est de chercher à optimiser à
fond l'algorithme actuel, économiser le quart de cycle là où c'est possible
; l'autre est de repenser le problème en cherchant un autre algorithme.

bitcount et atoi sont mes tests favoris lors d'un entretien
d'embauche pour un programmeur, j'ai un musée des horreurs où la
collection se renouvelle régulièrement, il est rare que j'aie
l'opportunité de faire analyser le bitcount par addition parallèle
qu'utilise PB (ce serait sadique), et jusqu'à présent personne ne l'a
proposé d'emblée (ce serait génial).

Mouais. ÀMHA, celui qui te le propose d'emblée, ce n'est pas un génie (car
il n'aurait en fait rien à faire dans ton entretien, désolé mais c'est comme
cela), mais plutôt quelqu'un qui a planché sur le sujet dans son contrat
précédent.

Par contre, dorénavant, celui qui est capable de te ressortir cela si tu lui
laisses 1 heure (et une station avec accès internet) pour résoudre le
problème, celui-là est intéressant parce que cela veut dire qu'il est
capable de savoir utiliser *efficacement* Google groups :-)))

Antoine

Antoine Leca

30/05/2007 à 18:59

Bzzzz...

En news:f368i9$kj1$,
Antoine Leca va escriure:

En news:,
Pascal Bourguignon va escriure:
Sinon, c'est plus simple de les enlever que de les compter:

int remove_ones_on_right(int bitfield){
/*
0101011111111
+1 0101100000000
xor 0000111111111
shift 0000011111111
- 0101000000000
*/
assert(bitfield>0);
return(bitfield-((bitfield^(bitfield+1))>>1));
}

Une fois que tu es arrivé là, on peut compter facilement, non ?

Jusque là, cela va.

int compter_les_uns_à_droite(int trame){
/*
0101011111111
+1 0101100000000
xor 0000111111111
shift 0000011111111
- 0101000000000

Cette soustraction est inutile, évidemment. En fait, le résultat du shift
est exactement ce que l'on cherche à compter.

*/
assert(trame>0);

switch((trame^(trame+1))>>1){

Bon, là cela déraille. Il est « évident » (merci à Chqrlie de me l'avoir
remis en mémoire) qu'il ne faut pas utiliser un switch ici, ce n'est pas
très efficace ; qui plus est, Pascal avait donné la piste pour le bon
algorithme.
Bref, faites pas attention à mes...

Antoine

Charlie Gordon

31/05/2007 à 02:56

"Antoine Leca" a écrit dans le message de news:
f3k9mi$8pt$

En news:465b6fdc$0$3630$,
Charlie Gordon va escriure:
Le code de Pascal Bourguignon est très instructif en la matière

Oui. Je dois dire que j'ai lu son article après avoir posté le mien, mais
qu'il m'a impressionné.
Maintenant, cela illustre deux approches très différentes (et généralement
complémentaires) de l'optimisation : l'une est de chercher à optimiser à
fond l'algorithme actuel, économiser le quart de cycle là où c'est
possible
; l'autre est de repenser le problème en cherchant un autre algorithme.

Oui ! D'ailleurs, c'est exactement ce que je me suis dit suite au post de
Bruno Causse qui propose un autre algorithme avec un modulo... Je fais
encore des tests, mais je pense pouvoir faire plus rapide que sa proposition
en 64 bits ;-)

bitcount et atoi sont mes tests favoris lors d'un entretien
d'embauche pour un programmeur, j'ai un musée des horreurs où la
collection se renouvelle régulièrement, il est rare que j'aie
l'opportunité de faire analyser le bitcount par addition parallèle
qu'utilise PB (ce serait sadique), et jusqu'à présent personne ne l'a
proposé d'emblée (ce serait génial).

Mouais. ÀMHA, celui qui te le propose d'emblée, ce n'est pas un génie (car
il n'aurait en fait rien à faire dans ton entretien, désolé mais c'est
comme
cela), mais plutôt quelqu'un qui a planché sur le sujet dans son contrat
précédent.

En fait, ça m'est réellement arrivé de rencontrer des génies de
l'informatique en entretien d'embauche (avec embauche !)
Mais c'est excessivement rare, je dirais une fois tous les dix ans, donc le
prochain est pour bientôt.

Je pense savoir distinguer celui qui connait l'algorithme, ce qui est déjà
remarquable sans s'aider d'Internet, celui qui s'est rencardé et s'attend à
la question mais est incapable d'expliquer le fonctionnement, et celui qui
un jour peut-etre réfléchira intensément pendant une minute et re-découvrira
cette méthode tout seul... c'est lui le génie.

Je leur donne 10 minutes pour écrire bitcount() avec du papier et un stylo,
sans Internet ni doc, 15 pour atoi(). Ceux qui ne demandent pas la
définition précise de l'API ont intérêt à la connaitre effectivement. Je
pense qu'un programmeur C correctement câblé peut résoudre ça sans
difficulté, mais dans le monde réel, le taux de chute est proche de 100%,
même avec plus de temps.

Par contre, dorénavant, celui qui est capable de te ressortir cela si tu
lui
laisses 1 heure (et une station avec accès internet) pour rme ésoudre le
problème, celui-là est intéressant parce que cela veut dire qu'il est
capable de savoir utiliser *efficacement* Google groups :-)))

1 heure pour bitcount avec Internet ! Tu plaisantes.
10 secondes avec google qui pointe immediatement sur
http://infolab.stanford.edu/~manku/bitcount/bitcount.html .
Ce n'est pas la meilleure page sur le sujet, celle de Sean Anderson est
beaucoup plus technique :
http://graphics.stanford.edu/~seander/bithacks.html et contient des tas
d'autres goodies...
Et rebelote : depuis que j'avais suggéré une petite optimisation, d'autres
sont allés encore plus loin en changeant subtilement l'algorithme (qui
d'ailleurs était faux dans mon post précédent ;-):

Cette collection vaut vraiment le détour !

Chqrlie.

"Antoine Leca" <root@localhost.invalid> a écrit dans le message de news:
f3k9mi$8pt$1@shakotay.alphanet.ch...

En news:465b6fdc$0$3630$426a74cc@news.free.fr,
Charlie Gordon va escriure:

Le code de Pascal Bourguignon est très instructif en la matière

Oui. Je dois dire que j'ai lu son article après avoir posté le mien, mais
qu'il m'a impressionné.
Maintenant, cela illustre deux approches très différentes (et généralement
complémentaires) de l'optimisation : l'une est de chercher à optimiser à
fond l'algorithme actuel, économiser le quart de cycle là où c'est
possible
; l'autre est de repenser le problème en cherchant un autre algorithme.

Oui ! D'ailleurs, c'est exactement ce que je me suis dit suite au post de
Bruno Causse qui propose un autre algorithme avec un modulo... Je fais
encore des tests, mais je pense pouvoir faire plus rapide que sa proposition
en 64 bits ;-)

bitcount et atoi sont mes tests favoris lors d'un entretien
d'embauche pour un programmeur, j'ai un musée des horreurs où la
collection se renouvelle régulièrement, il est rare que j'aie
l'opportunité de faire analyser le bitcount par addition parallèle
qu'utilise PB (ce serait sadique), et jusqu'à présent personne ne l'a
proposé d'emblée (ce serait génial).

Mouais. ÀMHA, celui qui te le propose d'emblée, ce n'est pas un génie (car
il n'aurait en fait rien à faire dans ton entretien, désolé mais c'est
comme
cela), mais plutôt quelqu'un qui a planché sur le sujet dans son contrat
précédent.

En fait, ça m'est réellement arrivé de rencontrer des génies de
l'informatique en entretien d'embauche (avec embauche !)
Mais c'est excessivement rare, je dirais une fois tous les dix ans, donc le
prochain est pour bientôt.

Je pense savoir distinguer celui qui connait l'algorithme, ce qui est déjà
remarquable sans s'aider d'Internet, celui qui s'est rencardé et s'attend à
la question mais est incapable d'expliquer le fonctionnement, et celui qui
un jour peut-etre réfléchira intensément pendant une minute et re-découvrira
cette méthode tout seul... c'est lui le génie.

Je leur donne 10 minutes pour écrire bitcount() avec du papier et un stylo,
sans Internet ni doc, 15 pour atoi(). Ceux qui ne demandent pas la
définition précise de l'API ont intérêt à la connaitre effectivement. Je
pense qu'un programmeur C correctement câblé peut résoudre ça sans
difficulté, mais dans le monde réel, le taux de chute est proche de 100%,
même avec plus de temps.

Par contre, dorénavant, celui qui est capable de te ressortir cela si tu
lui
laisses 1 heure (et une station avec accès internet) pour rme ésoudre le
problème, celui-là est intéressant parce que cela veut dire qu'il est
capable de savoir utiliser *efficacement* Google groups :-)))

1 heure pour bitcount avec Internet ! Tu plaisantes.
10 secondes avec google qui pointe immediatement sur
http://infolab.stanford.edu/~manku/bitcount/bitcount.html .
Ce n'est pas la meilleure page sur le sujet, celle de Sean Anderson est
beaucoup plus technique :
http://graphics.stanford.edu/~seander/bithacks.html et contient des tas
d'autres goodies...
Et rebelote : depuis que j'avais suggéré une petite optimisation, d'autres
sont allés encore plus loin en changeant subtilement l'algorithme (qui
d'ailleurs était faux dans mon post précédent ;-):

Cette collection vaut vraiment le détour !

Chqrlie.

Vous avez filtré cet utilisateur ! Consultez son message

"Antoine Leca" a écrit dans le message de news:
f3k9mi$8pt$

En news:465b6fdc$0$3630$,
Charlie Gordon va escriure:
Le code de Pascal Bourguignon est très instructif en la matière

Oui. Je dois dire que j'ai lu son article après avoir posté le mien, mais
qu'il m'a impressionné.
Maintenant, cela illustre deux approches très différentes (et généralement
complémentaires) de l'optimisation : l'une est de chercher à optimiser à
fond l'algorithme actuel, économiser le quart de cycle là où c'est
possible
; l'autre est de repenser le problème en cherchant un autre algorithme.

Oui ! D'ailleurs, c'est exactement ce que je me suis dit suite au post de
Bruno Causse qui propose un autre algorithme avec un modulo... Je fais
encore des tests, mais je pense pouvoir faire plus rapide que sa proposition
en 64 bits ;-)

bitcount et atoi sont mes tests favoris lors d'un entretien
d'embauche pour un programmeur, j'ai un musée des horreurs où la
collection se renouvelle régulièrement, il est rare que j'aie
l'opportunité de faire analyser le bitcount par addition parallèle
qu'utilise PB (ce serait sadique), et jusqu'à présent personne ne l'a
proposé d'emblée (ce serait génial).

Mouais. ÀMHA, celui qui te le propose d'emblée, ce n'est pas un génie (car
il n'aurait en fait rien à faire dans ton entretien, désolé mais c'est
comme
cela), mais plutôt quelqu'un qui a planché sur le sujet dans son contrat
précédent.

En fait, ça m'est réellement arrivé de rencontrer des génies de
l'informatique en entretien d'embauche (avec embauche !)
Mais c'est excessivement rare, je dirais une fois tous les dix ans, donc le
prochain est pour bientôt.

Je pense savoir distinguer celui qui connait l'algorithme, ce qui est déjà
remarquable sans s'aider d'Internet, celui qui s'est rencardé et s'attend à
la question mais est incapable d'expliquer le fonctionnement, et celui qui
un jour peut-etre réfléchira intensément pendant une minute et re-découvrira
cette méthode tout seul... c'est lui le génie.

Je leur donne 10 minutes pour écrire bitcount() avec du papier et un stylo,
sans Internet ni doc, 15 pour atoi(). Ceux qui ne demandent pas la
définition précise de l'API ont intérêt à la connaitre effectivement. Je
pense qu'un programmeur C correctement câblé peut résoudre ça sans
difficulté, mais dans le monde réel, le taux de chute est proche de 100%,
même avec plus de temps.

Par contre, dorénavant, celui qui est capable de te ressortir cela si tu
lui
laisses 1 heure (et une station avec accès internet) pour rme ésoudre le
problème, celui-là est intéressant parce que cela veut dire qu'il est
capable de savoir utiliser *efficacement* Google groups :-)))

1 heure pour bitcount avec Internet ! Tu plaisantes.
10 secondes avec google qui pointe immediatement sur
http://infolab.stanford.edu/~manku/bitcount/bitcount.html .
Ce n'est pas la meilleure page sur le sujet, celle de Sean Anderson est
beaucoup plus technique :
http://graphics.stanford.edu/~seander/bithacks.html et contient des tas
d'autres goodies...
Et rebelote : depuis que j'avais suggéré une petite optimisation, d'autres
sont allés encore plus loin en changeant subtilement l'algorithme (qui
d'ailleurs était faux dans mon post précédent ;-):

Cette collection vaut vraiment le détour !

Chqrlie.

Jean-Marc Bourguet

31/05/2007 à 09:24

"Charlie Gordon" writes:

Je pense qu'un programmeur C correctement câblé peut résoudre ça sans
difficulté, mais dans le monde réel, le taux de chute est proche de 100%,
même avec plus de temps.

Ca me rassure... Mais quel est l'interet d'une question (je parle de
popcount/bitcount) qui est aussi peu discrimimante et pour laquelle une
reponse correcte a plus de chance de montrer que le candidat a eu a
examiner la question qu'autre chose ? C'est vrai que j'ai bien prepare une
ou deux questions du genre, mais je ne compte les sortir(*) qu'apres avoir
verifie que les candidats ont une petite chance d'y repondre.

A+

(*) Je n'ai pas encore eu l'occasion de le faire. Mon implication dans le
processus d'embauche est recente, et je vais de desillusion en desillusion;
qu'on se survende dans les CV -- je l'accepte meme si je ne le ferais pas
-- mais qu'on continue a le faire alors que je commence par un petit laius
expliquant que je vais verifier effectivement la profondeur des
connaissances sur les domaines qui nous interessent c'est un culot qui me
depasse un peu. Et ce que je ne comprends absolument pas, c'est comment
apres s'etre pris veste sur veste sur chaque domaine aborte, un candidat
peut encore pretendre etre expert sur quelque chose que non seulement il ne
domine pas totalement, mais dont apparemment il ne connait que le nom -- il
y en a qui n'ont pas su repondre correctement a UNE seule question, et
pourtant j'ai fini par taper bas (j'ai eu ainsi un "expert" en
parralelisation qui ne savait pas la difference entre thread et processus,
qui s'imaginait qu'il etait impossible d'avoir de la memoire partagee entre
processeurs, et j'en passe).

--
Jean-Marc
FAQ de fclc: http://www.isty-info.uvsq.fr/~rumeau/fclc
Site de usenet-fr: http://www.usenet-fr.news.eu.org

Bruno Causse

31/05/2007 à 09:51

"Charlie Gordon" a écrit dans le message de news:
465e1d62$0$6073$

Oui ! D'ailleurs, c'est exactement ce que je me suis dit suite au post de
Bruno Causse qui propose un autre algorithme avec un modulo... Je fais >
encore des tests, mais je pense pouvoir faire plus rapide que sa
proposition en 64 bits ;-)

ca m'interresse de voir, en son temps (confirmer par quelque tests) sur des
processeurs modernes la fonction modulo etait en un cycle

Richard Delorme

03/06/2007 à 20:52

Patrick 'Zener' Brunet wrote:

Bonsoir.

Je cherche à optimiser une (pas si) bête opération de recherche de bit dans
un nombre entier.
[...]

Le but est d'extraire le nombre de 1 jointifs à droite, ou bien (c'est
équivalent) le rang du premier 0 à droite.
Dans cet exemple: 7

Un sous-problème peut être d'éliminer les 1 de la partie gauche...

x & (~x + 1)

Soit, avec la représentation la plus courante des entiers négatifs :

x & -x

d'où la fonction suivante (pour des entiers 64 bits) :

int bits_first_one(uint64_t b) {
const int magic_bitpos64[64]={
63, 0, 58, 1, 59, 47, 53, 2,
60, 39, 48, 27, 54, 33, 42, 3,
61, 51, 37, 40, 49, 18, 28, 20,
55, 30, 34, 11, 43, 14, 22, 4,
62, 57, 46, 52, 38, 26, 32, 41,
50, 36, 17, 19, 29, 10, 13, 21,
56, 45, 25, 31, 35, 16, 9, 12,
44, 24, 15, 8, 23, 7, 6, 5
};

b &= (-b);
return magic_bitpos64[(b * 0x07EDD5E59A4E28C2ULL) >> 58];
}

Pour les détails techniques on pourra lire :

ftp://theory.lcs.mit.edu/pub/cilk/debruijn.ps.gz
http://www.prism.gatech.edu/~gtg365v/Buzz/research/magic/Bitboards.pdf

A l'attention plus personnel de Bruno Causse, qui semble lire ce fil, je
tiens à préciser que le principe algorithmique des "coups magiques"
développé dans ce dernier article fonctionne aussi pour le jeu d'Othello.

--
Richard

Bruno Causse

04/06/2007 à 10:03

"Richard Delorme" a écrit dans le message de news:
46630e44>

Pour les détails techniques on pourra lire :

ftp://theory.lcs.mit.edu/pub/cilk/debruijn.ps.gz
http://www.prism.gatech.edu/~gtg365v/Buzz/research/magic/Bitboards.pdf

A l'attention plus personnel de Bruno Causse, qui semble lire ce fil, je
tiens à préciser que le principe algorithmique des "coups magiques"
développé dans ce dernier article fonctionne aussi pour le jeu d'Othello.

merci richard, j'utilise deja "l'architecture 64 bits" (post nicolet) dans
mon prog
mais je vais lire (et tenter de comprendre) cette publication (du 7 avril ==
tu es plutot au courant dit donc :-))

tu nous manque sur ggs :-)

a+

Patrick 'Zener' Brunet

08/06/2007 à 21:21

Bonsoir.

"Laurent Deniau" a écrit dans le message news:
f3gqiv$f3j$

Patrick 'Zener' Brunet wrote:
"Patrick 'Zener' Brunet" a écrit
dans

le message news: f34nr2$oi5$
Je cherche à optimiser une (pas si) bête opération de recherche
de bit [...]
Ben voilà, j'ai un beau tableau creux maintenant, qui doit donc

rester virtuel.
Il me reste donc à me pencher sur les Patricia trees :-)

Et peut-etre regarder les "Judy Array" qui font exactement ca, non?

http://judy.sourceforge.net/

Donc comme promis, j'ai étudié en détail la doc technique des Judy Arrays et
Judy Trees.

Je salue le perfectionnisme et aussi le style des auteurs. Très beau
travail.

Toutefois, ce système ne répond pas à mon besoin complet:

- il s'agit fondamentalement d'un système de stockage indexé, qu'il utilise
des tableaux creux ou des arbres creux pour raisons de performances.

- dans mon cas, les relations de parenté dans la structure d'arbre sont
essentielles, et ne peuvent pas être subordonnées à l'optimalité du
stockage.

- je pourrais alors utiliser ce stockage indexé pour gérer uniquement le
tableau virtuel qui implémente mon arbre, mais finalement la forme des clés
ne s'y prête pas facilement: l'arbre étant non balancé, je me rends compte
que leur longueur peut croître de manière exponentielle, ce qui impliquerait
de les allouer elles-mêmes dynamiquement, et aussi d'intervenir au niveau
des fonctions de comparaison, d'encodage des noeuds...

- si par contre je m'oriente vers une représentation des clés par un code
logarithmique, en partie partagé par les éléments d'une même branche, ça va
devenir encore plus difficile à marier...

Bref j'ai encore mis les pieds dans un problème épineux et donc passionnant
:-)

--
Cordialement.
--
/**************************************************
* Patrick BRUNET
* E-mail: lien sur http://zener131.free.fr/ContactMe
**************************************************/

Bonsoir.

"Laurent Deniau" <laurent.deniau@cern.ch> a écrit dans le message news:
f3gqiv$f3j$1@cernne03.cern.ch...

Patrick 'Zener' Brunet wrote:

"Patrick 'Zener' Brunet" <use.link.in.signature@ddress.invalid> a écrit
dans

le message news: f34nr2$oi5$1@shakotay.alphanet.ch...

Je cherche à optimiser une (pas si) bête opération de recherche
de bit [...]
Ben voilà, j'ai un beau tableau creux maintenant, qui doit donc

rester virtuel.
Il me reste donc à me pencher sur les Patricia trees :-)

Et peut-etre regarder les "Judy Array" qui font exactement ca, non?

http://judy.sourceforge.net/

Donc comme promis, j'ai étudié en détail la doc technique des Judy Arrays et
Judy Trees.

Je salue le perfectionnisme et aussi le style des auteurs. Très beau
travail.

Toutefois, ce système ne répond pas à mon besoin complet:

- il s'agit fondamentalement d'un système de stockage indexé, qu'il utilise
des tableaux creux ou des arbres creux pour raisons de performances.

- dans mon cas, les relations de parenté dans la structure d'arbre sont
essentielles, et ne peuvent pas être subordonnées à l'optimalité du
stockage.

- je pourrais alors utiliser ce stockage indexé pour gérer uniquement le
tableau virtuel qui implémente mon arbre, mais finalement la forme des clés
ne s'y prête pas facilement: l'arbre étant non balancé, je me rends compte
que leur longueur peut croître de manière exponentielle, ce qui impliquerait
de les allouer elles-mêmes dynamiquement, et aussi d'intervenir au niveau
des fonctions de comparaison, d'encodage des noeuds...

- si par contre je m'oriente vers une représentation des clés par un code
logarithmique, en partie partagé par les éléments d'une même branche, ça va
devenir encore plus difficile à marier...

Bref j'ai encore mis les pieds dans un problème épineux et donc passionnant
:-)

--
Cordialement.
--
/**************************************************
* Patrick BRUNET
* E-mail: lien sur http://zener131.free.fr/ContactMe
**************************************************/

Petit problème d'optimisation...

8 réponses

Veuillez sélectionner un problème