2

これらのノードのペア (ID) があるとします。

  • 0 1
  • 0 8
  • 500 4
  • 8 300

一意のノードの数を知っています: 6. 500x500 マトリックスを割り当てずに、それらをマトリックスに保存するにはどうすればよいですか? どの種類のマッピングを使用できますか?

前もって感謝します！

4

2 に答える 2

4

あなたが望むかもしれないのはスパース行列です - これは、行列にインデックスを付けるためのx、yに対応する値とそこに格納された値を含む配列として想像できます。これにより、ほとんどがゼロである行列を少量で格納できますスペースの。このデータ構造のメモリ オーバーヘッドは O(n) です。ここで、n は行列内のゼロ以外のエントリの数です。

実際には、パフォーマンス上の利点のために実際の配列以外のものを使用できます。これは、特に配列が存在しない場合 (最も一般的なケース)、x、y の配列を検索するのにコストがかかるためです。

1つのオプションは、x、y位置をハッシュしてキーを生成することにより、高速ハッシュマップタイプ構造を使用して値を保存することです...

詳細: http://en.wikipedia.org/wiki/Sparse_matrix

于 2012-11-09T16:07:50.653 に答える
1

これは疎行列と呼ばれ、使用できる表現はたくさんあります。どちらが必要かは、迅速に実行できるようにする必要がある操作によって異なります。

詳細については、ウィキペディアの疎行列の記事を参照してください。

于 2012-11-09T16:11:30.250 に答える