Bonjour,
L'une de mes problématiques précédentes était de réaliser une cache/indexation matriciel pour des pièces de puzzle.
Il y a un billet ici : [Retour][Optimisation][Eternity II] Problème récurrent et optimisation par cache matriciel
Et une discutions sur la problématique précédente ici : Hash/clé : permutation circulaire et unicité [Résolu]
L'idée de base était d'avoir un index permettant de savoir quel pièces permet de résoudre quel problème sans faire de test sur la pièce.
La solution retenu était :
1 2
| // Contrainte Top / Contrainte Left / Contrainte Bottom / Contrainte Right / Id de la pièce de la solution X [0..n]
private static int[][][][][] cacheIdSolutions = new int[24][24][24][24][0]; |
Celui-ci est performant pour une indexation sur un pièce. Mais, j'aimerai étendre le principe sur l'indexation d'un groupe de pièce (2x2 ou plus). La problématique est qu'il m'est impossible d'instancier la matrice d'index, car il serai nécessaire d'avoir :
private static MetaHash[][][][][][][][][] cacheIdSolutions =new MetaHash[24][24][24][24][24][24][24][24][0];
ou
private static MetaHash[][][][][] cacheIdSolutions =new MetaHash[576][576][576][576][0]; // Regroupe les côtés en
Ce qui représente 1,1x1011 espace mémoire ce que je n'ai pas.
A savoir que le nombre de groupe de pièces à indexé est 4 357 212, ce qui représente une quantité non négligeable.
Ma première piste étant une demi indexation :
1 2
| // Contrainte TopRight // Contrainte TopLeft // Contrainte LeftTop // Contrainte LeftBot
public static MetaHash[][][][][] cacheTopLeft = new MetaHash[24][24][24][24][0]; |
Ce qui me permet d'avoir un index sur les match suivant :
_II_
IPP*
IPP*
_**_
I : match indexé
P : pièce
* : match non indexé
Sachant que les groupes de pièces peuvent être tournée. J'ai indirectement l'indexation pour le reste (le bas et la droite). Cependant, il m'est impossible de réaliser un index par rapport à 3 côtés ou plus avec un complexité O(1).
En effet, si je veux faire un match sur 3 côtés, il m'est nécessaire faire deux recherches dans mon index et de faire l'intersection des deux ensembles retournées.
Du coup, je me demande si il n'y aurai pas un moyen pour faire une indexation adaptable par rapport à cette problématique.
Si vous avez des avis ou idées sur la question, hésitez pas !
Cordialement,
Patrick Kolodziejczyk.
Partager