Поиск объектов на основе весов атрибутов

Question

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

Например

объекта А => [attribute1, attribute2, attribute4] Объект В => [attribute2, attribute5]

Массы => {attribute1 => 0,5, attribute2 => 1,2, attribute3 = > 1, attribute4 => -1, attribute5 => 10}

с помощью этих весов: Объект а имеет оценку 0,5 + 1,2 + (-1) = 0,7 Объект в имеет балл 1,2 + 10 = 11,2

Таким образом, объект B будет верхним объектом.

Answer 1

Я бы сохранил объекты в массиве. Когда придет время найти верхний взвешенный объект, я бы поставил массив через qsort. Процедура сравнения для qsort сравнивала бы веса данных объектов путем добавления весов атрибутов объектов. После сортировки объекты в массиве находятся в взвешенном порядке, возьмите первое n.

Answer 2

Если я правильно понял проблему, лучший способ сделать это - использовать стандартное сбалансированное дерево поиска (например, AVL-деревья, RB-деревья, декартовы деревья. Std :: set in C++). В этом дереве я бы хранить пары

<AttributesWeightsSum, ObjectID>. 

Затем, вставка и удаление объекта будет принимать O (P + LogN) время, то P является сложность вычисления атрибутов весов суммы (то есть O (max_attributes_in_objects_count)) , а N - максимальное количество объектов в наборе. Поиск идентификаторов верхних объектов K будет только O (K), пройдя это дерево.

Если вам не нужно перечислить верхние объекты K, но только найдите один верхний объект, вместо сбалансированных деревьев поиска вы можете использовать двоичные кучи, содержащие те же пары, что описаны выше.