0

次のことを効率的に実行できるデータ構造にデータを保存しようとしています。

タイプ1の配列が10個、タイプ2の配列が10個あり、それぞれ100個の要素があります。これらの各配列には、100個の変数の値が格納されます。これらに付随して、対応する変数IDを含む20個の配列があります。タイプ1の配列には、1000個の変数の値が格納され、タイプ2の配列には、同じ1000個の変数の異なる値が格納されます。

ここで、タイプ1の配列の変数の値とタイプ2の配列の値の差をとる必要があります。Aをタイプ1の配列の1つとします。問題は、Aの変数がそれぞれ10個広がることです。タイプ2の10個のアレイすべてにわたって。

各配列の値を反復処理する必要があるため、ハッシュマップは役に立ちません。何か案は？

4

1 に答える 1

0

このような操作を頻繁に行う場合は、プログラムの起動時に構築してインデックスを作成し (構築にはO(n^2)時間の複雑性があります)、後で参照することをお勧めします。

struct LookupEntry {
   A *item1;
   B *item2;
};

std::map< IdType, LookupEntry > index;

これにより、タイプの配列を直線的に通過し、一定時間内Aにタイプの配列から値を取得できます。同様の方法でからアイテムをB差し引くこともできます。BA

または、インデックス項目を調べて、ある項目から別の項目を減算することもできます。

于 2012-08-10T09:17:42.277 に答える