Discussion :

[le Daoud]

Bonjour,

Je suis entrain de coder un jeu de reflexion type echecs. Je voudrais savoir quels sont les élements au niveau langage que je pourrais améliorer pour augmenter les performances de l'analyse.

Par exemple, une exception qui est levée puis catchée prend-elle beaucoup de temps, vaut-il mieux faire un test préalable ? Dans mon programme, si une pièce essaye d'aller sur une case qui n'existe pas, une exception ArrayIndexOutOfBound est levée puis catchée, est-ce trop consommateur ?
Un ArrayList offre-t-il un accès rapide comme un tableau ?
D'autres idées ?

merci
daoud

[Alwin]

Il est toujours préférable de tester des bornes plutôt que de catcher un ArrayOutOfBoundException oui, ainsi que toutes autres exceptions ne serais-ce que pour éviter l'instanciation de la classe d'exception ( l'instantiation est couteuse ) !

Quand à l'utilisation de List ( ou dérivé ) en lieu et place d'un tableau n'est pas justifiée dans ton cas car tu est sur un tableau à limites déterminées et de taille très réduite ( 8x8 )

Enfin, ceci n'est qu'un avis qui n'engage que moi

[le Daoud]

Merci pour ta réponse

Je vais changer pour les exceptions.
Sinon, le plateau du jeu n'est pas un échiquier (=>dvonn), mais a une structure irrégulière et les pièces se déplacent en fonction de la hauteur d'une pile de pièce. J'ai codé cela avec un tableau, d'où ma gestion d'exception. Mais j'ai aussi créé une List qui contient uniquement les pièces que l'on peut déplacer pour gagner du temps.

a+
daoud

[Glob]

Hello.
Principalement:
1) Éviter des instanciations d'objets ("new" et quasi toutes les opérations sur String)
2) Éviter les méthodes récursives (pas forcément applicable à une IA type alpha-beta)
3) Si tu as des listes à parcourir en entier, bosse avec des ArrayList; pour les parcourir, utilise toArray() et parcours le tableau obtenu (peut-être pas compatible avec le point 1, j'ai pas vérifié si on obtient une copie du tableau interne).
++

[jcarre]

dans le Commons Collection d'Apache, il me semble qu'il y a des Fast Array qui ont un mode lecture/écriture et un lecture seule bcp plus rapide.

[Glob]

Merci pour le lien.

http://jakarta.apache.org/commons/collections/apidocs-COLLECTIONS_3_1/org/apache/commons/collections/FastArrayList.html


Cependant, pour des opérations avec un seul thread, le bon vieux ArrayList est plus rapide... et plus portable...

[benohite]

Bonjour,

Comme tout le monde l'a dit ici, les tableaux sont bien plus rapides que les listes car tu accède à un élément en une unité de temps (t[i]). Alors que dans une liste, il te faut parcourir tous les éléments jusqu'à tomber sur celui que tu recherches.

Sinon, le plateau du jeu n'est pas un échiquier (=>dvonn), mais a une structure irrégulière et les pièces se déplacent en fonction de la hauteur d'une pile de pièce. J'ai codé cela avec un tableau, d'où ma gestion d'exception. Mais j'ai aussi crée une List qui contient uniquement les pièces que l'on peut déplacer pour gagner du temps.

Vu la structure de "l'échiquer", une matrice ne serait pas je pense une bonne idée. Si j'ai bien compris la hauteur de chaque case est variable et donc tu risques de te retrouver avec une grosse matrice peu remplie.
Je pense (et ca n'engage que moi ) que le plus éfficace serait de créer un tableau de listes.
Ainsi tu as un accés direct à chaque case et aprés un parcours pour la hauteur.

(peut-être pas compatible avec le point 1, j'ai pas vérifié si on obtient une copie du tableau interne)

On obtiens bien une copie:

Code :

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

1
2
3
4
5
6
 
    public Object[] toArray() {
	Object[] result = new Object[size];
	System.arraycopy(elementData, 0, result, 0, size);
	return result;
    }

Bon courage

Ben

[KiLVaiDeN]

Cependant, pour des opérations avec un seul thread, le bon vieux ArrayList est plus rapide... et plus portable...

J'ai fais plusieurs applications avec les collections de jakarta, et dans tous les cas ça s'est avéré plus rapide que ceux de base de Java ( notamment lors du changement de mode de lecture seule ).
Et en ce qui concerne la portabilité, je ne vois pas en quoi elle serait impactée, aurais-tu une argumentation à ce sujet ? Non pas que je veuille te contredire, mais je serais curieux de savoir ce qui te fait penser celà.

K

[adiGuba]

Salut,

Comme tout le monde l'a dit ici, les tableaux sont bien plus rapides que les listes car tu accède à un élément en une unité de temps (t[i]). Alors que dans une liste, il te faut parcourir tous les éléments jusqu'à tomber sur celui que tu recherches.

Juste une petite rectification : Cela dépend de quelle implémentation de List tu utilises...
Les ArrayList utilisent des tableaux et la différence est donc minime avec l'utilisation d'un tableau standard...

Pour plus d'info, voir http://java.developpez.com/faq/java/...IONS_info_list.

a++

[benohite]

Effectivement je parlais de listes dans le sens du C, c'est a dire des listes chainées (via pointeurs) et non des tableaux deguisées : ).


Ben

[Glob]

Cependant, pour des opérations avec un seul thread, le bon vieux ArrayList est plus rapide... et plus portable...

J'ai fais plusieurs applications avec les collections de jakarta, et dans tous les cas ça s'est avéré plus rapide que ceux de base de Java ( notamment lors du changement de mode de lecture seule ).
Et en ce qui concerne la portabilité, je ne vois pas en quoi elle serait impactée, aurais-tu une argumentation à ce sujet ?
K

Hello.
Pour la portabilité, je me réfère simplement à la javadoc du FastArray:

NOTE: This class is not cross-platform.

Maintenant, peut-être que cette info est fausse ou que... bref.

En ce qui concerne la vitesse, j'ai pas eu (et j'aurai pas avant longtemps) le temps de faire des tests, mais je reste persuadé qu'un ArrayList.toArray() suivi d'un parcours du tableau ainsi obtenu reste plus rapide. Sauf peut-être dans le cas inintéressant où l'on a 3 éléments.

J'ai du mal à concevoir qu'il existe quelque chose de plus rapide qu'un tableau[] pour accéder à des éléments de façon indexée, ou pour parcourir une liste. Même le parcours ordré d'une liste par pointeur nécessite des additions d'adresses mémoire.

Je ne suis pas même certain de pouvoir obtenir de meilleurs résultats avec une méthode native en C++: le changement de contexte d'exécution Java -> C -> Java a un coût...

M'enfin, pour un jeu d'échec ça doit pas être critique à ce point, c'est quand même pas un MMORPG (sans vouloir dénigrer)

[jcarre]

sinon, une méthode qui n'a rien a voir, tu peux faire en sorte que les éléments de ton tableau réagissent à un evenement donné. ensuite tu lance l'événement sur tous tes éléments et tu récupère ceux qui ont répondu.

[le Daoud]

Merci à vous pour vos réponses.

En ce qui concerne les exceptions le gain de temps à été très net.
Pour les tableaux, la différence est moins importante mais tout de même significative pour la mettre en oeuvre. Par exemple pour une même position avec le même nombre de noeuds explorés j'ai gagné 10% de temps sur la fonction d'évaluation.
Voici la partie du code modifiée avec en commentaire ce qu'il y avait avant :

Code :

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

1
2
3
4
5
6
7
 
//Iterator iter = plateau.getCasesJouables().iterator();
Object[] tab = plateau.getCasesJouables().toArray();
//while(iter.hasNext()){
for(int i = 0; i < tab.length; i++){
  //c = (Case)iter.next();
  c = (Case)tab[i];

peut-être que la différence aurait été moins significative si j'avais utilisé l'accès direct aux éléments plutôt que l'itérateur, mais je ne crois pas.

Sinon je réflechis à ton idée jcarre, mais je ne suis pas sur de l'avoir bien saisie.

Merci à tous

daoud

[thulsadoom]

je ne vois pas l'interet du toArray() qui provoque une recopie du tableau.
Tu utilises une ArrayList, classe qui implemente RandomAccess. Or toute liste qui implemente cette interface sera parcourue plus rapidement par un "for( ...) { la_liste.get(i) ... }" que par un iterateur. Passer par un tableau te fournis certe un gain par rapport a un iterateur, mais le for/get est encore meilleur. Dans tous les cas, l'iterateur est a proscrire pour toutes les listes de l'API standard, a l'exception des LinkedList, seules listes a ne pas implementer RandomAccess.