Optimisation de code

**Flow_75** · 14/02/2012, 22h47

Bonjour,

Je travaille actuellement sur un algorithme que j'utiliserai dans une application Android. (alias A*)
Y a t-il possibilité d'optimiser le code obtenu ?

Merci de votre renseignement.
Flo.

**guigz2000** · 16/02/2012, 13h53

Qu'entends tu par "Optimiser le code obtenu"?

Si tu utilises un algorithme standard, il y a peu de chances que tu arrives a l'optimiser beaucoups.

Ensuite,ca depends des structures de donnée que tu utilises et de ta manière de coder.
Sans code, c'est assez délicat de te répondre...

**Flow_75** · 16/02/2012, 13h54

Merci de ta réponse.

Je le posterai ce soir.

**atha2** · 16/02/2012, 15h43

Tu peux jeter un coup d’œil au NDK pour du développement natif (C/C++) sur Android.

EDIT :
@guigz2000 : je suis complétement d'accord avec toi. Je propose le NDK car Flob91 cherche un moyen

d'optimiser le code obtenu

et comme tu le dis dans ton poste précédent, si Flob91 utilise un algo connu, normalement on doit pas pouvoir l'optimiser. Après sans le code on ne peut pas vraiment savoir.

PS : quelqu'un sait comment on peut faire une citation au sein d'une ligne ?

**guigz2000** · 16/02/2012, 18h34

Perso, avant de me lancer dans une appli native, j'essaierai avec java.
Si le resultat est trop lent, alors effectivement passe en C++.

L'integration dans eclipse (ADT) est bien faite et ca te permettra de debugger plus facilement. Tu pourras utiliser ddms pour faire un profiling de ton code et voir les goulots d'étranglement. En plus, quand tron algorithme sera bien au point,ca sera très simple de passer au C++.

**Flow_75** · 16/02/2012, 22h26

Envoyé par guigz2000

Perso, avant de me lancer dans une appli native, j'essaierai avec java.
Si le resultat est trop lent, alors effectivement passe en C++.

L'integration dans eclipse (ADT) est bien faite et ca te permettra de debugger plus facilement. Tu pourras utiliser ddms pour faire un profiling de ton code et voir les goulots d'étranglement. En plus, quand tron algorithme sera bien au point,ca sera très simple de passer au C++.

Merci pour vos réponses.
Juste une question peut on faire (par exemple) un morceau de l'application en C++ et le reste en Java ?

Sinon voila mon algorithme, il s'agit de la création d'un labyrinthe (X par Y cases).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
   	Random random = new Random();
    	int d;
    	int frompropagate = 0, topropagate = 0;
 
    	isFinished = false;
    	isSolved   = false;
    	initialisation();
 
	    do
    	{
    		int x = 0;
    		int y = 0;
 
    		do
    		{
    			x = random.nextInt( (2*X)-1 )+1;
    			y = random.nextInt( (2*Y)-1 )+1;
    		}
    		while(  !(( x%2==1)^(y%2==1)) || Labyrinthe[x][y]!=-1);
 
    		if( x%2 == 1)
    		{
    			d = Labyrinthe[x][y-1] - Labyrinthe[x][y+1];
 
    			if(d > 0)
    			{
    				Labyrinthe[x][y] = Labyrinthe[x][y+1];
    				frompropagate = Labyrinthe[x][y+1];
    				topropagate = Labyrinthe[x][y-1];
    			}else if(d<0)
    			{
    				Labyrinthe[x][y] = Labyrinthe[x][y-1];
    				frompropagate = Labyrinthe[x][y-1];
    				topropagate = Labyrinthe[x][y+1];
    			}
    		}
    		else
    		{
    			d = Labyrinthe[x-1][y] - Labyrinthe[x+1][y];
 
    			if( d>0 )
    			{
    				Labyrinthe[x][y] = Labyrinthe[x+1][y];
    				frompropagate = Labyrinthe[x+1][y];
    				topropagate = Labyrinthe[x-1][y];
    			}else if( d<0 )
    			{
    				Labyrinthe[x][y] = Labyrinthe[x-1][y];
    				frompropagate = Labyrinthe[x-1][y];
    				topropagate = Labyrinthe[x+1][y];
    			}
    		}
 
    		for(int i = 0; i <  (2*X)+1 ; i++)
          	{
            	for(int j = 0; j < (2*Y)+1; j++)
          		{
            		if(Labyrinthe[i][j] == topropagate)
            		{
            			Labyrinthe[i][j] = frompropagate;
            		}
          		}
    		}
    	}
    	while ( !isComplete());
 
    	isFinished = true;
 
    	return true;
    }
 
    private boolean isComplete()
    {  	
    	for(int i = 0; i < (2*X)+1; i++)
    	{
    		for(int j = 0; j < (2*Y)+1; j++)		
    		{
    			if(Labyrinthe[i][j] != 0 && Labyrinthe[i][j] != -1)
    			{
    				return false;
    			}
    		}
    	}
 
    	return true;
    }

**atha2** · 17/02/2012, 01h01

Envoyé par Flob91

Merci pour vos réponses.
Juste une question peut on faire (par exemple) un morceau de l'application en C++ et le reste en Java ?

Aucune idée, je n'ai jamais eu besoin de l'utiliser.
Voici en vert quelque commentaire / modif:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
       
