2 x 2 矩阵的高效索引方法

Question

如果我在 2 x 2 矩阵中填充 1 到 4 的数字，则有 16 种可能的组合。我想要做的是将值存储在与每个矩阵对应的大小为 24 的数组中。所以给定一个 2 x 2 矩阵，我想要一个有效的索引方法来直接索引到数组中。（我不想比较 16 个位置中每个位置的所有 4 个元素）。类似于位向量的东西？但无法弄清楚如何？ 我想要一个 4 x 4 矩阵，也填充 1 到 9

Answer 1

澄清一下：您正在寻找 2x2 矩阵的有效哈希函数。您想使用哈希函数的结果来比较矩阵以查看它们是否相同。

首先，假设您实际上想要数字 0 到 3，而不是 1 到 4 - 这使得它更容易，并且更计算机科学。接下来，16 不对。数字 0-3 有 24 种可能的排列。使用四个字母的字母表有 4^4 = 256 个可能的长度为 4 的字符串（您可以重复已使用的数字）。

任何一个都可以轻松编码为单个字节。让前 2 位代表 (0,0) 位置，接下来的 2 位代表 (0,1)，依此类推。然后，要散列 2x2 矩阵，只需执行以下操作：

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

随机示例：二进制中的数字 54 是 00110110，它表示一个矩阵，如下所示：

2 1
3 0

Answer 2

当您需要效率时，有时代码清晰度就被抛之脑后了:)

首先您需要确定您想要效率 - 您有分析信息以确保简单的比较代码对您来说效率太低？

---

您可以简单地将其视为相同大小的字节数组。 memcmp 进行任意内存的比较：

诸如以下的数据结构：

int matrix[2][2];

存储方式相同：

int matrix[2*2];

可以动态分配为：

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

我不是建议您动态分配它们，我正在说明字节是如何分配的在你的原始类型中实际上是在内存中布局的。

因此，以下内容是有效的：

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);
}