1

多くの属性を持つオブジェクトがたくさんあるとします。私のシステムでは、属性のセット全体を把握しており、いつでもそれらの属性の重みのセットを生成できます。これらの属性の重みに基づいて上位 n 個のオブジェクトを見つけることができるように、オブジェクトを格納する最良の方法は何でしょうか。

例えば

オブジェクト A => [属性 1、属性 2、属性 4] オブジェクト B => [属性 2、属性 5]

重み => {属性 1 => 0.5、属性 2 => 1.2、属性 3 => 1、属性 4 => -1、属性 5 => 10}

これらの重みの使用: オブジェクト A のスコアは 0.5 + 1.2 + (-1) = .7 オブジェクト B のスコアは 1.2 + 10 = 11.2

したがって、オブジェクト B が一番上のオブジェクトになります。

4

2 に答える 2

2

オブジェクトを配列に保持します。最上位の重み付けされたオブジェクトを見つけるときが来たら、qsort を介して配列を配置します。qsort の比較ルーチンは、オブジェクトの属性の重みを追加することによって、指定されたオブジェクトの重みを比較します。配列内のオブジェクトを重み付け順に並べ替えた後、最初の n を取得します。

于 2013-02-10T07:13:31.907 に答える
0

問題を正しく理解した場合、それを行う最良の方法は、標準のバランスの取れた検索ツリー（AVLツリー、RBツリー、デカルトツリーなど。c++のstd :: set）を使用することです。このツリーにペアを保存します

<AttributesWeightsSum, ObjectID>.

次に、オブジェクトの挿入と削除にはO（P + logN）の時間がかかり、Pは属性の重みの合計（つまりO（max_attributes_in_objects_count））の計算の複雑さであり、Nはセット内のオブジェクトの最大数です。このツリーをトラバースすることにより、上位K個のオブジェクトのIDを見つけるのはO（K）になります。

上位K個のオブジェクトを列挙する必要はなく、上位K個のオブジェクトを1つだけ検索する場合は、バランスの取れた検索ツリーの代わりに、上記と同じペアを含むバイナリヒープを使用できます。

于 2013-02-10T10:57:51.440 に答える