J'ai écris un programme qui était censé être un prototype pour être
ensuite écrit en C.
Seulement voilà, il est déjà plus rapide qu'une version qui avait été
(mal) écrite en C++. C'est un programme genre calcul d'itinéraires, une
fonction récursive qui utilise intensivement les dictionnaires, lists et
arrays.
Ce qui m'étonne c'est que je ne gagne quasiment rien (10%) en utilisant
psyco. Du coup je me demande si j'y gagnerai quelque chose à le refaire
en C.
Des idées pour m'aider à estimer le gain ?
--
William Dodé - http://flibuste.net
Informaticien Indépendant
Si tu peux améliorer le code, envoi moi un patch, je prend. Un meilleur algo aussi, pourquoi pas.
Dans le jargon, le problème posé est celui du nombre de chemins hamiltoniens d'un cavalier sur un échiquier de côté N. Ce problème n'est pas répertorié (je parle de la question du dénombrement parce que sinon le problème est très connu), y compris sur le site de référence de Sloane :
Néanmoins, on trouve des traces de calculs sur le net et il s'avère que le nombre cherché devient rapidement extrêmement grand quand N augmente. Ce nombre est connu pour N=5, 6, 8 mais pas N=7. Une des rares références :
http://www.behnel.de/knight.html
Donc inutile de faire du très générique.
Je ne vois d'autre méthode que la bestiale (un parcours en profondeur du graphe du cavalier), avec les eux petites optimisations suivantes :
1) utiliser les symétries de l'échiquier (pour N=5, ça ramène le nombre de cases à 5) ;
oui, bien sûr, mais on ne compare plus vraiment la même chose...
2) précalculer les déplacements du cavaliers en fonction de sa case.
pas bête, ça change un peu, mais ça n'a pas l'air d'être plus performant au final.
Au total, mon code C est 15 fois plus rapide que celui que tu proposes (avec l'option -O2, j'obtiens 6.232s pour le tien et 0.408s pour le mien).
Si je modifie le mien pour qu'il ne fasse que les parcours 0,0 1,0 2,0 1,1 2,1 et 2,2 il redevient légèrement plus rapide que le tien...
-- William Dodé - http://flibuste.net Informaticien Indépendant
On 04-09-2009, candide wrote:
William Dode a écrit :
Si tu peux améliorer le code, envoi moi un patch, je prend. Un meilleur
algo aussi, pourquoi pas.
Dans le jargon, le problème posé est celui du nombre de chemins hamiltoniens
d'un cavalier sur un échiquier de côté N. Ce problème n'est pas répertorié (je
parle de la question du dénombrement parce que sinon le problème est très
connu), y compris sur le site de référence de Sloane :
Néanmoins, on trouve des traces de calculs sur le net et il s'avère que le
nombre cherché devient rapidement extrêmement grand quand N augmente. Ce nombre
est connu pour N=5, 6, 8 mais pas N=7. Une des rares références :
http://www.behnel.de/knight.html
Donc inutile de faire du très générique.
Je ne vois d'autre méthode que la bestiale (un parcours en profondeur du graphe
du cavalier), avec les eux petites optimisations suivantes :
1) utiliser les symétries de l'échiquier (pour N=5, ça ramène le nombre de cases
à 5) ;
oui, bien sûr, mais on ne compare plus vraiment la même chose...
2) précalculer les déplacements du cavaliers en fonction de sa case.
pas bête, ça change un peu, mais ça n'a pas l'air d'être plus performant
au final.
Au total, mon code C est 15 fois plus rapide que celui que tu proposes (avec
l'option -O2, j'obtiens 6.232s pour le tien et 0.408s pour le mien).
Si je modifie le mien pour qu'il ne fasse que les parcours 0,0 1,0 2,0
1,1 2,1 et 2,2 il redevient légèrement plus rapide que le tien...
Si tu peux améliorer le code, envoi moi un patch, je prend. Un meilleur algo aussi, pourquoi pas.
Dans le jargon, le problème posé est celui du nombre de chemins hamiltoniens d'un cavalier sur un échiquier de côté N. Ce problème n'est pas répertorié (je parle de la question du dénombrement parce que sinon le problème est très connu), y compris sur le site de référence de Sloane :
Néanmoins, on trouve des traces de calculs sur le net et il s'avère que le nombre cherché devient rapidement extrêmement grand quand N augmente. Ce nombre est connu pour N=5, 6, 8 mais pas N=7. Une des rares références :
http://www.behnel.de/knight.html
Donc inutile de faire du très générique.
Je ne vois d'autre méthode que la bestiale (un parcours en profondeur du graphe du cavalier), avec les eux petites optimisations suivantes :
1) utiliser les symétries de l'échiquier (pour N=5, ça ramène le nombre de cases à 5) ;
oui, bien sûr, mais on ne compare plus vraiment la même chose...
2) précalculer les déplacements du cavaliers en fonction de sa case.
pas bête, ça change un peu, mais ça n'a pas l'air d'être plus performant au final.
Au total, mon code C est 15 fois plus rapide que celui que tu proposes (avec l'option -O2, j'obtiens 6.232s pour le tien et 0.408s pour le mien).
Si je modifie le mien pour qu'il ne fasse que les parcours 0,0 1,0 2,0 1,1 2,1 et 2,2 il redevient légèrement plus rapide que le tien...
-- William Dodé - http://flibuste.net Informaticien Indépendant
candide
William Dode a écrit :
oui, bien sûr, mais on ne compare plus vraiment la même chose...
En effet mais tu avais dit vouloir améliorer le temps d'exécution ;) ? alors c'était vraiment la première optimisation à faire quand elle améliore vraiment le temps.
2) précalculer les déplacements du cavaliers en fonction de sa case.
pas bête, ça change un peu, mais ça n'a pas l'air d'être plus performant au final.
Au début, c'était la seule différence avec ton code. Mais ce n'est pas négligeable loin de là (grosso modo 3 fois plus rapide), voici ce que ça donne chez moi :
$ gcc -O2 -W -Wall -stdÉ9 -pedantic -o x cheval.c cheval.c:38: attention : return type defaults to «int» cheval.c: Dans la fonction «main» : cheval.c:40: attention : unused variable «i» $ time ./x Cherche avec 5
5x5 cases nbsol28 6 s ok real 0m6.305s user 0m6.108s sys 0m0.036s
$ gcc -O2 -W -Wall -stdÉ9 -pedantic -o x cavalier__.c $ time ./x 1728
real 0m2.214s user 0m2.144s sys 0m0.024s
et le fichier cavalier__.c si tu veux voir sur ta machine :
/* ----------------------------------------------*/ #include <stdio.h> #include <string.h> #define N 5 #define M 8
int echiquier[N][N]; int caseSuivante[N][N][M][2]; int nbVoisins[N][N]; int nbSol = 0;
void suivant(int lin, int col, int maxCases) { int k, m = nbVoisins[lin][col];
for (k = 0; k < m; k++) { int x = caseSuivante[lin][col][k][0]; int y = caseSuivante[lin][col][k][1];
if (echiquier[x][y] == 0) { echiquier[x][y] = 1; if (maxCases + 1 == N * N) nbSol++; suivant(x, y, maxCases + 1); echiquier[x][y] = 0; } } }
void creerVoisins(void) { int lin, col, x, y; int offset[M][2] = { {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1} }; for (col = 0; col < N; col++) for (lin = 0; lin < N; lin++) { int k;
for (k = 0; k < M; k++) { x = col + offset[k][0]; y = lin + offset[k][1]; if (0 <= (x) && (x) < N && 0 <= (y) && (y) < N) { int i = nbVoisins[lin][col];
Si je modifie le mien pour qu'il ne fasse que les parcours 0,0 1,0 2,0 1,1 2,1 et 2,2 il redevient légèrement plus rapide que le tien...
Ça peut se comprendre dans la mesure où le précalcul est intéressant si le calcul est effectué de nombreuses fois. Et au début, j'ai fait comme toi, j'ai itéré sur toutes les cases ...
Bon, de toute façon, l'intérêt des optimisations algorithmiques est limité dans le cas N=5 puisqu'on arrive aisément à obtenir le résultat.
Si on voulait s'attaquer au cas N=6 (j'ai fait un petit essai mais je n'ai pas le temps de me lancer là-dedans), il faut des optimisations un peu plus subtiles [voire trouver une méthode complètement différente mais je ne vois pas laquelle]. Une des premières qui me vient à l'esprit est de surveiller l'inaccessibilité de certaines cases ce qui permet de couper la branche correspondante du backtracking.
Exact. Chance pour moi, aucun parcours ne peut commencer à (2,1) (sinon je n'aurais pas trouvé 1728) et le temps de calcul est quasiment nul.
William Dode a écrit :
oui, bien sûr, mais on ne compare plus vraiment la même chose...
En effet mais tu avais dit vouloir améliorer le temps d'exécution ;) ?
alors c'était vraiment la première optimisation à faire quand elle améliore
vraiment le temps.
2) précalculer les déplacements du cavaliers en fonction de sa case.
pas bête, ça change un peu, mais ça n'a pas l'air d'être plus performant
au final.
Au début, c'était la seule différence avec ton code. Mais ce n'est pas
négligeable loin de là (grosso modo 3 fois plus rapide), voici ce que ça donne
chez moi :
$ gcc -O2 -W -Wall -stdÉ9 -pedantic -o x cheval.c
cheval.c:38: attention : return type defaults to «int»
cheval.c: Dans la fonction «main» :
cheval.c:40: attention : unused variable «i»
$ time ./x
Cherche avec 5
5x5 cases nbsol28 6 s
ok
real 0m6.305s
user 0m6.108s
sys 0m0.036s
$ gcc -O2 -W -Wall -stdÉ9 -pedantic -o x cavalier__.c
$ time ./x
1728
real 0m2.214s
user 0m2.144s
sys 0m0.024s
et le fichier cavalier__.c si tu veux voir sur ta machine :
/* ----------------------------------------------*/
#include <stdio.h>
#include <string.h>
#define N 5
#define M 8
int echiquier[N][N];
int caseSuivante[N][N][M][2];
int nbVoisins[N][N];
int nbSol = 0;
void suivant(int lin, int col, int maxCases)
{
int k, m = nbVoisins[lin][col];
for (k = 0; k < m; k++)
{
int x = caseSuivante[lin][col][k][0];
int y = caseSuivante[lin][col][k][1];
if (echiquier[x][y] == 0)
{
echiquier[x][y] = 1;
if (maxCases + 1 == N * N)
nbSol++;
suivant(x, y, maxCases + 1);
echiquier[x][y] = 0;
}
}
}
void creerVoisins(void)
{
int lin, col, x, y;
int offset[M][2] = {
{2, 1}, {1, 2}, {-1, 2}, {-2, 1},
{-2, -1}, {-1, -2}, {1, -2}, {2, -1}
};
for (col = 0; col < N; col++)
for (lin = 0; lin < N; lin++)
{
int k;
for (k = 0; k < M; k++)
{
x = col + offset[k][0];
y = lin + offset[k][1];
if (0 <= (x) && (x) < N && 0 <= (y) && (y) < N)
{
int i = nbVoisins[lin][col];
Si je modifie le mien pour qu'il ne fasse que les parcours 0,0 1,0 2,0
1,1 2,1 et 2,2 il redevient légèrement plus rapide que le tien...
Ça peut se comprendre dans la mesure où le précalcul est intéressant si le
calcul est effectué de nombreuses fois. Et au début, j'ai fait comme toi, j'ai
itéré sur toutes les cases ...
Bon, de toute façon, l'intérêt des optimisations algorithmiques est limité dans
le cas N=5 puisqu'on arrive aisément à obtenir le résultat.
Si on voulait s'attaquer au cas N=6 (j'ai fait un petit essai mais je n'ai pas
le temps de me lancer là-dedans), il faut des optimisations un peu plus subtiles
[voire trouver une méthode complètement différente mais je ne vois pas
laquelle]. Une des premières qui me vient à l'esprit est de surveiller
l'inaccessibilité de certaines cases ce qui permet de couper la branche
correspondante du backtracking.
oui, bien sûr, mais on ne compare plus vraiment la même chose...
En effet mais tu avais dit vouloir améliorer le temps d'exécution ;) ? alors c'était vraiment la première optimisation à faire quand elle améliore vraiment le temps.
2) précalculer les déplacements du cavaliers en fonction de sa case.
pas bête, ça change un peu, mais ça n'a pas l'air d'être plus performant au final.
Au début, c'était la seule différence avec ton code. Mais ce n'est pas négligeable loin de là (grosso modo 3 fois plus rapide), voici ce que ça donne chez moi :
$ gcc -O2 -W -Wall -stdÉ9 -pedantic -o x cheval.c cheval.c:38: attention : return type defaults to «int» cheval.c: Dans la fonction «main» : cheval.c:40: attention : unused variable «i» $ time ./x Cherche avec 5
5x5 cases nbsol28 6 s ok real 0m6.305s user 0m6.108s sys 0m0.036s
$ gcc -O2 -W -Wall -stdÉ9 -pedantic -o x cavalier__.c $ time ./x 1728
real 0m2.214s user 0m2.144s sys 0m0.024s
et le fichier cavalier__.c si tu veux voir sur ta machine :
/* ----------------------------------------------*/ #include <stdio.h> #include <string.h> #define N 5 #define M 8
int echiquier[N][N]; int caseSuivante[N][N][M][2]; int nbVoisins[N][N]; int nbSol = 0;
void suivant(int lin, int col, int maxCases) { int k, m = nbVoisins[lin][col];
for (k = 0; k < m; k++) { int x = caseSuivante[lin][col][k][0]; int y = caseSuivante[lin][col][k][1];
if (echiquier[x][y] == 0) { echiquier[x][y] = 1; if (maxCases + 1 == N * N) nbSol++; suivant(x, y, maxCases + 1); echiquier[x][y] = 0; } } }
void creerVoisins(void) { int lin, col, x, y; int offset[M][2] = { {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1} }; for (col = 0; col < N; col++) for (lin = 0; lin < N; lin++) { int k;
for (k = 0; k < M; k++) { x = col + offset[k][0]; y = lin + offset[k][1]; if (0 <= (x) && (x) < N && 0 <= (y) && (y) < N) { int i = nbVoisins[lin][col];
Si je modifie le mien pour qu'il ne fasse que les parcours 0,0 1,0 2,0 1,1 2,1 et 2,2 il redevient légèrement plus rapide que le tien...
Ça peut se comprendre dans la mesure où le précalcul est intéressant si le calcul est effectué de nombreuses fois. Et au début, j'ai fait comme toi, j'ai itéré sur toutes les cases ...
Bon, de toute façon, l'intérêt des optimisations algorithmiques est limité dans le cas N=5 puisqu'on arrive aisément à obtenir le résultat.
Si on voulait s'attaquer au cas N=6 (j'ai fait un petit essai mais je n'ai pas le temps de me lancer là-dedans), il faut des optimisations un peu plus subtiles [voire trouver une méthode complètement différente mais je ne vois pas laquelle]. Une des premières qui me vient à l'esprit est de surveiller l'inaccessibilité de certaines cases ce qui permet de couper la branche correspondante du backtracking.
