Мыслим перпендикулярно
Продолжаем тему Битовых головоломок. Anight предложил интересную идею как можно реализовать поиск данных по битовым маскам. Сначала я не понял о чём мне говорят, но когда до меня дошло, я в очередной раз порадовался простоте и элегантности решения от anight-а.
Теперь о самом решении. Задача стоит в том, чтобы максимально быстро выбрать набор данных, удовлетворяющих некоторому набору признаков, представленных в виде битовой маски. Далее предполагается, что мы работаем со 128-битным регистрами sse.
Мои идеи крутились вокруг деления битовой маски на куски по 128 бит и последовательной проверки каждого слова на соответствие поисковой маске. В результате получается матрица размерностью ceil(размер битовой маски / 128) по ширине и длинной в количество записей.
Новая идея в том, что мы строим матрицу, где строке соответствует один бит из битовой маски, а в столбцах у нас записи. Таким образом, у нас одно слово описывает один бит у 128 записей. Получается, что за одну операцию мы проверяем один бит у 128 записей. Если у нас n бит в маске, то мы проверим 128 записей за n операций. По-моему красиво 
Из плюсов вижу более компактное хранение (у нас не будет неиспользуемых бит в слове, если размер битовой маски не кратен 128) и большую скорость работы (мы проверяем только значимые биты, например, если у нас битовая маска 150 бит, то в первом варианте нам нужно 2 проверки на каждую запись, т.е. 256 операций на 128 записей, а во втором нам нужно 150 операций для проверки 128 записей). Из минусов вижу только более сложное формирование данных и поиска.
ИМХО красивая реализация
Tags: битовые операции, программирование
что мешает начинать поиск со старших разрядов? каждый разряд сокращает пространство поиска вдвое. один байт позволяет сократить число проверяемых записей в 256 раз. Т.е. идея в поразрядной индексации
Не понял идею сокращения пространства поиска вдвое
Так. Возможно я не понял задачу.
Моё видение.
Имеется A-входной битовый поток (ключ какой-нибудь). В некотором массиве хранятся соответствия битовых потоков какой-либо сущности.
Нужно найти в таком массиве из стомильёновмильярдов эту сущность, соответствующую A-входному битовому потоку.
Если я не вкурил, то поправь меня, пожалуйста!
–
Моя идея в том, чтобы вести поиск со старшего разряда (да в принципе-то с любого, который приведет к “эффективному” поиску).
Пусть массив содержит всего Ni записей. В первом шаге алгоритма мы выбираем все записи, в которых старший i-разряд ключа = старшему i-разряду маски. Далее ведём поиск в сформированном множестве по N(i-1) записей таких, что каждый i-разряд в них равен i-разряду маски. Процесс повторяется до нахождения нужной записи или до нахождения массива записей требуемого объёма, в котором находится искомая запись. Алгоритм “нечёток”, мы можем остановить его в любой момент и получить “суженное” пространство для поиска. Мы можем его распараллелить на C вычислительных машин, разделив исходный массив на C массивов, что сократит время поиска в C раз.
Фактически мы ведём поиск по бинарному (ну потому что разряды у нас принимают значение 0 или 1) дереву, в котором на каждом шаге пространство поиска сокращается вдвое при равномерном распределении битов по разрядам.
Вцелом, алгоритм отвратителен - он расходует много памяти
Но мы имеем стомильёновмильярдов записей, а также необходимость оптимального поиска по ним.
Построим теперь список частостей разрядов в массиве (”индекс”). Т.е. подсчитаем число, скажем битов, равных 1 в каждом разряде по всему огромному массиву. Разряд, в котором частость единиц минимальна это разряд, с которого следует начать поиск, т.к. в первой же итерации мы получаем минимальный объём записей, удовлетворяющих исходному A-битовому потоку.
Где-то я, возможно, налажал. Просто я занимаюсь сейчас линейным криптоанализом [википедия!] (да и ещё много чем), в нём подобный алгоритм используется для отыскания ключа блочного шифра. Если у тебя есть какая-нибудь выборка для опытов, то прошу в студию. Алгоритм поиска, описанный мною, эффективен при неравномерном распределении частостей битов. Как оптимизировать память, я пока не знаю, но можем поковыряться. С радостью помогу, чем могу. Блог достаточно интересный. У меня есть реализация алгоритма линейного криптоанализа на c++, но я её пока не тестил.
Если интересно, пиши на мыло erss_vlad@mail.ru, у меня есть трудовые резервы
У нас просто расходятся задачи, а, соответсвенно и решения задач. Моя задача состояла в ускорении поиска данных методом перебора. Для примера возьмём поиск человека с такими параметрами как пол, страна, наличие фотографии, и т.п. Если таких параметров будет много, индексы построить не получится, максимум можно сократить перебор по ряду параметров, но не по всем.
Решение в лоб: if (user.gender==1 && user.country==1 && user.photo==1). Т.е. на проверку одного пользователя надо столько операций условного перехода, сколько у нас параметров. Можно построить битовую маску где 0 бит — пол (1 или 0), 1-8 биты — страна (256 стран), 9 бит — наличие фотографии (1 или 0). Получаем одну проверку if (user.mask & mask). Но у такого подхода тоже есть минусы: битовая маска кратна 8 битам (байт), т.е. у нас будет неэффективное использование бит, не все параметры можно переложить в операцию И, иногда нужна операция ИЛИ, иногда НЕ И и так далее. Так вот “перпендикулярный” поиск решает эту задачу эффективно
Понятно.
Я не считаю, что алгоритм оптимален, т.к. ты не оптимизируешь сам перебор. Ну и что, что вычисляется одна N-битная операция И вместо 3*N побитных?
Давай разделим записи мужчин и женщин в разные массивы данных (в разные таблицы БД). Тогда время перебора автоматически сокращается вдвое, т.к. тебе один раз необходимо определить в каком наборе выполнять перебор, а наборы для перебора имеют вдвое (всреднем) меньший объём.
Только вот с практической стороной реализации жопа
Не проблема разделить на М/Ж данные и построить индексы. А если у тебя таких параметров больше 10? А если у тебя в поиске используются разные параметры? Я не рассматриваю тут задачи, которые рашаеются парой-тройкой индексов. Задача изначально ставится так, что индексы либо построить не реально, либо они не помогут, в приниципе. Едиственно возможный вариант решения задачи — перебор. Вот и встаёт вопрос, как перебирать максимально быстро, потому как if (user.gender==1 && user.country==1 && user.photo==1 …) — это явно медленно.