0

私の目標は、(メモリ制限のない世界では) 約 10^5 x 10^5 で double で埋められる行列の最も関連性の高いエントリを格納するための効率的な構造を作成することです。行列は対称であるため、実際には (10^10)/2 の値のみが含まれます。

シミュレーションでエントリに何度もアクセスする必要があるため、高速検索が重要です。

構造を管理しやすくするために、使用される可能性が低いメンバーを削除します。インデックスが (int_x1, int_x2) の場合、たとえば x1 を含むすべてのペアを削除したいことがよくあります。

このタスクに最適な構造または構造のセットは何ですか? 2 つの int の適切なハッシュは何ですか?

移植性のために、Boost は避けたいと思います。私は現在、プログラムの他の場所で TR1 の unordered_map を使用しています。キーペアで unordered_map を再度使用することを考えていましたが、この方法でエントリを効率的に削除する方法がわかりません。また、適切なハッシュ関数がどのようになるかわかりません。

私は初心者のプログラマーなので、明白なことを述べてください。

4

1 に答える 1

1

データがかなりまばらになる場合は、ハッシュテーブルの配列を使用できます。

hash_map<int,double> matrix[] = new hash_map<int,double>[10000];
for (int i = 0; i < 10000; i++) matrix[i] = new hash_map<int,double>();

次に、値（x、y）を検索するには、配列にxのインデックスを付け、ハッシュテーブルでyを検索します。

注意すべきいくつかのこと：

  • 多くのハッシュテーブルを反復処理する必要があるため、削除にはかなりのコストがかかる可能性があります。
  • 削除/挿入するとストレージの合計が増える可能性があるため、hash_mapsを時々trim（）する必要があります。
  • 対称性を利用するのは簡単なはずです。
于 2009-11-02T23:58:32.217 に答える