問題タブ [sparse-matrix]

Jscript にスパース配列があり、null 以外の要素が負のインデックスと正のインデックスの両方で発生しています。for in ループを使用しようとすると、最小 (負) のインデックスから最大の正のインデックスまで配列をトラバースしません。代わりに、要素を追加した順序で配列を返します。列挙も機能しません。それを可能にする方法はありますか？

例

ループすると、A、C、B の順に表示されるはずです。

私は Java で書かれたプロジェクトに取り組んでいます。このプロジェクトでは、非常に大きな 2 次元疎配列を構築する必要があります。それが違いを生む場合、非常にまばらです。とにかく、このアプリケーションの最も重要な側面は、時間の効率性です (メモリの負荷を想定しますが、標準の 2 次元配列を使用できるほど無制限ではありません。重要な範囲は両方の次元で数十億です)。 ）。

配列内の無数のセルのうち、オブジェクトを含む数十万のセルがあります。セルの内容を非常に迅速に変更できる必要があります。

とにかく:この目的のために特に優れたライブラリを知っている人はいますか? Berkeley、LGPL、または同様のライセンスである必要があります (製品を完全にオープンソースにすることはできないため、GPL は使用できません)。または、自作のスパース配列オブジェクトを作成する非常に簡単な方法があれば、それも問題ありません。

MTJを検討していますが、品質についての意見は聞いていません。

私は C++ で疎行列クラスを作成しています。このクラスでは、すべての行と列が、作成したクラス (適切な名前: LinkedList) からの連結リストの配列です。

このマトリックス内の 1 つのセルへの「スマート」ポインターであるクラスを作成したいと考えています。

そのクラスでは、たとえば、マトリックスのリンクされたリストを移動するためLIPointerの演算子関数を実装します。++

を作成するたびに行列配列とサイズ変更された要素の参照を移動せずにこれを行うエレガントな方法はありますlinkedlistPointerか?

stl::arrayetc. は自分で作らないといけないので使えません。

宣言は次のとおりです。

アドバイスや指示をいただければ幸いです。

更新:マトリックス全体で実行する必要があります。そのため、配列と行列のサイズを (参照により) 移動する必要があると思います。意図した効果は、これが最初の行のリンクされたリストの最後のセルから 2 番目の行の最初のセルになることです。

次のような、プロジェクト リビジョン全体のソース ファイル メトリックの値を表すテーブルがあります。

(上記のデータのリレーショナル ビューは異なります。各行には次の列が含まれます: Revision、FileId、Value。データの計算元となるファイルとそのリビジョンは Subversion リポジトリに格納されるため、リポジトリのリレーショナルスキーマの構造。)

10000 リビジョンには最大 23750 ファイルが存在する可能性があります (これはImageMagick描画プログラムの場合です)。ご覧のとおり、ほとんどの値は連続したリビジョン間で同じであるため、テーブルの有用なデータは非常にまばらです。データを保存する方法を探しています

• レプリケーションを回避し、スペースを効率的に使用します (現在、非スパース表現では、保存したいデータの 10% 未満に 260 GB (データ + インデックス) が必要です)
• SQLクエリを使用して特定のリビジョンの値を効率的に取得できます(リビジョンまたはファイルを明示的にループする必要はありません)
• 特定のメトリック値のリビジョンを効率的に取得できます。

理想的には、ソリューションは特定のRDBMSに依存せず、 Hibernateと互換性があるべきです。これが不可能な場合は、Hibernate、MySQL、または PostgreSQL 固有の機能を使用して生活できます。

スパース マトリックスを扱う場合、Matrix Market 形式を CRS (Compressed Row Storage) に変換するにはどうすればよいですか?

行列の固有値を計算するのにどれくらいの費用がかかりますか?

最高のアルゴリズムの複雑さは?

1000 x 1000 のマトリックスがある場合、実際にはどのくらいの時間がかかりますか? マトリックスがスパースであれば、それが役立つと思いますか?

固有値計算が終了しない場合はありますか?

ではR、次のおもちゃの例のように固有値を計算できます。

誰がそれが使用するアルゴリズムを知っていますか?

