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

Question

[vad4]

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

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

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

и тд.

Как максимально быстро реализовать возможность поиска по атрибутам в таком массиве? Причем можно задавать диапазоны поиска, то есть: покажи мне все объекты у которых атрибут 1: false, атрибут 2: от 1 до 90 и тд.
Задача похожа на запросы к БД. Интересно каким образом там это реализовано.
В голову пришло пока что ток одно: сделать для каждого атрибута бинарные деревья поиска.

Comments

[xappymah]

Универсальный алгоритм для такой постановки задачи вряд ли найти можно. Нужно уточнить определенные детали, чтобы на их основе создавать базу для оптимизации поиска.
Во-первых, как часто объекты вообще вставляются в этот массив и удаляются? А то какая-нибудь сверх-хитрая и быстрая структура данных может оказаться деоптимизацией из-за того, что очень дорогие вставки происходят чаще, чем происходит поиск.
Во-вторых, насколько атрибуты равноправны между собой? Если поиск по одному атрибуту происходит гораздо чаще, чем по другому, то на этой почве можно что-нибудь выиграть, иначе же нужен универсальный, а не спекулятивный алгоритм.

[ivsedm]

А засунуть все это в БД и переложить часть работы по оптимизации запросов на нее нельзя?

[alesto]

А можете подробнее описать где у Вас такой массив?

[vad4]

Скорость вставака и удаление не имеет значения. Есть массив с ним надо что то сделать что бы потом быстро по нему осуществлять поиск. Атрибуты полностью равноправны. В БД засунуть нельзя. Задание из разряда искуствено выдуманных

[Kindman]

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

Answer 1

[SabMakc]

Бинарные деревья по каждому элементу — сложность получается все равно как O(N), т.к. результаты все равно надо объединять. Даже если их представить как множества, то все равно для объединения надо проходить по всему массиву.

Answer 2

[ivsedm]

С предложенным вариантом, все равно остается сложность со слиянием результатов поиска по каждому из атрибутов. В этом случае большое значение будет иметь еще и порядок сравнения атрибутов. К примеру, если отобрать все записи по атрибуту 1, получим гигантскую кучу из половины всех записей (если равномерное распределение), потом их нужно пересечь с результатами по атрибуту 2 и т.д.
Плюс еще возникает задача как быстро сделать пересечение результатов.
Я в таком случае сделал бинарный поиск по самому частому и самому разнообразному атрибуту, занеся результаты в список. А дальше уже отбирал по этому списку элементы, которые подходят под другие условия, а неподходящие удаляя из списка. В результате остается только результат запроса.

Answer 3

[xappymah]

Как один из вариантов оптимизации поиска: факторизация всех объектов по булевским аттрибутам. То есть объекты делятся на непересекающиеся группы с различными комбинациями булевских параметров.
Имеется массив с количеством элементов, равным количеству групп.
Каждая группа объединяется в список и за голову цепляется за соответствующий элемент массива.

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

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

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

(кстати, а чем линейная сложность автора не устраивает?)

Comments

[vad4]

Проблема в том что булевых значений очень мало один, два атрибута. Линейный не устраивает потому что данных много 100М. Хотелось бы каким то образом подготовить массив один раз а дальше производить быстро поиск. Так же не важно сколько времени занимает вставка, удаление объекта.

[ivsedm]

Ну фактически получается, что нужно заранее составить все возможные комбинации элементов (до определенной степени), правильно?

[xappymah]

@ivsedm, можно сказать и так. В случае с булевскими параметрами это получается естественным образом — множество комбинаций бинарных значений легко отображается в целые числа.

Answer 4

[Анатолий]

В каждом языке есть функция сортировки которая принимает одним параметром массив, а вторым функцию обработчик, которая должна вернуть -1/0/1 и в зависимости от этого результата сортировка происходит как хочет разработчик. Почему бы Вам не воспользоваться этим?

Comments

[xappymah]

Сортировка так или иначе происходит по одному определенному параметру, относительно которого обработчик выдает результат при сравнении. В данном же случае имеется набор аттрибутов, по которым невозможно создать один единственный универсальный параметр для сравнения.

[Анатолий]

>.< Поиск, да, туплю =) Я прочитал как сортировка. В любом случае для поиска есть аналогичные функции. для пхп например, можно задавать условия вида:

$condition = array(
    'field' => 'field1',
    'type' => 'interval(9-20)'
)
$condition = array(
    'field' => 'field1',
    'type' => 'gt(9)'// все что больше 9
)
$condition = array(
    'field' => 'field1',
    'type' => 'eq(9)' // все что меньше 9
)

Filter::filter( $arrayObj, $condition );

Такие условия зарбирать просто, тип поля определить тоже просто.

Answer 5

[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 и так далее, пока не получим некоторое подмножество объектов, из которых линейным образом отбираются нужные, после этого возвращаемся на шаг назад и идем дальше.

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

Answer 6

[dbmaster]

Очень интересная и актуальная задача! Спасибо!

Про ограничения по памяти и серверов ничего не сказано, поэтому моё решение след:

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

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

дальше можно сделать выборку по одному атрибуту и проверять все остальные условия
или
мержить списки номеров объектов

Comments

[vad4]

А можно поподробней как построить индекс по атрибуту так что бы потом можно было искать его значения по диапазонам?

[dbmaster]

Тут можно обойтись тем же B-tree. В запросе x-y нам нужно найти значение x
а потом идти по списку.
Из того же списка en.wikipedia.org/wiki/B%2B_tree
Performing a range query with k elements occurring within the range requires O(log bn + k) operations

чтобы посчитать количество нужно будет хранить пару чисел в узлах
stackoverflow.com/questions/2329171/find-kth-smallest-element-in-a-binary-search-tree-in-optimum-way/2329236#2329236

Это конечно всё теория оторванная от реальности.

Answer 7

[MikhailEdoshin]

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

Comments

[vad4]

Да. Это наверно то что нужно. Я так понимаю именно так и сделано в БД. Спасибо!