Поиск ближайшего используемого индекса перед указанным индексом в массиве (быстро)

Question

Этот вопрос относится к Массиву пар 3-битных элементов
Этот массив имеет 52 пары (около 40 байтов), и я хочу найти первую пару перед указанной, у которой ее значения отличаются от 0 (используемая пара). Очевидным решением было бы проверить каждую пару <этой (сканирование справа налево), но это кажется очень неэффективным, если есть много неиспользованных пар (установлено в 0). </p>

Это изображение может лучше объяснить ситуацию:

Используются пары 0, 1 и 51.
Я хочу найти первую использованную пару до 51 (здесь 1).

Я пробовал такие трюки, как

if(*((int *)&array[arrayPos]) == 0) {
    arrayPos -= sizeof(int);
    pairPos -= ???
}  

Проблема здесь в том, что вычитать из pairPos не так просто, из-за 6 бит / пара, поэтому я закончил с таблицей поиска, основанной на некоторых отношениях между pairPos и arrayPos , и все это заставило решение работать как тривиальное.

Есть ли способ сделать этот поиск быстрее? Другая проблема заключается в том, что существует только 1 неиспользуемый байт ... возможно, я смогу освободить место для другого 4. Если бы было хотя бы 7, я мог бы использовать растровое изображение массива, и было бы намного быстрее пропускать неиспользуемые пары.

Answer 1

Можете ли вы сказать что-нибудь о смежных байтовых значениях, которые представляют пустую пару?

Я хочу предложить смотреть на байты, а не на биты.

Любой данный байт, если он является левым вкладчиком пары пустых 6-битовых символов, должен соответствовать конкретной битовой маске, значение которой зависит от его положения. ?? ?? 00 00 или ?? 00 00 00 или что-то еще. Вы можете рассматривать каждый байт по очереди для их кандидатуры как самый левый байт. Возможна простая таблица поиска, какую маску использовать.

Следовательно, нам на самом деле не нужно извлекать 6-битные символы перед их рассмотрением.

Можем ли мы добиться большего успеха, отбросив байт в качестве кандидата, можем ли мы теперь пропустить один слева?

В случае, если наша маска была 00 00 00 00, если это не удалось, тогда наш сосед слева, да, если установлен первый бит.

Это на самом деле делает вещи быстрее?

Answer 2

Обработка 6-битных значений в группах.

Вы можете использовать группы из 5 значений в 32-битном слове, которое тратит 2 бита или около 7% пространства. Если все значения в слове равны 0, тогда слово равно нулю, поэтому можно быстро найти непустое слово, а затем проверить 5 значений в слове.

Если вы не можете жить с небольшим потерянным пространством, используйте группы по 96 бит, где 96 - это наименьшее общее число, кратное 6 и 32. Т.е. упаковать 16 значений по 6 битов в три 32-битных слова.

Answer 3

Лучшее решение, которое я нашел, было:
1. сделать элементы 1 байт (не 6 бит, чем раньше) - спасибо Skizz
2. используйте растровое изображение, чтобы увидеть, какой элемент является ближайшим слева. Это было намного быстрее, чем возвращаться к технике, описанной djna.

Улучшения скорости впечатляют:
в одном тестовом случае, с 13 с теперь 6,5 с
в другом - с 7,4 до 3,6 с
Спектакль удвоился: D

Еще раз спасибо за ваши ответы!

Answer 4

Существуют специальные инструкции процессора для поиска битовых массивов. Они могут быть предоставлены как встроенные функции компилятора. Многие файловые системы Linux широко их используют.

__buildin_ffs () - один в GCC.

ffsll () может быть POSIX, хотя я не слышал об этом до сих пор.