CODEWITHSUNDEEP
algorithmsearchdata-structuresstorage
dpick
dpick

Reputation: 153

Finding objects based on attribute weights

Say I have a bunch of objects with a lot of attributes. In my system I know the total set of attributes and at any given time I can generate a set of weights for those attributes. What would be the best way to store the objects so that I would be able to find the top n objects based on those attribute weights.

E.g

Object A => [attribute1, attribute2, attribute4] Object B => [attribute2, attribute5]

Weights => {attribute1 => 0.5, attribute2 => 1.2, attribute3 => 1, attribute4 => -1, attribute5 => 10}

Using these weights: Object A has a score of 0.5 + 1.2 + (-1) = .7 Object B has a score of 1.2 + 10 = 11.2

So Object B would be the top object.

Upvotes: 1

Views: 152

Answers (2)

K. Bulatov
K. Bulatov

Reputation: 154

If I understood the problem correctly, the best way to do it is using standard balanced search tree (like AVL-trees, RB-trees, Cartesian trees. std::set in c++). In this tree I'd store pairs 

<AttributesWeightsSum, ObjectID>.

Then, insertion and removing the object will take O(P + logN) time, there P is the complexity of calculating attributes weights sum (that is O(max_attributes_in_objects_count)), and N is the maximum number of objects in set. Finding ID-s of top K objects will be just O(K) by traversing this tree.

If you don't have to enumerate top K objects, but only find one top object, instead of balanced search trees you can use binary heaps containing the same pairs as described above.

Upvotes: 0

PQuinn
PQuinn

Reputation: 1022

I would maintain the objects in an array. When it comes time to find the top weighted object I would put the array through qsort. The compare routine for qsort would compare the weights of the given objects by adding the weights of the objects' attributes. After sorting the objects in the array are in weighted order, take the first n.

Upvotes: 2

Related Questions