Эффективный метод индексации для матрицы 2 на 2

Question

Если я заполню числа от 1 до 4 в матрице 2 на 2, есть 16 возможных комбинаций. Я хочу сохранить значения в массиве размером 24, соответствующем каждой матрице. Так дано Матрица 2 на 2, я хочу, чтобы эффективный метод индексации индексировал в массив напрямую (я не хочу сравнивать все 4 элемента для каждой из 16 позиций). Что-то похожее на битовый вектор? но не в состоянии разобраться как? Я хочу это для матрицы 4 на 4, также заполняя от 1 до 9

Answer 1

, чтобы уточнить: вы ищете эффективную хэш-функцию для матриц 2x2. Вы хотите использовать результаты хеш-функции для сравнения матриц, чтобы увидеть, совпадают ли они.

во-первых, давайте предположим, что вы на самом деле хотите цифры от 0 до 3 вместо от 1 до 4 - это упрощает работу и делает компьютер более точным Далее 16 не правильно. Есть 24 возможных перестановок чисел 0-3. Есть 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);
}