軽量マトリックス

は、私は単にint行列を使用することができます知っているが軽量マトリックス

matrix[i][j] = [true|false]

で、標準Cで行列が真理値表を格納しなければならないN×N個を言います、またはC99を使用している場合はbooleanタイプですが、メモリの点で最も軽量なソリューションを探していました。

命名されましたか？ –

@nmこれは実際に私がこれまで実装してきた解決策ですが、より効率的な解決法があるかどうかを知りたかったのです（そして非常に面白い答えが出ています:) –

真理値表は1と0 ？ランダムですか？それは疎なのか密なのか？典型的なNとMはどれくらいですか？ – osgx

最も軽量なソリューションは、charに8つのブール値を保存している：

unsigned char getBit(char byte, unsigned short bit){ 
    assert(bit < 8); 
    return byte&(1<<bit); 
}

その後、あなたは各行のバイトを保存することでN x 8M行列を格納することができます。これらのバイトの多くが空の場合は、スパース行列形式（たとえば、圧縮スペア行）を使用する必要があります。

2012-02-14 18:01:08 Zeta

これはキャッシュの破棄も避けることができますか？ –

まあ、行間を繰り返す場合は - 多分。上記のソリューションはブール値にちょうど1ビットを使用します。しかし、行列を計算または操作するときは、getBitのような関数を使わず、最適化を確実にするために、 '|、^、＆、'と '0x01'、' 0x02'、 '0x04' 。 – Zeta

ありがとう、実際には、関数を使用せずに直接ビット単位の操作をコードで処理するいくつかの有用なマクロを見つけました...うまくいくと思います... :) –

マトリックスが特に散在している場合は、ハッシュ実装またはリストのリストを使用できます。

また、iまたはjがシステムが格納できる最大の整数よりも小さい場合は、ブール値のビットセットを1つの整数にパックして、各ビットを1つのインデックスに対応させることができます。ビット単位の操作を使用してアクセスまたは変更できます。メモリの面で

2012-02-14 17:58:11 shuttle87

std :: bitsetは何用ですか？

2012-02-14 18:19:47

私はC++を使用していません。） –

oops誤読タグ残念 –

より効率的な解決策があるかどう

あなたが単一のビットに1つの以上ブール値を保存したい場合は、いくつかの圧縮を使用する必要があります。

圧縮は非ランダムデータでのみ機能します。また、圧縮データへのランダムアクセスは遅くなる可能性があります。

最も簡単な方法の1つはRLE（各行を独立して圧縮）です。もう少し複雑なのは、データを疎な行列に格納することです（1よりもずっと多くの値が0の場合のみ、このメソッドは多次元データを圧縮できます）。

はるかに複雑な圧縮がここで使用されます：http://crd-legacy.lbl.gov/~kewu/fastbit/index.htmlセルごとに1ビットを使用し、 `符号なしlong`s、たとえば、中にビットを格納すると間違って何"Word-Aligned Hybrid compression scheme"

2012-02-14 18:24:36 osgx

答えて