algorithm - 根据属性权重查找对象

Question

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

例如

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

权重 => {attribute1 => 0.5，attribute2 => 1.2，attribute3 => 1，attribute4 => -1，attribute5 => 10}

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

所以对象 B 将是顶部对象。

score 2 · Accepted Answer

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

score 0 · Accepted Answer

如果我正确理解了这个问题，最好的方法是使用标准的平衡搜索树（如 AVL-trees、RB-trees、Cartesian trees.std::set in c++）。在这棵树上我会存储对

<AttributesWeightsSum, ObjectID>.

然后，插入和删除对象将花费 O(P + logN) 时间，其中 P 是计算属性权重总和的复杂度（即 O(max_attributes_in_objects_count)），N 是集合中的最大对象数。通过遍历这棵树，找到前 K 个对象的 ID-s 将只是 O(K)。

如果您不必枚举前 K 个对象，而只找到一个顶部对象，则可以使用包含与上述相同对的二叉堆来代替平衡搜索树。

2 回答 2