2

これが私の問題の定義です。それぞれラベルを含む700 万個の indexの配列があります。簡単にするために、私が扱っている配列の例を次に示します: [1 2 3 3 3 5 2 1 7]。

この配列を調べる必要があり、ラベルに出くわすたびに、ラベルの場所を同じラベルの他のすべての「セット」に入力します。配列が非常に大きいため、任意の時点で特定のラベルの場所にのみアクセスしたいので、たとえば、3 の場所にのみアクセスし、それらの場所を処理して 5 に変更したいとしますが、もっとやりたい1回の操作だけでなく、すべてのラベルで個別に実行したい. 私の例のような小さな配列では、配列に固執するだけで簡単に思えます。ただし、700 万点の配列があるため、ラベルの検索を完了してから操作するには、はるかに時間がかかります。

混乱を解消するために、私の例を使用して、例の配列で次のようにします。

  • 0 と 7 を含むセットにマップされた 1
  • 1 と 6 を含むセットにマッピングされた 2
  • 2、3、および 4 を含むセットにマップされた 3
  • 5 を含むセットにマッピングされた 5

もともと、私は元の配列で処理を行い、単に配列を操作していました。これには、各ラベルに対応するインデックスの数を決定するのに約 30 秒かかりました (したがって、1 のサイズは 2、6 のサイズは 2、3 のサイズは 3 などであると判断できました。しかし、そうではありませんでした。このメソッドを使用して前記ラベルの位置を生成します. したがって、参照されたラベルのすべてのインデックスを見つけたら終了を追加することで高速化されましたが、各ラベルの位置を見つける残りの処理全体で時間が追加されました. 、検索を停止します。

次のステップでは、を使用しましたmap<int,set<int>>が、これにより最終的に時間が 100 秒まで増加しましたが、後の処理時間は短縮されましたが、時間の大幅な増加を正当化するのに十分ではありませんでした。

まだ実装していませんが、追加のステップとして、ラベルに対応するインデックスを使用してセットの配列を初期化し、このメソッドを実行しようと計画しています。

hash_maps も試してみましたが、役に立ちませんでした。Unordered_sets と unordered_maps は Visual Studio 2005 の STL に含まれていないため、これら 2 つの構造で上記を実装していません。

キーポイント: 最大ラベルを認識し、すべてのラベルが連続するように配列を前処理しました (最小ラベルと最大ラベルの間にギャップはありません)。ただし、元の配列ではランダムに分散しています。これは、セットサイズのデータ​​構造の初期化に役立つ場合があります。ラベルに対応するインデックスの順序は重要ではありません。指定されたデータ構造内のラベルの順序も重要ではありません。

編集:背景として、配列はバイナリ イメージに対応し、バイナリ シーケンシャル ラベル付けを実装して、すべてのバイナリ blob にラベルが付けられた UINT16 のバイナリ イメージと同じサイズの配列を出力しました。ここでやりたいことは、各ブロブを構成するポイントのマップをできるだけ効率的に取得することです。

4

2 に答える 2

1

そのタスクになぜそのような複雑なデータ構造を使用するのですか? ベクトルのベクトルを作成して、各ラベルのすべての位置を格納するだけです。また、各ラベルに必要なスペースを前処理することで、面倒なベクトル メモリの割り当てを回避することもできます。そんな感じ：

vector <int> count(N);
for(size_t i = 0; i < N; ++i)
    ++count[dataArray[i]];
vector < vector <int> > labels(N);
vector <int> last(N);
for(size_t i = 0; i < N; ++i)
    labels[i].resize(count[i]);
for(size_t i = 0; i < N; ++i) {
    labels[dataArray[i]][last[dataArray[i]]] = i;
    ++last[dataArray[i]];
}

O(N) 時間で動作します。これは、700 万の整数に対して 1 秒のように見えます。

于 2013-06-03T17:14:04.243 に答える
0

これには、必ずしも汎用マップ (またはハッシュ テーブル) を使用する必要はありません。

私の最初の直感は、700 万 (または任意の N) の位置の 2 番目の配列「位置」と、範囲 [最小ラベル、最大ラベル] に対応する 3 番目の配列「last_position_for_index」を作成することです。これはほぼ確実に、どの種類のマップよりも少ないストレージを使用することに注意してください。

last_position_for_index のすべてのエントリを予約済みの値に初期化してから、(未テスト) のようなもので配列をループできます。

for (std::size_t k = 0; k<N; ++k) {
  IndexType index = indices[k];
  positions[k] = last_position_for_index[index-min_label];
  last_position_for_index[index-min_label] = k;
}
于 2013-06-03T17:01:01.277 に答える