Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Алгоритм сравнения матриц [D7, WinXP]

JetuS © (2008-02-12 15:07:00)
Есть большой массив двухмерных битовых матриц 64х64:
A: array of array[1..64, 1..64]: Boolean;
И есть одна контрольная матрица 64х64.

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

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

MBo (2008-02-12 15:37:00) [1]
>вроде была такая, искать лень
увы, команды такой нет, но способов посчитать биты - море.

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

---
Understanding is not required. Only obedience.

Palladin (2008-02-12 15:34:00) [3]

> в int64 4 байта

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

ketmar (2008-02-12 15:32:00) [4]
>[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.

JetuS (2008-02-12 15:25:00) [5]

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

И что дальше?

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

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

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

---
Understanding is not required. Only obedience.

MBo (2008-02-12 15:20:00) [7]
Можно попробовать задавать матрицу как array[0..63] of Int64
тогда сравнение строки с контрольной - один xor, затем подсчет количества единичных битов

ketmar (2008-02-12 15:11:00) [8]
для начала — выкидываем boolean'ы и берём longword'ы.

---
Understanding is not required. Only obedience.

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »