C ou Python

Michel Claveau - MVP

17/07/2009 à 13:32

Salut !

Psycho V2 vient juste de sortir. Alors, comme tu as un jeu d'essai tout prêt, tu pourrais nous dire s'il y a beaucoup d'améliorations...

@+
--
Michel Claveau

William Dode

17/07/2009 à 16:07

On 17-07-2009, Michel Claveau - MVP wrote:

Salut !

Psycho V2 vient juste de sortir. Alors, comme tu as un jeu d'essai tout prêt, tu pourrais nous dire s'il y a beaucoup d'améliorations...

Aucune en ce qui me concerne...

Par contre j'ai un exemple de code où le gain avec psyco (v1 ou v2) est
énorme, 18s contre 5 minutes. (en C 5s, en java 7s).
Le remplissage d'un damier avec des déplacement de chevaux...

--
William Dodé - http://flibuste.net
Informaticien Indépendant

William Dode

17/07/2009 à 19:28

On 08-07-2009, William Dode wrote:

A propos d'optimisation...

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.

Bingo, j'ai trouvé !!! Je faisais juste naïvement psyco.full(), et j'ai
essayé avec ce qui est indiqué dans la doc, from psyco.classes import *
et là j'ai carrément un gain de 10x !!! oui, 10x plus rapide ! Je me
disais bien aussi, un programme qui ne fait que du calcul...

Et effectivement, j'ai du utiliser la V2, la v1 me donne un segfault, je
n'ai pas encore regardé pourquoi.

J'ai hâte de voir la tête de l'équipe avec qui je bosse, ils sont encore
au PHP et étaient déjà impressionnés par la version python sans psyco !

--
William Dodé - http://flibuste.net
Informaticien Indépendant

Stéphane Santon

01/09/2009 à 18:15

Bonjour,

William Dode a écrit :

Par contre j'ai un exemple de code où le gain avec psyco (v1 ou v2) est
énorme, 18s contre 5 minutes. (en C 5s, en java 7s).
Le remplissage d'un damier avec des déplacement de chevaux...

J'ai fait ça quand j'étais au service militaire... 1990... sur des
80386 (peut-être 16 MHz ?).
D'abord en Visual Basic, puis en TurboPascal 5.5 (compilé).
Avec la progression des algorithmes sur 5 jours, on est passé de 5
minutes à une demi-seconde... sur des 386.

Donc ton damier (echiquier) doit être énorme pour durer quelques
secondes avec les fréquences d'aujourd'hui !

--
Stéphane

Jeune Chambre Economique de Saintes *** http://www.jce-saintes.org
Agitateurs d'idées... accélérateurs de talents !

BTS Electrotechnique *** http://enselec.santonum.eu

William Dode

01/09/2009 à 21:12

On 01-09-2009, Stéphane Santon wrote:

Bonjour,

William Dode a écrit :
Par contre j'ai un exemple de code où le gain avec psyco (v1 ou v2) est
énorme, 18s contre 5 minutes. (en C 5s, en java 7s).
Le remplissage d'un damier avec des déplacement de chevaux...

J'ai fait ça quand j'étais au service militaire... 1990... sur des
80386 (peut-être 16 MHz ?).
D'abord en Visual Basic, puis en TurboPascal 5.5 (compilé).
Avec la progression des algorithmes sur 5 jours, on est passé de 5
minutes à une demi-seconde... sur des 386.

Donc ton damier (echiquier) doit être énorme pour durer quelques
secondes avec les fréquences d'aujourd'hui !

Le temps est celui pour trouver *toutes* les solutions, d'un damier 5x5

Le code est là si tu veux jeter un coup d'oeuil :
http://hg.flibuste.net/libre/games/cheval/

Les résultats :
c 1.65s
gcj 1.9s
cython 2s
java 2.4s
shedskin 0.2 -bw 2.6s
python2.5 + psyco 2.9s
unladen-2009Q2 125s (2m05)
Jython 2.2.1 on java1.6.0_12 176s (without array, like shedskin)
python2.5 215s (3m35s)
python3.1 246s (4m06s)
Jython 2.2.1 on java1.6.0_12 334s (with array)
php5.2.6 500 (8m20s)
ironpython1.1.1 (mono) 512 (8m32s)

--
William Dodé - http://flibuste.net
Informaticien Indépendant

candide

03/09/2009 à 23:39

William Dode a écrit :

Le temps est celui pour trouver *toutes* les solutions, d'un damier 5x5

Le moins que l'on puisse dire est que le problème n'a pas été clairement formulé :

-- la contrainte c'est quoi ? elle n'est pas explicitement formulée. Parcourir
toutes les cases d'un échiquier N x N par un cavalier en sorte que
chaque case soit occupée une fois et une seule ?
-- où est le cavalier au départ ? A priori n'importe où ? C'est ce que
laisserait supposer les lignes 29-31 du code C mais ce serait quand même mieux
de ne pas avoir à jouer aux devinettes.

Le code est là si tu veux jeter un coup d'oeuil :
http://hg.flibuste.net/libre/games/cheval/

Les résultats :
c 1.65s

La variable i déclarée dans main() n'est pas utilisée.

Ça manque de commentaires. Et certaines constantes magiques telles que 400, 100
ou 5 n'aident pas à la lisibilité. Et si on veut changer l'échiquier en une
taille 8x8, il faut changer ces constantes ?

William Dode

04/09/2009 à 09:49

On 03-09-2009, candide wrote:

William Dode a écrit :

Le temps est celui pour trouver *toutes* les solutions, d'un damier 5x5

Le moins que l'on puisse dire est que le problème n'a pas été clairement formulé :

-- la contrainte c'est quoi ? elle n'est pas explicitement formulée. Parcourir
toutes les cases d'un échiquier N x N par un cavalier en sorte que
chaque case soit occupée une fois et une seule ?

Oui

-- où est le cavalier au départ ? A priori n'importe où ? C'est ce que
laisserait supposer les lignes 29-31 du code C mais ce serait quand même mieux
de ne pas avoir à jouer aux devinettes.

Le cavalier part de toutes les cases (ça crée une redondance si on
tourne le damier).

Le but du jeu n'était pas pour moi de trouver la toute meilleure
solution mais d'avoir le code le plus proche possible entre les
différents langages.

Le code est là si tu veux jeter un coup d'oeuil :
http://hg.flibuste.net/libre/games/cheval/

Les résultats :
c 1.65s

La variable i déclarée dans main() n'est pas utilisée.

Ça manque de commentaires. Et certaines constantes magiques telles que 400, 100
ou 5 n'aident pas à la lisibilité. Et si on veut changer l'échiquier en une
taille 8x8, il faut changer ces constantes ?

Oui, c'est pour optimiser

Si tu peux améliorer le code, envoi moi un patch, je prend. Un meilleur
algo aussi, pourquoi pas.

--
William Dodé - http://flibuste.net
Informaticien Indépendant

Pierre Maurette

04/09/2009 à 11:42

William Dode, le 04/09/2009 a écrit :

[...]

Ça manque de commentaires. Et certaines constantes magiques telles que 400,
100 ou 5 n'aident pas à la lisibilité. Et si on veut changer l'échiquier en
une taille 8x8, il faut changer ces constantes ?

Oui, c'est pour optimiser

Avant que vous ne vous fassiez gronder: je n'ai jeté un oeil qu'en
diagnonale, néanmoins il me semble que vous n'optimisez pas vraiment,
bien au contraire.
Vous écrivez par exemple:

int SIDE=5;
int SQR_SIDE%;

il manque déjà un const:

const int SIDE=5;
const int SQR_SIDE%;

pour augmenter les "chances" que le compilateur optimise. Mais le but
étant de bien montrer clairement ce qui est une constante dès la
compilation, autant faire:

#define SIDE 5
#define SQR_SIDE (SIDE * SIDE)

en "centralisant" au maximum (5 et 25 sont redondants, alors que 5 et
(SIDE * SIDE) ne le sont pas). Et en utilisant les macros partout où
c'est possible, ce qui ne me semble pas être le cas dans votre code,
loin s'en faut.

