méthode d'indexation efficace pour une 2 par 2

Question

matrice

Si je remplis des nombres de 1 à 4 dans une matrice deux par deux, il y a 16 combinaisons possibles. Ce que je veux faire est de stocker des valeurs dans un tableau de taille 24 correspondant à chaque matrice. Donc, étant donné un deux par deux matrice, je veux une méthode efficace d'indexation pour indexer dans la matrice directement. (Je ne veux on compare les 4 éléments pour chacune des 16 positions). Quelque chose de similaire au vecteur de bits? mais pas capable de comprendre comment? Je le veux pour une matrice 4 par 4 remplissant également de 1 à 9

Answer 1

pour clarifier: vous cherchez une fonction de hachage efficace pour les matrices 2x2. vous voulez utiliser les résultats de la fonction de hachage pour comparer les matrices pour voir si elles sont les mêmes. Tout d'abord, supposons que vous voulez vraiment les chiffres de 0 à 3 au lieu de 1 à 4 - ce qui le rend plus facile, et est plus informaticien. Ensuite, 16 n'est pas correct. il y a 24 permutations possibles des nombres 0-3. Il y a 4^4 = 256 chaînes possibles de longueur 4 qui utilisent un alphabet de quatre lettres (vous pouvez répéter les numéros déjà utilisés).

ou l'autre est trivial pour coder en un seul octet. Laissez les 2 premiers bits représentent la (0,0) position, les 2 bits suivants représentent (0,1), et ainsi de suite. Que, de hachage votre matrice 2x2, il suffit de faire:

hash = m[0][0] | (m[0][1] << 2) | (m[1][0] << 4) | (m[1][1] << 6 

exemple au hasard: le nombre 54 en binaire est 00110110 qui représente une matrice comme:

2 1 
3 0 

Answer 2

Lorsque vous avez besoin d'efficacité, parfois la clarté du code va par la fenêtre :)

Vous devez d'abord être sûr que vous voulez l'efficacité - vous avez des informations de profilage pour être sûr que le code de comparaison simple est trop inefficace pour vous?

---

Vous pouvez simplement le traiter comme un tableau d'octets de la même taille. memcmp ne fait des comparaisons de mémoire arbitraire:

Une structure de données telle que:

int matrix[2][2]; 

est stocké le même que:

int matrix[2*2]; 

qui pourrait être attribué de façon dynamique en tant que:

typedef int matrix[2*2]; 
matrix* m = (matrix*)malloc(sizeof(matrix)); 

Je ne suggère pas que vous les allouer dynamiquement, j'illustre comment les octets dans votre type d'origine est effectivement mis en mémoire.

Par conséquent, ce qui suit est valable:

matrix lookup[16]; 

int matrix_cmp(const void* a,const void* b) { 
    return memcmp(a,b,sizeof(matrix)); 
} 

void init_matrix_lookup() { 
    int i; 
    for(i=0; i<16; i++) { 
     ... 
    } 
    qsort(lookup,16,sizeof(matrix),matrix_cmp)); 
} 

int matrix_to_lookup(matrix* m) { 
    // in this example I'm sorting them so we can bsearch; 
    // but with only 16 elements, its probably not worth the effort, 
    // and you could safely just loop over them... 
    return bsearch(m,lookup,16,sizeof(matrix),matrix_cmp); 
}