根據屬性權重查找對象

假設我有一堆有很多屬性的對象。在我的系統中，我知道屬性的總集合，並且在任何給定時間，我都可以爲這些屬性生成一組權重。存儲對象的最佳方法是什麼，以便我能夠根據這些屬性權重找到最前面的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

回答