根据属性权重查找对象

假设我有一堆有很多属性的对象。在我的系统中，我知道属性的总集合，并且在任何给定时间，我都可以为这些属性生成一组权重。存储对象的最佳方法是什么，以便我能够根据这些属性权重找到最前面的n个对象。根据属性权重查找对象

例如

对象A => [ATTRIBUTE1，attribute2，attribute4] 对象B => [attribute2，attribute5]

重量=> {ATTRIBUTE1 => 0.5，attribute2 => 1.2，attribute3 = > 1，属性4 => -1，属性5 => 10}

使用这些权重：对象A的得分为0.5 + 1.2 +（-1）= .7 对象B的得分为1.2 + 10 = 11.2

所以对象B将成为顶级对象。

2013-02-10 dpick

我会维护数组中的对象。当要找到最重要的加权对象时，我会通过qsort来放置数组。 qsort的比较例程将通过添加对象属性的权重来比较给定对象的权重。排序后，数组中的对象按加权顺序排列，取第一个n。

2013-02-10 07:13:31 PQuinn

您可以通过不继续对已知不能包含前n项的部分进行排序来加快此目的的标准快速排序。 http://en.wikipedia.org/wiki/Selection_algorithm上有关于此方法和其他方法的非常好的维基百科文章 – mcdowella 2013-02-10 08:04:35

如果我正确地理解了这个问题，最好的方法就是使用标准的平衡搜索树（如AVL树，RB树，笛卡尔树，C++中的std :: set）。在此树我存储对

<AttributesWeightsSum, ObjectID>.

然后，插入和移除所述对象将采取O（P + logN）的时候，有P为计算属性的权重之和的复杂性（即O（max_attributes_in_objects_count）），N是集合中的最大对象数量。通过遍历这棵树，找到顶层K对象的ID-s就是O（K）。

如果您不必枚举顶层K对象，但只能找到一个顶层对象，而不是平衡搜索树，则可以使用包含与上述相同对的二进制堆。

2013-02-10 10:57:51

回答