2

私は自分が取り組んでいるこのプロジェクトを持っています。以下の条件が適用されます

  1. このプロジェクトでは、1つの巨大なアレイを作成する必要があります（最大7.13e + 17のアレイを作成できるといいのですが、このターゲットはまだ先にあります）。
  2. 配列内の各セルには、0、1、2の3つの値のいずれかを含めることができます。
  3. 言語としてC++を使用しています。

通常の動的配列コマンドを使用してみました

int * p;
int i;    
i=[size]; //This is calculated somewhere else.
p= new (nothrow) int[i];

しかし、私が理解している限り、この配列は、intの最大サイズの可能な最大サイズの配列を作成します。コードを変更して次のコードを使用した場合

long long * p;
long long i;    
i=[size]; //This is calculated somewhere else.
p= new (nothrow) long long [i];

次に、配列内の各セルは「long long」型であるため、配列は非常にメモリを大量に消費します。long longを使用して配列を作成し、配列内のセルの数を決定し、サイズがintのすべてのセルを持つ方法はありますか？

どうもありがとう、ウリエル。

編集：詳細については。

  1. この問題は主に理論的なものであり、私の修士論文の一部です。私はまだこのプログラムが可能な限りうまく機能することを望んでいます。
  2. 私の現在のステップは、2.56e + 09アイテムのアレイでこれを機能させることです。簡単な計算では、少なくとも0.6ギガバイトのアレイについて話していることがわかります。これは私のシステムで対処できるはずです。それでも、必要なスペースの量が実際には4.5GBであっても、現在のコーディングソリューションではこの目標を達成できません。
4

7 に答える 7

7

long longを使用して配列を作成し、配列内のセルの数を決定し、サイズがintのすべてのセルを持つ方法はありますか？

配列の型が、サイズを指定するために使用される変数の型と同じである必要がある理由はありません。したがってlong long、サイズを指定する変数に使用し、次にint配列のタイプに使用します。

int * p;
long long i;    
i=[size]; //This is calculated somewhere else.
p= new (nothrow) int [i];

ただし、「最大7.13e+17」の配列を作成する必要があると言うと心配です。あなたがバイトを意味するのか要素を意味するのかはわかりませんが、どちらの方法でも、まっすぐな配列としては信じられないほど巨大です。それはペタバイトのデータの領域に入っています。

32ビットプログラムでは、それは単純に不可能です。理論的には、最大数ギガバイトのアレイを使用できます（ただし、実際にはほとんどの場合はかなり少なくなります）。

64ビットプログラムでは、理論的には、私が知る限り、これほど大きな配列を割り当てることができます。しかし、ほとんどのマシンが実際にそれを処理できるかどうかについては懐疑的です。この量のデータはマシンのRAMをはるかに超えるため、オペレーティングシステムはこの配列の大部分をページファイルにプッシュすることを余儀なくされます。しかし、ペタバイトサイズのページファイルは、現在最も一般的なマシンのハードドライブ容量をはるかに超えています。

いずれにせよ、巨大な配列全体を一度に割り当てるのではなく、おそらく別のスキームを真剣に検討する必要があります。

于 2010-09-12T18:06:54.837 に答える
4

パッキング密度を最大化する必要があるため、ビットフィールドを使用するのがおそらく最善です。

struct item_pack { 
    char a:2;
    char b:2:
    char c:2;
    char d:2;
};

次に、これらの配列を作成し、プロキシオブジェクトを使用して、個々のアイテムの読み取りと書き込みをサポートできます。ただし、プロキシオブジェクトで実行できる量にはいくつかの制限があるため、少し注意する必要があります。これをどのように使用しようとするか。に関する記事のいくつかを少し見ると、いくつかのvector<bool>合理的なヒントが得られるはずです。その特徴のほとんどは、この一般的なタイプの実装に由来しています。汎用コンテナとしての欠点にもかかわらず、これは制限内で機能し、ほとんどの明白な代替手段よりもはるかに緊密な情報のパッキングを提供します。

于 2010-09-12T18:07:47.637 に答える
2

このプロジェクトでは、1つの巨大なアレイを作成する必要があります（最大7.13e + 17のアレイを作成できるといいのですが、このターゲットはまだ先にあります）。

これは、大規模な割り当てを回避するために、キーがインデックスであるデジタルツリー（またはbツリー）という専用の構造を作成することを要求します。

大規模な割り当て、特に再割り当ては、不要なメモリの断片化を引き起こす可能性があります。大きな配列を小さなチャンクに分割すると、配列の拡張が容易になるだけでなく、疎な配列の表示も可能になります。

NB~7.13e+17は約60ビットの長さです。それだけのRAMをサポートできるハードウェアもありますか？業界をしっかりとフォローしているわけではありませんが、58ビットのアドレスバスを備えたNUMAアーチについて簡単に聞きましたが、60ビット以上のアーチについては何も聞きませんでした。

配列内の各セルには、0、1、2.2の3つの値のいずれかを含めることができます。

セルに含まれる値が3つだけの場合（2.2は2として表すことができます）、2ビットの情報になります。uint32_tつまり、 16個の値とuint64_t32個の値にパックできるということです。

