Алгоритм сравнения матриц

← →
JetuS (2008-02-12 15:07) [0]

Есть большой массив двухмерных битовых матриц 64х64:
A: array of array[1..64, 1..64]: Boolean;
И есть одна контрольная матрица 64х64.

Как быстро сравнить масив А с контрольной матрицей и определить, какая матрица из масива А имеет наибольше "совпадений" с контрольной?

Совпадение - это когда A[x][i, j]=Contr[i, j]
Простым перебором for работает очень долго, а хотелось бы побыстрее.

← →
ketmar © (2008-02-12 15:11) [1]

для начала — выкидываем boolean"ы и берём longword"ы.

---
Understanding is not required. Only obedience.

← →
MBo © (2008-02-12 15:20) [2]

Можно попробовать задавать матрицу как array[0..63] of Int64
тогда сравнение строки с контрольной - один xor, затем подсчет количества единичных битов

← →
ketmar © (2008-02-12 15:24) [3]

>[2] MBo © (2008-02-12 15:20:00)
он умный, он поймёт и так.

---
Understanding is not required. Only obedience.

← →
JetuS (2008-02-12 15:25) [4]

> для начала — выкидываем boolean"ы и берём longword"ы.

И что дальше?

> Можно попробовать задавать матрицу как array[0..63] of Int64

Не совсем я понял как из 64х64 сделать одномерную матрицу 0..63

← →
ketmar © (2008-02-12 15:32) [5]

>[4] JetuS (2008-02-12 15:25:00)
Джетус, а с чего она одномерной стала? байты — они состоят из битов. в каждом байте — 8 битов. в int64 4 байта. бит принимает значения 0 и 1. Boolean принимает значения true и false. нсходство не улавливаешь?

правда, с битами придётся работать руками. зато сравнение — один xor и одна асм-команда подсчёта единичных битов (вроде была такая, искать лень %-).

преобразуется примерно так:
установить значение в [ i, j ]: arr[ i ] := arr[ i ] or (1 shl j);
дальше по аналогии.

---
Understanding is not required. Only obedience.

> в int64 4 байта

8 там байт... восемь...

>[6] Palladin © (2008-02-12 15:34:00)
тьфу. и в [1] ту же ошибку сделал. точно, пора спать. вот пиво допью, пожру — и…

---
Understanding is not required. Only obedience.

>вроде была такая, искать лень
увы, команды такой нет, но способов посчитать биты - море.

Алгоритм сравнения матриц Найти похожие ветки