Logo GNT
Actualités Tests & Guides Bons Plans
GTA 6 iPhone 17 Copilot Switch 2 Temu ChatGPT Tesla
OVH Cloud OVH Cloud
Entraide Développement Développement Langage C++ Améliorer la vitesse ?

Améliorer la vitesse ?

43 réponses
Avatar
ByB
Bonjour,

Je suis curieux de savoir si en remplaçant deux boucles imbriquées :

for (int i = 0;i<8;i++)
{

for (int j=0;j<8;j++)
{
FaireQuelqueChose(i,j);

}

}

par une seule boucle :

int i,j;
for (int x = 0;x<64;x++)
{

i = x % 8;
j = x/8;

FaireQuelqueChose(i,j);

}

je gagne quelque chose (en particulier en vitesse d'exécution du
programme) ou si cela ne change rien ?

Merci.


--
Ladra que muerde no perra. (Chespirito)
Signaler un problème avec ce contenu

10 réponses

Supprimer
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire

Veuillez sélectionner un problème

Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
1 2 3 4 5
Avatar
kanze
Sylvain wrote:
ByB wrote on 29/07/2006 03:15:

Je suis curieux de savoir si en remplaçant deux boucles imbriquées :
par une seule boucle :

int i,j;
for (int x = 0;x<64;x++){
i = x % 8;
j = x/8;
}


la division et plus encore le modulo compte bcp plus chers que le calcul
d'indice.


La division et le modulo (par une puissance de deux) sont une
seule instruction chacune. Selon les processeurs, on pourrait
bien y gagner. Ou non, selon le processeur. (Que la différence
soit significative, c'est une autre question. Note aussi que le
nombre de règistres dont dispose le processeur joue un rôle
aussi. Si le compilateur est obligé de garder l'indice de la
boucle exterieur en mémoire, plutôt que dans un règistre, ça ne
va pas améliorer les choses.)

(À titre indicatif : sur Sun Sparc sous Solaris, la boucle avec
/ et % a besoin de huit fois plus de temps que les boucles
embriquées avec g++ et d'environ 3,5 fois plus avec Sun CC ;
sur un PC sous Linux, en revanche, avec g++, la boucle avec / et
% a besoin de moins de temps. Je n'ai pas régardé le code
généré, mais ça ne m'étonnerait pas que la différence soit du au
fait que le PC n'a que 8 régistres, tandis que le Sparc en a
32.)

remplacer 2 boucles par une (est généralement inutile) et
passerait plus par un remplacement de 'int grid[8](8]' par
'int grid[64]'.


C'est effectivement généralement inutile. Mais il y a des cas.

note; si vous ne trouvez pas de profiler, vous pouvez insérer qlq

long globalElapseN = 0L;
...

struct _timeb start;
_ftime(&start);

uneGrosseMethode();

struct _timeb end;
_ftime(&end);

globalElapseN += 1000L * (end.time - start.time) + end.millitm -
start.millitm;


Encore une fois, ce n'est pas du C++ que tu présentes, mais une
extension propre à une implémentation. Les noms qui commence par
un _ doit en être un avertissement. (Aussi, les struct font
penser à C ; il ne sont pas nécessaire en C++.)

En C++, on écrira :

clock_t begin = clock() ;
fonctionAMesurer() ;
clock_t end = clock() ;
double elapsed
= static_cast< double >(end - begin)
/ static_cast< double >( CLOCKS_PER_SECOND ) ;

(Ça donne le temps en secondes.)

Ce qu'on mesure réelement dépend un peu du système : sous
Windows, c'est le temps total passé ; sous Unix, le temps CPU
d'exécution. De même que la granularité : sous Unix,
CLOCKS_PER_SECOND est prèsque toujours 1000000, mais ça ne veut
pas réelement dire que tu puisses mesurer au milliséconde près.

