|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Mike Murov 2:5030/976.55 29 Mar 2002 01:18:10
To : Alexander Shmidt
Subject : Сравнить матрицы
--------------------------------------------------------------------------------
Сpд Маp 27 2002 15:33, я пишу:
>> < Е >< Е >< Хау, бледнолицый All! >< Е >< Е ><
AS> (будешь долго за компом сидеть, не то что бледным - зеленым
AS> станешь!)
AS> Задача есть 25*80 булевых матриц размера 14х8. Каждую из них надо
AS> сравнить на совпадение с одной из 200 эталонных матриц (такого же
AS> размера) _как_можно_быстрее_.
AS> Пока делаю так:
AS> При инициализации проги завожу 2х 14*8 масивов множеств. Таким
AS> образом, на каждый элемент матрицы - по два множества. В одном
AS> хранятся индексы эталонов, в которых элемент=true, в другом -
AS> наоборот. При проверке очередной матрицы проходимся по каждому ее
AS> элементу и ищем пересечение соответствующих множеств (эл. матрицы=true
AS> - берем множество индексов, где этот элемент=true, =false - берем
AS> множество индексов, где элемент=falsе). В конце прохода имеем в
AS> результирующем множетсве либо индекс эталона, которому соответствует
AS> проверяемая матрица, либо ничего (тоже результат).
AS> Как сделать еще быстрее? Каждая мелочь поможет, каждый такт - на вес
AS> золота.
AS> Может проверять множества не подряд, а в определенном порядке (чтоб
AS> быстрее закончить проверку: если на каком-то этапе уже есть множество,
AS> содержащее <=1 элемент, вываливаемся из процедуры)? Сначала проверять
AS> какие-то определенные "контрольные" множества, потом - менее
AS> определяющие?
Булево это 0/1?
Тогда предлагаю матрицы по 14*8 бит ~128 = 16 байт
Проверка - memcmp(x, y, 16) - в x86 оптимизировано, прерывается по первому
несовпадению в байте (или двойном слове, зависит от выравнивания).
При выравнивании на двойное слово самое худшее (без учета кэша) 4
такта/сравнение матрицы.
А теперь самое интересное: при таком подходе сортируем исходный массив из 200
образцов как char[16], а дальше можно бинарным поиском т.к. memcmp() выдает 0,
1, -1...
Худшее кол-во просмотров log2 200 ~ 8, число тактов 4*8+ 8= 40 тактов для
проверки бинарного массива 14*8 по 200 образцам, кто меньше?
P.S. Hа C и asm все вот так прозрачно, но если ясна идея то с реализацией
проблем не будет.
P.P.S. Реально все будет еще быстрее, особенно когда все 200 образцов
разместятся в кэше (3 200 байт), а последовательные операции сравнения будут
распараллелены по конвейерам процессора. Причем выравнивание на 16 байт - то что
доктор прописал для архитектуры P6...
Еще увидимся, Alexander.
--- GoldED/W32 3.0.1
* Origin: Kill. Ем All. (2:5030/976.55)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