A ce moemnt-là tout ce petit monde sera remplacé avant la compilation
proprement-dite. Vous pouvez d'ailleurs ajouter un:

#define NB_CASES SQR_SIDE

absolument sans aucun coût en performance.

Pourquoi dire clairement au compilateur ce qui est connu, constant à la
compilation ? Pour qu'il puisse entrer dans un processus
d'optimisations pour lesquelles il est en général très doué. Deux
exemple: les multiplications par des constantes entières, pour
lesquelles il génèrera un code machine bien plus rapide que la
multiplication (en x86, le plus souvent un LEA). Si vous demandez une
optimisation en vitesse, il va également développer les boucles "assez
petites" pour peu que le nombre de passage soit connu à la compilation.
A 3, c'est toujours valable, à 5 également, à mon avis. Par exemple, la
boucle:

for(x = 0; x < 5; x++){
f(y, x);
}
(f() remplace du code, pas l'appel d'une fonction nécessairement).

sera compilée comme:
f(y, 0);
f(y, 1);
f(y, 2);
f(y, 3);
f(y, 4);

et même souvent la boucle développée ou non disparaîtra, au profit d'un
truc comme:

y = un_resultat;

ou

y = g(y, autres_valeurs);

parce que le compilateur peut très bien faire tourner la boucle à la
compilation.

Si 5 est replacé par SIDE et que SIDE est un #define, tout se passera
comme ça. Avec un SIDE défini comme un const int, un peu moins de
chance. Et encore moinsavec un SIDE défini comme un simple int.

--
Pierre Maurette

William Dode, le 04/09/2009 a écrit :

[...]

Ça manque de commentaires. Et certaines constantes magiques telles que 400,
100 ou 5 n'aident pas à la lisibilité. Et si on veut changer l'échiquier en
une taille 8x8, il faut changer ces constantes ?

Oui, c'est pour optimiser

Avant que vous ne vous fassiez gronder: je n'ai jeté un oeil qu'en
diagnonale, néanmoins il me semble que vous n'optimisez pas vraiment,
bien au contraire.
Vous écrivez par exemple:

int SIDE=5;
int SQR_SIDE%;

il manque déjà un const:

const int SIDE=5;
const int SQR_SIDE%;

pour augmenter les "chances" que le compilateur optimise. Mais le but
étant de bien montrer clairement ce qui est une constante dès la
compilation, autant faire:

#define SIDE 5
#define SQR_SIDE (SIDE * SIDE)

en "centralisant" au maximum (5 et 25 sont redondants, alors que 5 et
(SIDE * SIDE) ne le sont pas). Et en utilisant les macros partout où
c'est possible, ce qui ne me semble pas être le cas dans votre code,
loin s'en faut.

A ce moemnt-là tout ce petit monde sera remplacé avant la compilation
proprement-dite. Vous pouvez d'ailleurs ajouter un:

#define NB_CASES SQR_SIDE

absolument sans aucun coût en performance.

Pourquoi dire clairement au compilateur ce qui est connu, constant à la
compilation ? Pour qu'il puisse entrer dans un processus
d'optimisations pour lesquelles il est en général très doué. Deux
exemple: les multiplications par des constantes entières, pour
lesquelles il génèrera un code machine bien plus rapide que la
multiplication (en x86, le plus souvent un LEA). Si vous demandez une
optimisation en vitesse, il va également développer les boucles "assez
petites" pour peu que le nombre de passage soit connu à la compilation.
A 3, c'est toujours valable, à 5 également, à mon avis. Par exemple, la
boucle:

for(x = 0; x < 5; x++){
f(y, x);
}
(f() remplace du code, pas l'appel d'une fonction nécessairement).

sera compilée comme:
f(y, 0);
f(y, 1);
f(y, 2);
f(y, 3);
f(y, 4);

et même souvent la boucle développée ou non disparaîtra, au profit d'un
truc comme:

y = un_resultat;

ou

y = g(y, autres_valeurs);

parce que le compilateur peut très bien faire tourner la boucle à la
compilation.

Si 5 est replacé par SIDE et que SIDE est un #define, tout se passera
comme ça. Avec un SIDE défini comme un const int, un peu moins de
chance. Et encore moinsavec un SIDE défini comme un simple int.

--
Pierre Maurette

Vous avez filtré cet utilisateur ! Consultez son message

William Dode, le 04/09/2009 a écrit :

[...]

Ça manque de commentaires. Et certaines constantes magiques telles que 400,
100 ou 5 n'aident pas à la lisibilité. Et si on veut changer l'échiquier en
une taille 8x8, il faut changer ces constantes ?

Oui, c'est pour optimiser

Avant que vous ne vous fassiez gronder: je n'ai jeté un oeil qu'en
diagnonale, néanmoins il me semble que vous n'optimisez pas vraiment,
bien au contraire.
Vous écrivez par exemple:

int SIDE=5;
int SQR_SIDE%;

il manque déjà un const:

const int SIDE=5;
const int SQR_SIDE%;

pour augmenter les "chances" que le compilateur optimise. Mais le but
étant de bien montrer clairement ce qui est une constante dès la
compilation, autant faire:

#define SIDE 5
#define SQR_SIDE (SIDE * SIDE)

en "centralisant" au maximum (5 et 25 sont redondants, alors que 5 et
(SIDE * SIDE) ne le sont pas). Et en utilisant les macros partout où
c'est possible, ce qui ne me semble pas être le cas dans votre code,
loin s'en faut.

A ce moemnt-là tout ce petit monde sera remplacé avant la compilation
proprement-dite. Vous pouvez d'ailleurs ajouter un:

#define NB_CASES SQR_SIDE

absolument sans aucun coût en performance.

Pourquoi dire clairement au compilateur ce qui est connu, constant à la
compilation ? Pour qu'il puisse entrer dans un processus
d'optimisations pour lesquelles il est en général très doué. Deux
exemple: les multiplications par des constantes entières, pour
lesquelles il génèrera un code machine bien plus rapide que la
multiplication (en x86, le plus souvent un LEA). Si vous demandez une
optimisation en vitesse, il va également développer les boucles "assez
petites" pour peu que le nombre de passage soit connu à la compilation.
A 3, c'est toujours valable, à 5 également, à mon avis. Par exemple, la
boucle:

for(x = 0; x < 5; x++){
f(y, x);
}
(f() remplace du code, pas l'appel d'une fonction nécessairement).

sera compilée comme:
f(y, 0);
f(y, 1);
f(y, 2);
f(y, 3);
f(y, 4);

et même souvent la boucle développée ou non disparaîtra, au profit d'un
truc comme:

y = un_resultat;

ou

y = g(y, autres_valeurs);

parce que le compilateur peut très bien faire tourner la boucle à la
compilation.

Si 5 est replacé par SIDE et que SIDE est un #define, tout se passera
comme ça. Avec un SIDE défini comme un const int, un peu moins de
chance. Et encore moinsavec un SIDE défini comme un simple int.

--
Pierre Maurette

William Dode

04/09/2009 à 13:19

On 04-09-2009, Pierre Maurette wrote:

William Dode, le 04/09/2009 a écrit :

[...]

Ça manque de commentaires. Et certaines constantes magiques telles que 400,
100 ou 5 n'aident pas à la lisibilité. Et si on veut changer l'échiquier en
une taille 8x8, il faut changer ces constantes ?

Oui, c'est pour optimiser

Avant que vous ne vous fassiez gronder: je n'ai jeté un oeil qu'en
diagnonale, néanmoins il me semble que vous n'optimisez pas vraiment,
bien au contraire.
Vous écrivez par exemple:

int SIDE=5;
int SQR_SIDE%;

il manque déjà un const:

const int SIDE=5;
const int SQR_SIDE%;

pour augmenter les "chances" que le compilateur optimise. Mais le but
étant de bien montrer clairement ce qui est une constante dès la
compilation, autant faire:

