java - ハッシュテーブルを使用せずにJavaでスパース行列を構築しますか？

Question

私のプロジェクトでは、グラフの隣接行列を作成しようとしています。スペースと時間の考慮のために、スパース行列を使用することになっています。これは、私の理解では、ハッシュマップを使用すると最も簡単に実行できます。残念ながら、隣接リストも実装する必要がありました。これは、上記のハッシュマップを使用して実装しました。隣接行列は構造的に異なる必要があるため、行列にハッシュマップを使用することはできません。他に実装する方法はありますか？

Answer 1

n 次元の行列の場合、バイナリ ツリーの変形を使用できます。などを挿入するときは、葉が見つかるまで寸法を循環します。

したがって、(2, 5)、(10, 1)、(5, 6)、(3, 4) という単純な 2 次元データセットをこの順序で挿入すると、次のようになります。

 (2, 5)
    \
   (10, 1)
       \
      (5, 6)
        /
    (3, 4)

(2, 5) はルートに挿入されます。

(10, 1) は 10 > 2 なので正しくなります。

(5, 6) は、5 > 2 であるため、(2, 5) の右になります。次に、6 > 1 であるため、(10, 1) の右になります。

(3, 4) は右 3 > 2 になります。次に、右 4 > 1 になります。次に、左 3 < 5 になります。

Answer 2

スパース行列に関するウィキペディアのページには、 6 つの代替案がリストされています。

• キーのディクショナリ (DOK)。
• リストのリスト (LIL)
• コーディネート一覧（COO）
• エール形式
• 圧縮されたスパース行 (CSR または CRS)
• 圧縮スパース列 (CSC または CCS)

もう 1 つの選択肢はAdjacency Listです。

最後に、隣接行列をビットマップとして表し、各行列セルを特定のビットにマッピングすることも検討する必要があります。(典型的な JVM は、boolean[]1 バイトあたり 1 つのブール値を持つマシン バイトの配列として a を表します。) Java ハッシュ テーブルとリストのスペース オーバーヘッドを考慮すると、隣接行列は、かなり大きく ... 疎である必要があります。より複雑な「まばらな」データ構造により、スペースを節約できます。

Answer 3

リストのリストまたは座標リストを使用できます。