final Random random = new Random();// Aide le compilateur à optimiser
        int d;
        int frompropagate = 0, topropagate = 0;

        isFinished = false;
        isSolved   = false;
        initialisation();
        
        do
        {
            int x = 0;
            int y = 0;
            
            do
            {
                x = random.nextInt( (2*X)-1 )+1;// X est-il déclaré en tant que constante (final static) ?
                y = random.nextInt( (2*Y)-1 )+1;// pareil pour Y ? Si ce n'est pas le cas (et si ce n'est pas possible) il vaux mieux calculer l'expression avant la boucle. C'est le cas pour toutes les expressions contenant X et Y. Et tant qu'a faire, stocks le résultat dans une variable final.
            }
            while(  !(( x%2==1)^(y%2==1)) || Labyrinthe[x][y]!=-1);
            // !(( x%2==1)^(y%2==1)) <=> x%2 == y%2 <=> (x-y)%2 == 0
                    
            if( x%2 == 1)
            {
                d = Labyrinthe[x][y-1] - Labyrinthe[x][y+1];
                
                if(d > 0)
                {
                    Labyrinthe[x][y] = Labyrinthe[x][y+1];
                    frompropagate = Labyrinthe[x][y+1];
                    topropagate = Labyrinthe[x][y-1];
                }else if(d<0)
                {
                    Labyrinthe[x][y] = Labyrinthe[x][y-1];
                    frompropagate = Labyrinthe[x][y-1];
                    topropagate = Labyrinthe[x][y+1];
                }
            }
            else
            {
                d = Labyrinthe[x-1][y] - Labyrinthe[x+1][y];

                if( d>0 )
                {
                    Labyrinthe[x][y] = Labyrinthe[x+1][y];
                    frompropagate = Labyrinthe[x+1][y];
                    topropagate = Labyrinthe[x-1][y];
                }else if( d<0 ) // ici equivalent à d != 0, sur certain système ça peux être avantageux
                {
                    Labyrinthe[x][y] = Labyrinthe[x-1][y];
                    frompropagate = Labyrinthe[x-1][y];
                    topropagate = Labyrinthe[x+1][y];
                }
            }
                
            for(int i = 0; i <  (2*X)+1 ; i++)// pareil que plus haut X est-il constant ?
              {
                for(int j = 0; j < (2*Y)+1; j++)
                  {
                    if(Labyrinthe[i][j] == topropagate)
                    {
                        Labyrinthe[i][j] = frompropagate;
                    }
                  }
            }
        }
        while ( !isComplete());
        
        isFinished = true;
        
        return true;
    }
      
    private boolean isComplete()
    {      
        for(int i = 0; i < (2*X)+1; i++)
        {
            for(int j = 0; j < (2*Y)+1; j++)        
            {
                if(Labyrinthe[i][j] != 0 && Labyrinthe[i][j] != -1)
                {
                    return false;
                }
            }
        }
        
        return true;
    }

Pour ce qui est de l'algo en tant que tel, je ne me rappel plus du fonctionnement de A*, donc je ne vais pas pouvoir t'aider. Par contre il existe HPA* qui apparemment est 10 fois plus rapide et est quasiment aussi bon.

**Flow_75** · 17/02/2012, 09h33

Merci de tes conseils.

Tu auras remarqué évidemment qu'il ne s'agit pas de l'algo A*, mais d'un algo pour faire un labyrinthe.

A* est utilisé pour pouvoir le résoudre...

**atha2** · 17/02/2012, 10h25

Je t'avoue que non ;comme jte disais je l'ai vu il y a un bout de temps

Je pensais que tu t'en servais pour générer des grilles résolvables (génération aléatoire de grilles, on ne garde que celles avec une solution).

**Flow_75** · 17/02/2012, 11h42

Envoyé par atha2

Je t'avoue que non ;comme jte disais je l'ai vu il y a un bout de temps

Je pensais que tu t'en servais pour générer des grilles résolvables (génération aléatoire de grilles, on ne garde que celles avec une solution).

oui ca genere des grilles resolvables.
Après j'utilise A* pour pouvoir afficher la solution au joueur.

**guigz2000** · 17/02/2012, 13h09

Hello,

Memes remarque que Flob.

essaie de faire un preprocessing pour certaines valeurs.(optimisation classique)
ton 2*X (X est une constante?) peut etre précalculé dans une variable locale ou une autre constante.
Ca te fais economiser une multiplication à chaque iteration de la boucle.

Oui,tu peux faire une partie en java et une en C++.
Il faut utiliser "JNI".En gros, tu vas creer des fonctions en C++ et les appeler en java.
C'est assez lourd a gerer (ca oblige a avoir le SDK et le NDK) et c'est pas la panacée non plus.Un appel de fonction JNI est plus lent qu'une fonction java et moins protègé(je te parle meme pas du debuggage!).C'est interessant quand tu as un gros bout de code très lourd a effectuer en C++.Pour une petite fonction simple,aucun interet.

**Flow_75** · 17/02/2012, 14h46

Envoyé par guigz2000

Oui,tu peux faire une partie en java et une en C++.
Il faut utiliser "JNI".En gros, tu vas creer des fonctions en C++ et les appeler en java.
C'est assez lourd a gerer (ca oblige a avoir le SDK et le NDK) et c'est pas la panacée non plus.Un appel de fonction JNI est plus lent qu'une fonction java et moins protègé(je te parle meme pas du debuggage!).C'est interessant quand tu as un gros bout de code très lourd a effectuer en C++.Pour une petite fonction simple,aucun interet.

En faite, le NDK serai pour la partie de création du Labyrinthe. Cette partie là je l'ai en Java et en c/c++. Je sais qu'elle marche correctement.
Donc il y aurai juste passage des paramètres (X/Y) et ensuite en retour d'un tableau avec le labyrinthe generé.

**guigz2000** · 18/02/2012, 18h05

Hello,

Si tu es interesse par le mix Java/C++, voila un petit tuto pour commencer a apprehender la chose.

http://mobile.tutsplus.com/tutorials.../ndk-tutorial/

Optimisation de code

Android

Discussions similaires

Partager

Partager