#define SIDE 5
#define SQR_SIDE (SIDE * SIDE)

Je viens d'intégrer ça, mais hélas ça ne change pas grand chose pour le
coup vu qu'il ne se sert pas de ces valeurs pour boucler. Mais ne
serait-ce que pour la lisibilité c'est mieux...

en "centralisant" au maximum (5 et 25 sont redondants, alors que 5 et
(SIDE * SIDE) ne le sont pas). Et en utilisant les macros partout où
c'est possible, ce qui ne me semble pas être le cas dans votre code,
loin s'en faut.

A ce moemnt-là tout ce petit monde sera remplacé avant la compilation
proprement-dite. Vous pouvez d'ailleurs ajouter un:

#define NB_CASES SQR_SIDE

absolument sans aucun coût en performance.

Pourquoi dire clairement au compilateur ce qui est connu, constant à la
compilation ? Pour qu'il puisse entrer dans un processus
d'optimisations pour lesquelles il est en général très doué. Deux
exemple: les multiplications par des constantes entières, pour
lesquelles il génèrera un code machine bien plus rapide que la
multiplication (en x86, le plus souvent un LEA). Si vous demandez une
optimisation en vitesse, il va également développer les boucles "assez
petites" pour peu que le nombre de passage soit connu à la compilation.
A 3, c'est toujours valable, à 5 également, à mon avis. Par exemple, la
boucle:

for(x = 0; x < 5; x++){
f(y, x);
}
(f() remplace du code, pas l'appel d'une fonction nécessairement).

sera compilée comme:
f(y, 0);
f(y, 1);
f(y, 2);
f(y, 3);
f(y, 4);

La fonction qui boucle le plus est déjà avec un #define (nbmove), mais
je me demande si ça joue beaucoup dans le cas d'une fonction récurcive ?

Si je met int nbmove=5; le résultat est identique chez moi...

Je serait curieux de voir le code que ça donnerait en lisp ou autre, si
quelqu'un connait ?

--
William Dodé - http://flibuste.net
Informaticien Indépendant

On 04-09-2009, Pierre Maurette wrote:

William Dode, le 04/09/2009 a écrit :

[...]

Ça manque de commentaires. Et certaines constantes magiques telles que 400,
100 ou 5 n'aident pas à la lisibilité. Et si on veut changer l'échiquier en
une taille 8x8, il faut changer ces constantes ?

Oui, c'est pour optimiser

Avant que vous ne vous fassiez gronder: je n'ai jeté un oeil qu'en
diagnonale, néanmoins il me semble que vous n'optimisez pas vraiment,
bien au contraire.
Vous écrivez par exemple:

int SIDE=5;
int SQR_SIDE%;

il manque déjà un const:

const int SIDE=5;
const int SQR_SIDE%;

pour augmenter les "chances" que le compilateur optimise. Mais le but
étant de bien montrer clairement ce qui est une constante dès la
compilation, autant faire:

#define SIDE 5
#define SQR_SIDE (SIDE * SIDE)

Je viens d'intégrer ça, mais hélas ça ne change pas grand chose pour le
coup vu qu'il ne se sert pas de ces valeurs pour boucler. Mais ne
serait-ce que pour la lisibilité c'est mieux...

en "centralisant" au maximum (5 et 25 sont redondants, alors que 5 et
(SIDE * SIDE) ne le sont pas). Et en utilisant les macros partout où
c'est possible, ce qui ne me semble pas être le cas dans votre code,
loin s'en faut.

A ce moemnt-là tout ce petit monde sera remplacé avant la compilation
proprement-dite. Vous pouvez d'ailleurs ajouter un:

#define NB_CASES SQR_SIDE

absolument sans aucun coût en performance.

Pourquoi dire clairement au compilateur ce qui est connu, constant à la
compilation ? Pour qu'il puisse entrer dans un processus
d'optimisations pour lesquelles il est en général très doué. Deux
exemple: les multiplications par des constantes entières, pour
lesquelles il génèrera un code machine bien plus rapide que la
multiplication (en x86, le plus souvent un LEA). Si vous demandez une
optimisation en vitesse, il va également développer les boucles "assez
petites" pour peu que le nombre de passage soit connu à la compilation.
A 3, c'est toujours valable, à 5 également, à mon avis. Par exemple, la
boucle:

