c - cの短い短いint？

Question

できるだけ多くの記憶を絞り出そうとしています。intの行列があり4.9999995e13ますが、必要なのは true または false だけです。基本的に、これらの int ごとに 1 ビットのストレージしか必要ありません。

Cには単一のビット型がないことを理解しています（誰かが理由を説明できるかもしれません）。また、short short int存在する場合、charと同じ1バイトになることも知っています。ただし、C のすべての論理演算は int を返します (他のいくつかの関数も同様です)。

だから私の質問は：

存在させる方法はありshort short intますか？
代わりに使用charすると、すべてのキャストを実行する必要があるため、パフォーマンスが低下intしますか?
私が見逃している別の方法はありますか？

関連する場合に備えて、C99用のGCCでコンパイルしています。

編集このウィキペディアのページでタイプがあるのを見たばかり_Boolですが、これは実際に標準ですか?

score 6 · Accepted Answer

型は Cの_Bool最新バージョンでは標準ですが、 a は_Bool依然として少なくとも 1 バイトを占めるため ( acharと同様に、定義により)、それはあなたが望むものではありません。

いいえ、多くのブールビットが必要な場合は、ビットフィールドまたはビット配列にパックする必要があります。C にはビットフィールドの標準データ型がないため、特定のオフセットでビットを取得するための独自のマクロまたは関数を作成する必要もあります。また、十分な RAM を備えた 64 ビットマシンでこれを実行することを願っています。そうしないと、メモリが不足して高速になります。

score 5 · Accepted Answer

約50テラビットのデータがあります。それらすべてを一度にRAMに収めたいですか？1ビットの情報を保持するために1ビット以上のRAMをorderで使用することはまったく正気ではありません。それでも、コンピュータはこの地球上で最大のスーパーコンピュータとほぼ同じサイズである必要があります。ビットパッキングのパフォーマンスを忘れてください。まったく違うことを心配する必要があります。

score 5 · Accepted Answer

必要なのはビットマップ（またはウィキペディアで呼ばれているビット配列）です。

そして、Cの中で最小の整数ストレージクラスであるashort short intのようなものはありません。char

このアプローチを使用すると、パフォーマンスのオーバーヘッドが発生する可能性がありますが、intへの暗黙のキャストが原因ではなく、配列メンバーを直接操作するよりもビットマップの操作が難しいためです。

小さな例が説明に役立つかもしれません：

通常の整数行列の使用：

int mat [8 * 8]; //行のメジャーオーダーを想定
int is_element_set（int x、int y）{
  リターンマット[y*8 + x];
}

ビットマップを使用する場合：

unsigned char mat[8]; // assuming CHAR_BIT == 8
int is_element_set(int x, int y) { 
  return mat[y] & (1 << x);
}

score 4 · Accepted Answer

5e13 では、ビットフィールドを表すためだけに必要なストレージは約 5.6 テラバイトです。おそらく、問題を処理するためのより良い方法があります。

score 1 · Accepted Answer

他の人が示唆しているように、おそらくビットフィールドを使用する必要があります。

さらに、true/false 値のみを使用していて、値の 1 つが他の値よりも一般的でない場合は、暗黙的なコーディングの使用を検討してください。これは、マップデータ構造を使用して簡単に実現できます。グラフを操作しているとき、グラフがまったくまばらな場合、これにより膨大な量のメモリが節約されます。これを上記のビットパッキング手法と組み合わせると、すべてを RAM に収めることさえできます。ただし、インデックス作成についてはかなり賢くする必要があります。

処理中にパフォーマンスが低下することを気にしない場合 (つまり、処理よりも保存することの方が心配な場合) にできるもう 1 つの方法は、ブロック単位で圧縮アルゴリズムを使用して構造体を実行することです。そのようなもので90％以上節約できるbzip2用のCライブラリがあります。欠点は、これには (非常に!) 長い時間がかかることです。これで、動的マルコフ圧縮 (DMC) のようなビットごとの圧縮から同等のパフォーマンスが得られる可能性があり、それらははるかに高速です。

score 1 · Accepted Answer

ANSI C で利用可能なビットフィールド構造体の賢明な実装を使用できるかもしれません。

このようなもの：

typedef struct node_t_
{
    char bit0 : 1;
    char bit1 : 1;
    char bit2 : 1;
    char bit3 : 1;
    char bit4 : 1;
    char bit5 : 1;
    char bit6 : 1;
    char bit7 : 1;
} node_t;

次に、このマトリックスの要素を取得および設定するための高速な関数 (おそらくマクロ) を作成できます。ただし、このようなものを実装したことはありません。

score 1 · Accepted Answer

C99stdbool.hでは、bool. ただし、ここでの問題は、4.9999995e13/8 が多かれ少なかれ 6.2500e+12 ($10^9$ は G バイト、$10^12$ は T バイト) になるため、6 T バイトを超える実 + 仮想メモリが必要になることです (ラッキー）。これは、何か他のことを間違っていることを示唆しています。より少ないメモリを使用して処理できるサブ問題で問題を「スケーリング」する必要があります。

score 0 · Accepted Answer

できるだけ多くの記憶を絞り出そうとしています。

これが正しい場合、1 ビット分のデータを格納するために 8 ビットを無駄にすることはありません。ビットフィールドを使用します。

マトリックスの内容の種類について何か知っている場合は、他の最適化を使用できます。たとえば、行列の大部分が通常 0 に設定されていることがわかっている場合、1 に設定された要素の x、y ペアのみを保存できます。

そうでない場合、4.9999995e13 は約 6 TB の RAM を必要とします!

c - cの短い短いint？

8 に答える 8

Related

Reference