Привет. Вот такая есть задачка, что дано: Есть массив битовых записей, объём большой (~10Mb). Размер одной записи 10бит для определённости, но лучше решать в общем виде (nbits). Записи идут подряд от старшего бита к младшему: aaaaaaaa aabbbbbb bbbbcccc ccccccdd dddddddd Известно что в этом массиве есть нулевые записи - т.е. записи, все биты в которых установлены в 0. Также известно что записей этих мало: < 1% от общего числа. Требуется скопировать исходный массив в другой, при этом найти все эти записи и определённым образом обработать. Задача в том как максимально оптимально их найти с учётом того что их мало. Производительность очень критична, памяти 10К - так что большие таблицы не предлагать. У меня пока идеи такие - выбрать размер блока таким образом, чтобы его размер в битах был кратен 8 и кратен nbits. Т.е. чтобы блок содержал целое число байт и целое число записей. После чего проверяем есть ли в нём нулевые записи. Если нету - просто копируем, если есть - ищем какая именно запись и обрабатываем. Вот вопрос в том как проверить наличие нулевых записей максимально быстро, не перебирая их все. Т.е. не получать положение записи, сколько их таких в блоке и т.д., а просто есть или нету. Вот на этом я застрял как-то. С выделением каждой записи и проверкой всё работает, но долго.
Примитивно, но возможно вполне годно: сделать побитовое and всем 5 двордам, если результат 0 -- то тестить есть ли нули, количество промахов возможно будет приемлимым..
cppasm Эту задачку для какого процессора решать требуется? Вариантов пока я вижу два: грузить в регистры и делать test/jz или сдвигать и делать OR чтобы получить в одном бите признак запись 0/не 0. Но последний вариант может быть хорош только для записей малого размера и для SSE.
Еще одна мысль: mov eax,[esi] mov ebx,[esi+4] mov ecx,[esi+8] mov edx,[esi+12] mov ebp,[esi+16] sub eax,40100401h sbb ebx,10040100h sbb ecx,04010040h sbb edx,01004010h sbb ebp,00401004h sbb eax,0 xor eax,[esi] xor ebx,[esi+4] xor ecx,[esi+8] xor edx,[esi+12] xor ebp,[esi+16] and eax,40100401h and ebx,10040100h and ecx,04010040h and edx,01004010h and ebp,00401004h or eax,ebx or eax,ecx or eax,edx or eax,ebp xor eax,555555555h jnz exist_zero_field
Если nbits>=15, можно сначала искать нулевой байт через repne scasb, а потом анализировать его окрестности.
Процессор ARM. nbits<16 всегда. Для 5 байт сложенных по И слишком часто будут промахи. Black_mirror последний вариант интересный, разбираюсь пока как работает. Но получается в итоге что оно того не стоит. Примерно таким же количеством команд можно по маске выделить записи и проверить.