for(x = 0; x < 5; x++){
f(y, x);
}
(f() remplace du code, pas l'appel d'une fonction nécessairement).

sera compilée comme:
f(y, 0);
f(y, 1);
f(y, 2);
f(y, 3);
f(y, 4);

La fonction qui boucle le plus est déjà avec un #define (nbmove), mais
je me demande si ça joue beaucoup dans le cas d'une fonction récurcive ?

Si je met int nbmove=5; le résultat est identique chez moi...

Je serait curieux de voir le code que ça donnerait en lisp ou autre, si
quelqu'un connait ?

--
William Dodé - http://flibuste.net
Informaticien Indépendant

Vous avez filtré cet utilisateur ! Consultez son message

On 04-09-2009, Pierre Maurette wrote:

William Dode, le 04/09/2009 a écrit :

[...]

Ça manque de commentaires. Et certaines constantes magiques telles que 400,
100 ou 5 n'aident pas à la lisibilité. Et si on veut changer l'échiquier en
une taille 8x8, il faut changer ces constantes ?

Oui, c'est pour optimiser

Avant que vous ne vous fassiez gronder: je n'ai jeté un oeil qu'en
diagnonale, néanmoins il me semble que vous n'optimisez pas vraiment,
bien au contraire.
Vous écrivez par exemple:

int SIDE=5;
int SQR_SIDE%;

il manque déjà un const:

const int SIDE=5;
const int SQR_SIDE%;

pour augmenter les "chances" que le compilateur optimise. Mais le but
étant de bien montrer clairement ce qui est une constante dès la
compilation, autant faire:

#define SIDE 5
#define SQR_SIDE (SIDE * SIDE)

Je viens d'intégrer ça, mais hélas ça ne change pas grand chose pour le
coup vu qu'il ne se sert pas de ces valeurs pour boucler. Mais ne
serait-ce que pour la lisibilité c'est mieux...

en "centralisant" au maximum (5 et 25 sont redondants, alors que 5 et
(SIDE * SIDE) ne le sont pas). Et en utilisant les macros partout où
c'est possible, ce qui ne me semble pas être le cas dans votre code,
loin s'en faut.

A ce moemnt-là tout ce petit monde sera remplacé avant la compilation
proprement-dite. Vous pouvez d'ailleurs ajouter un:

#define NB_CASES SQR_SIDE

absolument sans aucun coût en performance.

Pourquoi dire clairement au compilateur ce qui est connu, constant à la
compilation ? Pour qu'il puisse entrer dans un processus
d'optimisations pour lesquelles il est en général très doué. Deux
exemple: les multiplications par des constantes entières, pour
lesquelles il génèrera un code machine bien plus rapide que la
multiplication (en x86, le plus souvent un LEA). Si vous demandez une
optimisation en vitesse, il va également développer les boucles "assez
petites" pour peu que le nombre de passage soit connu à la compilation.
A 3, c'est toujours valable, à 5 également, à mon avis. Par exemple, la
boucle:

for(x = 0; x < 5; x++){
f(y, x);
}
(f() remplace du code, pas l'appel d'une fonction nécessairement).

sera compilée comme:
f(y, 0);
f(y, 1);
f(y, 2);
f(y, 3);
f(y, 4);

La fonction qui boucle le plus est déjà avec un #define (nbmove), mais
je me demande si ça joue beaucoup dans le cas d'une fonction récurcive ?

Si je met int nbmove=5; le résultat est identique chez moi...

Je serait curieux de voir le code que ça donnerait en lisp ou autre, si
quelqu'un connait ?

--
William Dodé - http://flibuste.net
Informaticien Indépendant

candide

04/09/2009 à 20:57

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 :

http://www.research.att.com/~njas/sequences/index.html

mais j'ai proposé une soumission au site.

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) ;
2) précalculer les déplacements du cavaliers en fonction de sa case.

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).

Je l'ai aussi écrit en Python et là par contre ton code est plus rapide (19.7 s
contre 6.3 s) mais je ne connais pas (et n'utilise donc pas) le module array qui
parait-il optimise bien. Sans psyco, chez moi c'est très lent 63 s.

Voici les codes :

/* cavalier.c */
#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 afficher(int t[][N])
{
int i, j;

for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
printf("%d ", t[i][j]);
printf("n");
}
}

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];

caseSuivante[lin][col][i][0] = y;
caseSuivante[lin][col][i][1] = x;
nbVoisins[lin][col]++;
}
}
}
}

void nbParcours(int debutx, int debuty)
{
memset(echiquier, 0, N * N * sizeof(int));
echiquier[debuty][debutx] = 1;
suivant(debuty, debutx, 1);
}

int main(void)
{
creerVoisins();
nbParcours(0,0);
nbParcours(1,0);
nbParcours(2,0);
nbParcours(1,1);
nbSol*=4 ;/* symétries */
nbParcours(2,2);
printf("%dn", nbSol);
return 0;
}
-------------------------------------------------------------------
# cavalier.py

import time
s=time.time()

def creerVoisins(N):
sauts= [
(2, 1), (1, 2), (-1, 2), (-2, 1),
(-2, -1), (-1, -2), (1, -2), (2, -1)
]
voisins=dict([((col, lin),[]) for lin in range(N) for col in range(N)])
for (col, lin) in voisins:
for (a,b) in sauts:
if 0<= col + a < N and 0<= lin + b < N:
voisins[(col,lin)]+=[(col+a, lin+b)]
return voisins

N=5
voisins=creerVoisins(N)
nbSol=0
echiquier=dict([((col, lin),0) for lin in range(N) for col in range(N)])

def suivant(pos, casesOccupees):
global nbSol
for v in voisins[pos]:
if echiquier[v]==0:
echiquier[v]=1
if casesOccupees + 1 == N * N:
nbSol+=1
suivant(v, casesOccupees+1)
echiquier[v]=0

def nbParcours(debut):
for z in echiquier:
echiquier[z]=0
echiquier[debut]=1
suivant(debut,1)

def main():
global nbSol
for debut in [(0,0), (1,0), (2,0),(1,1)]:
nbParcours(debut)

nbSol*=4
nbParcours((2,2))

print nbSol

import psyco; psyco.full()
main()
print "%f sn" % (time.time()-s)
#--------------------------------------------------------------------------------

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 :

http://www.research.att.com/~njas/sequences/index.html

mais j'ai proposé une soumission au site.

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) ;
2) précalculer les déplacements du cavaliers en fonction de sa case.

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).

Je l'ai aussi écrit en Python et là par contre ton code est plus rapide (19.7 s
contre 6.3 s) mais je ne connais pas (et n'utilise donc pas) le module array qui
parait-il optimise bien. Sans psyco, chez moi c'est très lent 63 s.

Voici les codes :

/* cavalier.c */
#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 afficher(int t[][N])
{
int i, j;

for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
printf("%d ", t[i][j]);
printf("n");
}
}

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];

caseSuivante[lin][col][i][0] = y;
caseSuivante[lin][col][i][1] = x;
nbVoisins[lin][col]++;
}
}
}
}

void nbParcours(int debutx, int debuty)
{
memset(echiquier, 0, N * N * sizeof(int));
echiquier[debuty][debutx] = 1;
suivant(debuty, debutx, 1);
}

int main(void)
{
creerVoisins();
nbParcours(0,0);
nbParcours(1,0);
nbParcours(2,0);
nbParcours(1,1);
nbSol*=4 ;/* symétries */
nbParcours(2,2);
printf("%dn", nbSol);
return 0;
}
-------------------------------------------------------------------
# cavalier.py

import time
s=time.time()