et mesurer ainsi via qlq compteurs la méthode qui consume
(globalement) le plus, une fois localisée vous raffinez en
mésurant ses sous fonctions (cela ne mesure toutefois que des
temps > à la ms; si les méthodes sont plus rapides (ou si
l'organisation globale ne permet pas d'isoler des méthodes
tournant en ce temps) la méthode est inapplicable.


C'est possible, faute d'autre chose. Ça prend un temps énorme,
en revanche, pour obtenir les informations qu'on a directement
d'un seul essai avec le profileur.

Si on veut comparer le temps d'exécution de deux algorithmes ou
de deux solutions (ou plus), c'est une bonne technique, à
condition de prendre assez de précautions pour s'assurer que le
compilateur ne supprime pas ce que tu veux mesurer à titre
d'optimisation.

--
James Kanze GABI Software
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


Avatar
ByB
Mieux que du Shakespeare, c'est le message de Bruno Causse qui affirme
:
ByB wrote:

Merci pour vos conseils.
En fait, je suis en train de développer un programme qui joue à
l'Othello, et je remarque que l'ordinateur met pas mal de temps à
trouver le coup qu'il veut jouer.
Mon code est plein de parcours du tableau de jeu (de 8x8 cases) et je
cherchais un moyen d'accélérer les choses ...


bonjours,

un prog d'othello tres bonne idee ;-)

pour ameliorer la vitesse, la premiere chose a faire est de structurer
correctement les données.

pour la representation de l'othellier voir "mailbox" ou "bitboard" pour
commencer. un tableau 8*8 n'est pas une bonne idée (a la limite 10*10).

ensuite si ca t'interesse j'ai plein de liens


Bonjour,

Pour la représentation des données, c'est un peu tard pour changer, car
la plupart de mes algorithmes sont au point sur le damier 8x8.
En fait, j'en suis (à peu de choses près) à l'optimisation du code coté
ordi pour qu'il puisse jouer en un temps ... raisonnable (1 à 5
secondes ?)

--
Les familles, l'été venu, se dirigent vers la mer en y emmenant leurs
enfants, dans l'espoir, souvent déçu, de noyer les plus laids.
(Alphonse Allais)


Avatar
ByB
Désormais, et grace à ByB, le monde entier sait que
Mieux que du Shakespeare, c'est le message de Bruno Causse qui affirme :
ByB wrote:

Merci pour vos conseils.
En fait, je suis en train de développer un programme qui joue à l'Othello,
et je remarque que l'ordinateur met pas mal de temps à trouver le coup
qu'il veut jouer.
Mon code est plein de parcours du tableau de jeu (de 8x8 cases) et je
cherchais un moyen d'accélérer les choses ...


bonjours,

un prog d'othello tres bonne idee ;-)

pour ameliorer la vitesse, la premiere chose a faire est de structurer
correctement les données.

pour la representation de l'othellier voir "mailbox" ou "bitboard" pour
commencer. un tableau 8*8 n'est pas une bonne idée (a la limite 10*10).

ensuite si ca t'interesse j'ai plein de liens


Bonjour,

Pour la représentation des données, c'est un peu tard pour changer, car la
plupart de mes algorithmes sont au point sur le damier 8x8.
En fait, j'en suis (à peu de choses près) à l'optimisation du code coté ordi
pour qu'il puisse jouer en un temps ... raisonnable (1 à 5 secondes ?)


Pour les liens, ça m'intéresse toujours ... :-)

--
Pour la chasse aux lions : vous achetez un tamis et vous allez dans le
désert. Là, vous passez tout le désert au tamis. Quand le sable est
passé, il reste les lions.
[Alphonse Allais]



Avatar
Fabien LE LEZ
On Tue, 01 Aug 2006 23:02:40 +0200, ByB :

Pour la représentation des données, c'est un peu tard pour changer, car
la plupart de mes algorithmes sont au point sur le damier 8x8.


Si le programme ne remplit pas le cahier des charges (ici, la vitesse
d'exécution), il ne fonctionne pas, point. Tu ne peux donc pas
prétendre que tes algorithmes sont au point.
Par ailleurs, si modifier les structures de données casse tout ton
programme, tu as peut-être un problème plus profond -- le manque de
généricité de ton code.

Idéalement, une classe a un nombre réduit de fonctions qui permettent
d'accéder indirectement à ses données internes. La structure de ces
données n'a guère d'importance ; si elle change pour une raison ou une
autre, on change l'implémentation des fonctions membres (quelques
lignes) et le code client n'a pas à être modifié.
Si le profiler indique qu'une fonction bien précise est trop lente,
alors on pourra "bricoler" pour que cette fonction accède directement
à la cuisine interne de la classe, pour pouvoir l'accélérer. Elle
pourra même dicter la structure de données, sans casser le reste du
code.

Avatar
Bruno CAUSSE
dans l'article , ByB à a
écrit le 1/08/06 23:03 :

Pour la représentation des données, c'est un peu tard pour changer, car la
plupart de mes algorithmes sont au point sur le damier 8x8.
En fait, j'en suis (à peu de choses près) à l'optimisation du code coté ordi
pour qu'il puisse jouer en un temps ... raisonnable (1 à 5 secondes ?)



tôt ou tard, si tu portes de l'intérêt a ton programme il faudra changer.
Je programme ce type de jeu depuis 4/5 ans (avec un certain succès) et j'ai
changer plusieurs fois la structure de mes données.


Pour les liens, ça m'intéresse toujours ... :-)


Pour commencer, va son mon site

http://hcyrano.free.fr/concepts/Ressources.html


Avatar
kanze
Fabien LE LEZ wrote:
On Tue, 01 Aug 2006 23:02:40 +0200, ByB :

Pour la représentation des données, c'est un peu tard pour
changer, car la plupart de mes algorithmes sont au point sur
le damier 8x8.


Si le programme ne remplit pas le cahier des charges (ici, la vitesse
d'exécution), il ne fonctionne pas, point. Tu ne peux donc pas
prétendre que tes algorithmes sont au point.
Par ailleurs, si modifier les structures de données casse tout ton
programme, tu as peut-être un problème plus profond -- le manque de
généricité de ton code.


De l'encapsulation, plutôt que de la généricité, non ? Si
modifier une structure de donnée implique changer tout, partout,
c'est que cette structure de donnée n'a pas été correctement
encapsulée (et que le code n'est pas, dans la pratique,
maintenable).

--
James Kanze GABI Software
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


Avatar
Fabien LE LEZ
On 2 Aug 2006 01:00:04 -0700, "kanze" :

De l'encapsulation, plutôt que de la généricité, non ?


Disons que je m'attachais plus particulièrement à un des avantages de
l'encapsulation, qui est la généricité (c'est-à-dire l'indépendance du
code client par rapport à la structure interne des données).

Avatar
Laurent Deniau
Fabien LE LEZ wrote:
On 2 Aug 2006 01:00:04 -0700, "kanze" :


De l'encapsulation, plutôt que de la généricité, non ?



Disons que je m'attachais plus particulièrement à un des avantages de
l'encapsulation, qui est la généricité (c'est-à-dire l'indépendance du
code client par rapport à la structure interne des données).


Pour reprendre tes termes, la genericite c'est la (relative)
independance du code "interne" (e.g. de l'algorithme) par rapport au
code/structure client, le fameux "write-once, use everywhere". Reste a
definir ce que tu entends par "interne".

C'est donc bien de l'encapsulation dont il s'agit, eventuellement avec
un soupcon de parametrisation.

a+, ld.


Avatar
Fabien LE LEZ
On Wed, 02 Aug 2006 14:59:29 +0200, Laurent Deniau
:

C'est donc bien de l'encapsulation dont il s'agit, eventuellement avec
un soupcon de parametrisation.


Dans l'exemple qui nous occupe, la généricité est le but, et
l'encapsulation un moyen d'atteindre ce but.

Avatar
Laurent Deniau
Fabien LE LEZ wrote:
On Wed, 02 Aug 2006 14:59:29 +0200, Laurent Deniau
:


C'est donc bien de l'encapsulation dont il s'agit, eventuellement avec
un soupcon de parametrisation.



Dans l'exemple qui nous occupe, la généricité est le but, et
l'encapsulation un moyen d'atteindre ce but.


Un exemple ou l'encapsulation (et uniquement l'encapsulation) permet de
rendre un code generique? L'encapsulation est une fermeture tandis que
la genericite est une substitution (i.e. plusieurs formes), deux
concepts complementaires, orthogonaux et tres precieux (cf. la multitude
de papiers sur l'integration et l'extension de code).

a+, ld.


1 2 3 4 5