固有値を計算する他の (オープンソース) パッケージはありますか?

疎行列を格納するアプリケーションがあります。この行列には、主に行列の主対角線周辺に存在するエントリがあります。この種のスパース行列を効率的に処理できる効率的なアルゴリズム (または既存のライブラリ) があるかどうか疑問に思っていましたか? できれば、これは、各マトリックス エントリをユーザー定義型にできる一般的な実装にすることをお勧めします。

質問/回答に応じて編集:

ほとんどが主対角線の周りにあると言うとき、ほとんどの行列の特徴は、ほとんどのエントリが主対角線から離れてクラスター化されているが、対角線の近くにゼロがあり、遠く離れたゼロ以外の値がある可能性があるということです。対角線。ここで「ほとんどの」場合に効率的なものが必要です。

これを何に使うのでしょうか？行のすべての値または列のすべての値に効率的にアクセスできる必要があります。格納される値はブール値です。例は次のとおりです。

1. 行のすべての真の値について、各列に真が表示され、列のすべてのエントリを何かに設定します
2. 行のすべての false 値について、エントリを何かに設定します

これは以前はすべてリンクされたリストで行われていましたが、実装するのは非常に混乱していました。疎行列を使用してアルゴリズムを改善できることを期待していましたが、「適切な」タイプの疎行列アルゴリズムを見つけることは困難であることが判明しました。

ps 今までの反応ありがとう

.NET/C# 用の優れた (十分にテストされ、完全な機能を備え、理想的には優れたインターフェイスを備えた) マトリックス ライブラリを探しています。ここでの私の主な要件は、無料であること (この場合はオープンソースかどうかは特に気にしません) と、できれば疎行列演算をサポートすることだけです。必須要件は、すべての基本演算 (乗算、転置、反転など) と、固有値と固有ベクトルの検索です。固有値を発見するための解析的手法ではなく数値的手法の実装、特にランチョス アルゴリズム疎行列の場合、これから扱う行列が非常に大きく (10,000 以上の長さ)、正方行列であり、適度に疎であるため、非常に望ましいでしょう。そうは言っても、私はそこに少し多くを求めている可能性があるので、合理的に完全な行列ライブラリの提案は素晴らしいでしょう.

現在、Python にはそのようなタスク (つまりNumPy / SciPy ) に役立つライブラリが 1 つまたは 2 つあることを認識していますが、残念ながら .NET にはその分野が欠けているようです。

少し検索すると、.NET 用の次のライブラリが見つかりました。これを使用できる可能性があります。

• ルッツ・ローダーのマップパック
• DotNetMatrix (コードプロジェクト)
• C# マトリックス ライブラリ(CodeProject)

ただし、私はこれらのライブラリやその他のライブラリを使用した経験がまったくないため (いずれにせよ、それぞれを適切にチェックするのに十分な時間がありません)、さまざまなライブラリに関する推奨事項について議論できる人がいれば、非常にありがたいです。 、特に私の用途への適合性に関する長所/短所、およびそれらの一般的な経験.

MatLab に頼ることは常にオプションですが、優先されるものではありません。行列の計算を自分のプログラムに直接統合できればはるかに便利だからです。

スパース行列に対していくつかの数学演算を実行する必要があります。特に行列の行数が200を超える可能性があるため、配列を使用することがメモリを利用する最も効率的な方法ではない可能性があることに気付きました。リンクリストの使用も検討しましたが、それが良いかどうかはわかりません。この状況に適したデータ構造[アプローチ]はありますか。

.NET アプリケーションで最大 4 次元の疎行列が必要です。マトリックスのサイズ (.NET 配列として表される場合) は、400MB を超える可能性があります。

配列は非常にまばらである可能性が高く、インスタンス化して非常に迅速に破棄できるようにする必要があります (ただし、それは不可能ではありません)。したがって、私は.NET 3.5から消費可能なスパース配列ライブラリを求めています（Managed C ++からBGLを使用することは除外されていると思いますか？）。低コストでキャッシュできる密度の高い形式にシリアライズ可能である必要があります。

そのようなものは (まだ) .NET に存在しますか? フォス? 成熟した？

ティア

アンドリュー・マシューズ