30 ЯнвМыслим перпендикулярно
Продолжаем тему Битовых головоломок. Anight предложил интересную идею как можно реализовать поиск данных по битовым маскам. Сначала я не понял о чём мне говорят, но когда до меня дошло, я в очередной раз порадовался простоте и элегантности решения от anight-а.
Теперь о самом решении. Задача стоит в том, чтобы максимально быстро выбрать набор данных, удовлетворяющих некоторому набору признаков, представленных в виде битовой маски. Далее предполагается, что мы работаем со 128-битным регистрами sse.
Мои идеи крутились вокруг деления битовой маски на куски по 128 бит и последовательной проверки каждого слова на соответствие поисковой маске. В результате получается матрица размерностью ceil(размер битовой маски / 128) по ширине и длинной в количество записей.
Новая идея в том, что мы строим матрицу, где строке соответствует один бит из битовой маски, а в столбцах у нас записи. Таким образом, у нас одно слово описывает один бит у 128 записей. Получается, что за одну операцию мы проверяем один бит у 128 записей. Если у нас n бит в маске, то мы проверим 128 записей за n операций. По-моему красиво 
Из плюсов вижу более компактное хранение (у нас не будет неиспользуемых бит в слове, если размер битовой маски не кратен 128) и большую скорость работы (мы проверяем только значимые биты, например, если у нас битовая маска 150 бит, то в первом варианте нам нужно 2 проверки на каждую запись, т.е. 256 операций на 128 записей, а во втором нам нужно 150 операций для проверки 128 записей). Из минусов вижу только более сложное формирование данных и поиска.
ИМХО красивая реализация
