Un bon développeur est un développeur flemmard !

Dans un puzzle, le problème récurant est de trouver les pièces qui correspondent à un set de 4 contraints.

L'algorithme intuitif est de prendre l'ensemble des pièces et de les tester une par une.

Le cas Eternity II :

• Les bords peuvent prendre 23 formes différents numéroté de (0 à 22)
• Il y a 256 pièces.

La différence principale avec un puzzle classique c'est qu'il existe plusieurs pièces possibles pour chaque contrainte. Est pas de vérification visuel possible !

Cependant, il y a moyen de faire beaucoup plus efficace...
L'idée de la liste "cache" :
Ma première idée étant d'avoir un hash unique pour chaque set de contraints et de rechercher le hash dans une liste prédéfinit.
(Astuce : La contrainte "libre" étant numéroté 23.)
L'optimisation est efficace, mais on perd du temps à générer les hash (création, recherche etc...)
Voici la fonction de hash testé :

Code java :

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

1
2
3
static int Hash(int a, int b, int c,int d) {
	return ((a<< 18)+(b<< 12)+(c<< 6)+d);
}

Le Hash circulaire :
J'ai cherché à avoir un hash identique pour les rotation circulaires des contraintes, afin de réduire la taille de la liste. Cependant, après vérification, il y a des collisions de hash. Ce qui demande donc d'avoir un hash plus complexe à calculer. Ce qui et justement ce qu'on cherche à éviter.
Ce fût pour moi une mauvaise piste.

La matrice "cache":
L'idée de la matrice est une variante de la liste "cache". Le principe est d'avoir une matrice de "solutions" à N dimension où N est le nombre de contraint.

@tbc92 : Merci pour l'idée !

Voici la définition de mon cache :

Code java :

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

1
2
3
4
5
6
7
8
9
	// Top / Left / Bottom / Right / Id de la pièce de la solution X [0..n]
	private static int[][][][][] cacheIdSolutions;
	// Top / Left / Bottom / Right / Orientation de la solution X [0..n]
	private static Orientation[][][][][] cacheOrientationSolutions;
	{
		// Début de l'initialisation du cache
		cacheIdSolutions = new int[24][24][24][24][0];
		cacheOrientationSolutions = new Orientation[24][24][24][24][0];
	}

Ainsi, pour avoir l'ensemble des pièces possible pour un endroit. On ne fait que 4 accès mémoires. (Il faut cependant vérifier leur disponibilité.)
C'est pour cela qu'au lieu d'utiliser une liste pour les pièces disponibles, je suis passé à un tableau basé sur les ID des pièces :

Code Java :

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

OrientedPiece[] pieces = new OrientedPiece[257];// Id de 1 à 256

On a donc un accès O(1) aux pièces à partir des ID à la place d'un accès O(n) !

Impacte mémoire :
Analyse avec Java VisualVM :

Multiplication en 3 et 4 de l’espace mémoire utilisé au total pour l'application. (Allocation pour le cache en lui-même => 14 062 804 Bytes)
Note : Les rampes sont dû à la génération de String pour la sortie console. (Need feed back ^^)

Impacte sur la vitesse de traitement :
L'unité de mesure que j'utilise pour calculé l’efficacité de mon algorithme par rapport à sa rapidité est le nombre de pièce placée. Je ne mesure pas celui-ci précisément en fonction du temps. (Je pourrai, mais je n'ai pas mise en place le code correspondant.) Mais, il m'est facile d'avoir une moyenne assez propre :

1 368 pièces/seconde sans cache (moyenne sur 1 minute)
136 504 pièces/seconde avec cache matriciel (moyenne sur 1 heure)

On est donc sur un facteur 100. Bien qu'il y ai eu d'autres amélioration dans la gestion globale entre les deux implémentations. Celle-ci étant orienté consommation mémoire et réutilisation d'objet, qui représente une amélioration d'environ 2 à 4% après l'évolution du cache. Cela est principalement dû au fait que le Garbage Collector a beaucoup moins de travail, sur une partie qui est beaucoup plus utilisé du fait de l'ajout du cache.

Processus d'optimisation appliqué :
Avant de partir sur cette optimisation spécifique, J'ai analysé mon programme afin d'isoler les fonctions consommatrices, ainsi que la dynamique de mon programme. L'idée étant d'avoir une optimisation là où il y a un impact majeur pour le programme.
Pour cela, Java VisualVM est un outil redoutable (pour java) !
D'ailleurs voici la comparaison de l'utilisation du CPU :

Les deux fonctions placePieceByHeatmap() sont identique en contenu et sont les fonctions "top level". On passe donc de 0.6% à faire du "top level" à "10,6%". Le mieux serai d'avoir 90/10 et non 10/90 comme actuellement !

Les limites du cache :
Le temps de création
Il serai possible de crée un cache basé sur un groupe de pièce et pas uniquement sur une pièce seulement. C'est d'ailleurs l'une des pistes d'optimisation que je teste en ce moment. Plus la taille de ce cache augment, plus le temps de création de celui-ci est à prendre en compte. Actuellement celui-ci est inférieur à la seconde et le programme tourne sur plusieurs heures. Cependant, ma première estimation pour un cache matriciel de 4 pièces (8 contraintes) est de 10¹¹unités mémoires (int/octect/bytes peu importe). Et la structure ressemblerai à ceci :

Code java :

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

1
2
	// Top 1/2 / Left 1/2 / Bottom 1/2 / Right 1/2 / Id de la pièce de la solution X [0..n]
	private static int[][][][][][][][][] cacheIdSolutions;

Pas sûr que cela soit une bonne idée ! Mais je testerai probablement... Dans tout les cas, le temps de création du cache ne sera plus proche de 0.
Validité du cache
De même, il est nécessaire de vérifier si la pièce solution est présente de le set actuel des pièces disponibles. Il est probable qu'une optimisation soit possible si le cache est mise à jour quand un certains nombre de pièces sont posées. (Ce qui réduit les vérifications, est augment potentiellement la vitesse de calcul.)

Conseil :
Si vous réalisez une optimisation d'un logiciel ou d'un algorithme quelconque. Ne réalisez pas d'optimisation technique en premier ! Il est souvent plus efficace de ce concentré sur l'algorithme et la logique en premier. Car l'optimisation technique n'est peut-être valable que pour la version actuelle de l'algorithme. Si vous modifiez celui-ci après coup, vous constaterez peut-être que l'algorithme A optimisé est plus rapide que B sans optimisation. Il vous sera dur à ce moment là de détruire votre optimisation pour comparer sur un socle égale ou d'ajouter les optimisations sur B pour comparer.

Quel est votre optimisation qui vous a le plus marqué ?
Quel est votre avis sur cette optimisation ?

Cordialement,
Patrick Kolodziejczyk.

Source :
http://www.developpez.net/forums/d14...laire-unicite/
http://jmdoudoux.developpez.com/cour...p#outils-jdk-9
http://arodrigues.developpez.com/tut...ation-java-ee/

Ps : Je ne publie pas le code correspondant. Car celui-ci n'est absolument pas propre et en modification intensive en ce moment.