Быстрый алгоритм поиска

Есть большой массив объектов. Объект имеет несколько атрибутов. Атрибут может принимать булевое значение или число (как целове так и вещественное).
Пример:

Объект 1:
атрибут 1: true
атрибут 2: 2
атрибут 3: 22.43

Объект 2:
атрибут 1: false
атрибут 2: 5
атрибут 3: 10.7

и тд.

Как максимально быстро реализовать возможность поиска по атрибутам в таком массиве? Причем можно задавать диапазоны поиска, то есть: покажи мне все объекты у которых атрибут 1: false, атрибут 2: от 1 до 90 и тд.
Задача похожа на запросы к БД. Интересно каким образом там это реализовано.
В голову пришло пока что ток одно: сделать для каждого атрибута бинарные деревья поиска.
  • Вопрос задан
  • 7936 просмотров
Пригласить эксперта
Ответы на вопрос 7
SabMakc
@SabMakc
Бинарные деревья по каждому элементу — сложность получается все равно как O(N), т.к. результаты все равно надо объединять. Даже если их представить как множества, то все равно для объединения надо проходить по всему массиву.
Ответ написан
@ivsedm
С предложенным вариантом, все равно остается сложность со слиянием результатов поиска по каждому из атрибутов. В этом случае большое значение будет иметь еще и порядок сравнения атрибутов. К примеру, если отобрать все записи по атрибуту 1, получим гигантскую кучу из половины всех записей (если равномерное распределение), потом их нужно пересечь с результатами по атрибуту 2 и т.д.
Плюс еще возникает задача как быстро сделать пересечение результатов.
Я в таком случае сделал бинарный поиск по самому частому и самому разнообразному атрибуту, занеся результаты в список. А дальше уже отбирал по этому списку элементы, которые подходят под другие условия, а неподходящие удаляя из списка. В результате остается только результат запроса.
Ответ написан
xappymah
@xappymah
Как один из вариантов оптимизации поиска: факторизация всех объектов по булевским аттрибутам. То есть объекты делятся на непересекающиеся группы с различными комбинациями булевских параметров.
Имеется массив с количеством элементов, равным количеству групп.
Каждая группа объединяется в список и за голову цепляется за соответствующий элемент массива.

Таким образом, имея запрос с булевскими параметрами можно за почти константное время (ограниченное сверху) можно найти все такие фактор-группы и линейно по ним пройтись, отбирая элементы по другим параметрам.

Сами списки можно также факторизовать по какому-нибудь часто-используемому атрибуту (потребуется набор индексов, для нахождения соответствующих фактор-групп) или просто отсортировать.

Но все приведенное выше является не более чем оптимизацией поиска. В худшем случае все равно будет линейное время.

(кстати, а чем линейная сложность автора не устраивает?)
Ответ написан
taliban
@taliban
php программист
В каждом языке есть функция сортировки которая принимает одним параметром массив, а вторым функцию обработчик, которая должна вернуть -1/0/1 и в зависимости от этого результата сортировка происходит как хочет разработчик. Почему бы Вам не воспользоваться этим?
Ответ написан
xappymah
@xappymah
В качестве расширения своего предыдущего предложения — оптимизация для сужения множества поиска.

Откинем булевские атрибуты, считая их целочисленными для универсальности.
Имеем атрибуты A1, A2… An. Каждый из этих атрибутов имеет некоторый диапазон значений.
Для каждого атрибута разбиваем соответствующий диапазон на k_i кусков, каждый из которых обозначим через Ai_1, Ai_2...Ai_k_i.

Далее, имеем множество всех объектов ALL с упомянутыми атрибутами.
Возьмем атрибут A1 и разобьем множество ALL на непересекающиеся подмножества ALL_A1_j, где 1 <= j <= k_1, такие, что ALL_A1_j содержит объекты, у которых значение атрибута A1 находится в диапазоне A1_j.

Далее, с каждым этим подмножеством производится аналогичное разбиение по атрибуту A2. Потом каждое подмножество разбивается по значениям атрибута A3 и так далее до An.

Таким образом имеется дерево разбиения множества ALL по диапазонам значений всех атрибутов.

Теперь, можно считать, что при поиске заданы желаемые диапазоны для всех атрибутов: если какой-то атрибут при поиске не указан, значит желаемым диапазон — множество всех значений атрибута.
Для каждого атрибута Ai в начале отбираются такие диапазоны Ai_k, которые пересекаются с желаемым.

После этого делается обход по дереву разбиений в глубину: то есть, начиная от корня ALL идем в ALL_A1_k1, из которого в ALL_A1_k1_A2_k1 и так далее, пока не получим некоторое подмножество объектов, из которых линейным образом отбираются нужные, после этого возвращаемся на шаг назад и идем дальше.

В худшем случае, обход по дереву разбиений может иметь линейную сложность, а по факту, чуть хуже, чем простой линейный перебор.
Но при удачном выборе порядка атрибутов и диапазонов разбиений круг поиска может уменьшиться во много раз (вплоть до вырожденного случая, когда параметрам поиска будет соответствовать строго одно подмножество, которое находится за константное время).
Ответ написан
dbmaster
@dbmaster
Очень интересная и актуальная задача! Спасибо!

Про ограничения по памяти и серверов ничего не сказано, поэтому моё решение след:
  • присвоить каждому объекту номер 1,2,3,4,5
  • строим независимый индекс по каждому атрибуту (если значения атрибута совпадают, сортируем по номеру объекта)

запрос разбиваем на части и по каждому индексу можем за o(log(n)) = o(log(100M))=19 операций узнать сколько объектов будет в результате если будем фильтровать только по этому одному атрибуту.

дальше можно сделать выборку по одному атрибуту и проверять все остальные условия
или
мержить списки номеров объектов
Ответ написан
@MikhailEdoshin
О, моя любимая задача. Есть такое UB-Tree (плюс в Википедии ссылки полезные) из того же материала от того же Рудольфа Бауэра, что изобрел и B-Tree. На мой взгляд, правда, слишком оно головоломное, и сам я его не испытывал.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
iChar Санкт-Петербург
от 120 000 до 180 000 ₽
Яндекс Москва
от 100 000 до 300 000 ₽
26 янв. 2021, в 18:54
2000 руб./за проект
26 янв. 2021, в 18:45
2000 руб./за проект