def creerVoisins(N):
sauts= [
(2, 1), (1, 2), (-1, 2), (-2, 1),
(-2, -1), (-1, -2), (1, -2), (2, -1)
]
voisins=dict([((col, lin),[]) for lin in range(N) for col in range(N)])
for (col, lin) in voisins:
for (a,b) in sauts:
if 0<= col + a < N and 0<= lin + b < N:
voisins[(col,lin)]+=[(col+a, lin+b)]
return voisins

N=5
voisins=creerVoisins(N)
nbSol=0
echiquier=dict([((col, lin),0) for lin in range(N) for col in range(N)])

def suivant(pos, casesOccupees):
global nbSol
for v in voisins[pos]:
if echiquier[v]==0:
echiquier[v]=1
if casesOccupees + 1 == N * N:
nbSol+=1
suivant(v, casesOccupees+1)
echiquier[v]=0

def nbParcours(debut):
for z in echiquier:
echiquier[z]=0
echiquier[debut]=1
suivant(debut,1)

def main():
global nbSol
for debut in [(0,0), (1,0), (2,0),(1,1)]:
nbParcours(debut)

nbSol*=4
nbParcours((2,2))

print nbSol

import psyco; psyco.full()
main()
print "%f sn" % (time.time()-s)
#--------------------------------------------------------------------------------

Vous avez filtré cet utilisateur ! Consultez son message

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 :

http://www.research.att.com/~njas/sequences/index.html

mais j'ai proposé une soumission au site.

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) ;
2) précalculer les déplacements du cavaliers en fonction de sa case.

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).

Je l'ai aussi écrit en Python et là par contre ton code est plus rapide (19.7 s
contre 6.3 s) mais je ne connais pas (et n'utilise donc pas) le module array qui
parait-il optimise bien. Sans psyco, chez moi c'est très lent 63 s.

Voici les codes :

/* cavalier.c */
#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 afficher(int t[][N])
{
int i, j;

for (i = 0; i < N; i++)
{
for (j = 0; j < N; j++)
printf("%d ", t[i][j]);
printf("n");
}
}

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];

caseSuivante[lin][col][i][0] = y;
caseSuivante[lin][col][i][1] = x;
nbVoisins[lin][col]++;
}
}
}
}

void nbParcours(int debutx, int debuty)
{
memset(echiquier, 0, N * N * sizeof(int));
echiquier[debuty][debutx] = 1;
suivant(debuty, debutx, 1);
}

int main(void)
{
creerVoisins();
nbParcours(0,0);
nbParcours(1,0);
nbParcours(2,0);
nbParcours(1,1);
nbSol*=4 ;/* symétries */
nbParcours(2,2);
printf("%dn", nbSol);
return 0;
}
-------------------------------------------------------------------
# cavalier.py

import time
s=time.time()

def creerVoisins(N):
sauts= [
(2, 1), (1, 2), (-1, 2), (-2, 1),
(-2, -1), (-1, -2), (1, -2), (2, -1)
]
voisins=dict([((col, lin),[]) for lin in range(N) for col in range(N)])
for (col, lin) in voisins:
for (a,b) in sauts:
if 0<= col + a < N and 0<= lin + b < N:
voisins[(col,lin)]+=[(col+a, lin+b)]
return voisins

N=5
voisins=creerVoisins(N)
nbSol=0
echiquier=dict([((col, lin),0) for lin in range(N) for col in range(N)])

def suivant(pos, casesOccupees):
global nbSol
for v in voisins[pos]:
if echiquier[v]==0:
echiquier[v]=1
if casesOccupees + 1 == N * N:
nbSol+=1
suivant(v, casesOccupees+1)
echiquier[v]=0

def nbParcours(debut):
for z in echiquier:
echiquier[z]=0
echiquier[debut]=1
suivant(debut,1)

def main():
global nbSol
for debut in [(0,0), (1,0), (2,0),(1,1)]:
nbParcours(debut)

nbSol*=4
nbParcours((2,2))

print nbSol

import psyco; psyco.full()
main()
print "%f sn" % (time.time()-s)
#--------------------------------------------------------------------------------

C ou Python

10 réponses

Veuillez sélectionner un problème