1024 * 1024 * 1024 * 4スパース配列のサイズを圧縮する方法

Question

サイズが1024 * 1024 * 1024 *のスパース配列があります。この配列の項目はバイトです。したがって、配列のメモリは4Gです。これは疎配列です。すなわち、約600Mしかない非ゼロの項目です。うまくいけば、（2〜3Gに圧縮された）疎アレイを圧縮するための記憶構造が提案され、良好なアクセス速度を有することが望ましくあり得る。

Answer 1

適切な表現は、スパース配列でどのような操作が望ましいかによって異なります。一般的なアプローチは、非ゼロ項目の位置とその値をデータ構造体に格納することです。

1つのオプションは、ハッシュテーブルを使用することです。 get()とput()のようなハッシュテーブルの動作により

enum {NumDimensons = 4}; 
struct ArrayLocation { 
    int16_t location[NumDimensions]; 
}; 

typedef uint8_t ArrayValue; 

// Hash Table with key as ArrayLocation and value as ArrayValue 

は簡単ですが、反復はありません。反復が重要な場合は、バイナリ検索ツリーを使用することもできます。