問題タブ [binary-matrix]

要素ごとに、異なる行列のバイナリ値を 1 つの行列に連結したいと考えています。

例えば、

これはどのように行うことができますか？

100000 x 100000のような巨大なバイナリ マトリックスがあります。

この記事http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdfを読んで、バイナリマトリックスを記憶して操作するための最良のトレードオフはboost::dynamic_bitsetsを使用することであることを理解したようです。

「表 2: データ構造を実装したプログラムの相対時間パフォーマンス」では、 std :: vector<bool>が最後の位置にあり、boost::dynamic_bitsetが最初の位置にあります。

また、「表 3: データ構造を実装したプログラムの相対的なメモリ使用量」では、 std ::vector<bool>が最初の位置にありますが、boost::dynamic_bitsetは 2 番目の位置にあります。

また、論文の7ページ目に次のような記述があります。

「std::vector の印象的なメモリ パフォーマンスにもかかわらず、その悲惨な時間パフォーマンスにより、大規模なアプリケーションでは使用できなくなります。」

そして結論では：

「boost::dynamic_bitset は、実行速度の点で他のほとんどの実装よりもかなり効率的であることを示しましたが、std::vector<char> を使用した実装は、メモリ効率の点で他の実装よりも優れていました。」

私の場合、ターゲットマシンはXEON PHIです。
私のターゲット アプリケーションはGame Of Lifeです。
バイナリ行列を ROWS x COLS セルのバイナリ配列として表現しました。

-O3最適化フラグを指定したicpcコンパイラを使用して、3 つの異なる構成でコードを試しました。

1. ブール値の配列
2. ブール値の配列 + ベクトル化、つまり、ここで説明されているように配列表記を使用してコードを変更します

3. boost::dynamic_bitsets . この場合、配列表記を使用してコードを変更できませんでした。試行すると、次のエラーが発生するためです。

   std::vector<bool>を使用した場合と同じエラー。

100000 x 100000 サイズのマトリックスのゲーム メイン ループの 1 回だけの反復のパフォーマンスを調べると、ソリューション 2はソリューション 1よりもほぼ 6 倍高速に動作することがわかりましたが、予想外にソリューション 1はソリューション 3よりも 2 倍高速に動作します。

結論として、次の質問をする必要があります。

1. 一般に、HUGE MATRIXを格納/操作するための最も効率的なデータ構造は何ですか?
2. ターゲット マシンがXEON PHIであることを知っていれば、 「1 に答える」よりもうまくできるでしょうか?
3. vector<bool>またはboost::dynamic_bitsetsにベクトル化を適用することは可能ですか?

特定のターゲット アプリケーションである Game Of Life について回答していただきありがとうございます。
しかし、他のコンテキストで巨大なバイナリ マトリックスを操作する場合はどうでしょうか。

次のような Python Pandas DataFrame があります。

a, bユーザー機能のリストを表す文字列です

これを次のようなユーザー機能のバイナリマトリックスに変換するにはどうすればよいですか:

同様の質問Creating boolean matrix from one column with pandasを見ましたが、列にはリストであるエントリが含まれていません。

私はこれらのアプローチを試しましたが、2つをマージする方法はありますか:

pd.get_dummies()

df[1].apply(lambda x: pd.Series(x.split()))

このタイプのバイナリ マトリックスを作成するさまざまな方法にも興味があります。

どんな助けでも大歓迎です！

ありがとう

Rのバイナリマトリックスにbyclusteringを適用したい.「biclust」と呼ばれる素敵なパッケージが利用可能ですが、それは私が望むものすべてを表示するわけではありません.

次のようなバイナリマトリックスがあります。

そして、私の目標は、これを次のように二重クラスター化 (および表示) することです (色付けされている場合があります)。

設定コード:

「biclust」R パッケージの biclust 関数を適用しました。

実際、期待される2つのクラスターを取得します。

次の方法で、両方のクラスターを別々に表示できます。

クラスター化されたマトリックス全体 (左上隅にある 1 つのクラスター) を次のように表示できます。

ここまでは良いですが、私が欲しいのは:

1. ディスプレイの色が切り替わりました。1 が赤、0 が緑になりました。
2. 元の行列の行と列を見たいです。現在、特定のクラスターの行番号と列番号のみが表示され (drawHeatMap を使用)、クラスター化されたマトリックス全体 (drawHeatMap2) の行番号と列番号は表示されていません。
3. 整然としたクラスター化されたマトリックスが必要です。これで、drawHeatmap2 で指定されたクラスターのみが左上隅に表示されますが、マトリックスの残りの部分については、残りのマトリックスの左上隅から右下隅まで他のクラスターも適切に並べたいと思います。

これらの変更は可能ですか (「biclust」パッケージを使用)? それとも、Rで別の方法で行う方が良いですか?

0 と 1 だけを含むMbyの行列の場合、同一の行を作成しない方法は存在しません。Nたとえば、 と の場合N = 3、M = 31 つの解決策は次のとおりです。

徹底的な順列アルゴリズムの使用が機能することは知っていますM < 2^Nが、一般的なケースであるため、より良い解決策があると考えています。