既存のデジタルツリーの実装を見つけて（または独自にロールして）、インデックスの主要な上位ビットとして使用することができます。元のインデックスの残りのビットは、値がパックされた配列であるツリーリーフへのインデックスになります。std::mapトライの代わりに使用する例として、テストされていません。

enum {
   LS_BITS = 16,
   MS_BITS = 64-LS_BITS
};

enum {
   VALUE_BITS = 2,
   VALUE_MASK = ((1<<VALUE_BITS)-1)
};

// this represents an array of `1<<LS_BITS` values
struct leaf_node {
   uint64_t packed_data[ ((1<<LS_BITS)*VALUE_BITS) / (sizeof(uint64_t)*8) ];
};

// that should be a trie, to provide faster look-up
typedef std::map< uint64_t, leaf_node > big_array_type;

void
big_array_set_value( big_array_type &b, uint64_t index, uint64_t value )
{
   leaf_node &n = b[index >> LS_BITS];
   uint64_t li = index & ((1<<LS_BITS)-1);
   li *= VALUE_BITS;   // convert into bit offset
   uint64_t &x = n.packed_data[ li / (sizeof(uint64_t)*8) ];
   li %= (sizeof(uint64_t)*8);
   x = (x & (VALUE_MASK<<li)) | (value << li);
}

int
big_array_get_value( big_array_type &b, uint64_t index, uint64_t value )
{
   leaf_node &n = b[index >> LS_BITS];
   uint64_t li = index & ((1<<LS_BITS)-1);
   li *= VALUE_BITS;   // convert into bit offset
   uint64_t &x = n.packed_data[ li / (sizeof(uint64_t)*8) ];
   li %= (sizeof(uint64_t)*8);
   return (x >> li) & VALUE_MASK;
}

この方法では、ストレージが2ビットで4つの値を使用できるため、0.5ビットの情報が無駄になりますが、使用されるのは3つだけです。これも改善できますが、アクセスパフォーマンスのコストがはるかに高くなります。

于 2010-09-12T18:21:32.197 に答える
1

値のリストは有限であるため、char配列を使用できる場合があります。1バイトは、3つの異なる値を非常に簡単に保持できます。

値：
0-> 0
1-> 1
2.2-> 2

値の保存：

char values[i];
values[i] = 0;
values[i] = 1;
values[i] = 2;  // really the 2.2 value

値の取得：

int zero = values[i] - 0;
int one  = values[i] - 0;
double two_point_two values[i] - 0;
if (two_point_two == 2)
    two_point_tow = 2.2;

最後の値を取得するには少し特別な注意が必要ですが、配列は小さくなります（1バイト）。

配列の割り当て：

int main ()
{   
    // static allocation requires a const size
    const int static_array_size = 100;
    char static_array[static_array_size];
    std::cout << "static array size is:" << sizeof(static_array) << std::endl;

    // heap allocation can vary in size (i.e. non const heap_array_size variable)
    int heap_array_size = 200;
    char* heap_array = new char[heap_array_size];
    std::cout << "static array size is:" << sizeof(heap_array_size) << std::endl;
}
于 2010-09-12T17:40:53.600 に答える
1

すべての値が255より小さいため、これをcharの配列にすることをお勧めします。いずれの場合も、ポインターのタイプは、同じものに割り当て可能な最大サイズを指示しません。

于 2010-09-12T17:32:38.160 に答える
1

しかし、私が理解している限り、この配列は、intの最大サイズの可能な最大サイズの配列を作成します。コードを変更して次のコードを使用した場合

それは絶対に間違っています！配列のサイズは、配列のタイプの最大値から完全に独立しています。

long longしたがって、配列にする必要はありません。代わりに、それをchar配列にするか、それよりも少なくする必要があります。

3つの異なる値のみを格納する必要がある場合は、acharまたはその他のタイプ内のビットで遊ぶ必要があります。次に、これらの配列を作成します。

Acharは通常1バイトなので、8ビットです。3つの値を格納するには、2ビットが必要です。したがって、に4つの値を格納できますchar。

バイナリマスクを使用して、それを最適化する方法を考え出す必要があります。

于 2010-09-12T18:13:48.980 に答える
1

配列のサイズを指定するために使用されるサイズは、タイプである必要がありますsize_t。式で使用されるnew型は、配列要素の型です。例のタイプに関係なく、配列を作成するためiに変換されます。size_t

現在、32ビットマシンでは、最大値size_tは約4e + 9であるため、サイズ1e+17の配列を作成するのは簡単です。64ビットマシンでsize_tは、理論的には約1e + 19まで上がる可能性がありますが、その量のメモリに近い場所を確保する方法がないため、割り当ては失敗します。

したがって、代わりに、他の人が議論したように、ある種のスパースデータ構造が必要です。ここで重要なのは、3つの値のどれが最も一般的であるかを判断し、配列が他の2つの値の1つである場所の値のみを格納することです。std :: mapを使用して、これらの値（[index]構文の使用もサポート）、または実行しようとしていることやデータの詳細に応じて、他のさまざまな値を保持できます。

于 2010-09-12T18:41:04.270 に答える