webdevqa.jp.net

C ++に最大配列長の制限はありますか?

C++の配列に最大長はありますか?

それはC++の制限ですか、それとも私のマシンに依存しますか?調整可能ですか?配列の作成タイプに依存しますか?

どういうわけかその制限を破ることができますか、または情報を保存するより良い方法を検索する必要がありますか?そして、最も簡単な方法は何ですか?

私がしなければならないことは、配列にlong long intを保存することです。私はLinux環境で作業しています。私の質問は次のとおりです。N> 10桁のN個のlong long整数の配列を格納する必要がある場合はどうすればよいですか。

これが必要なのは、学校用の暗号化アルゴリズム(p-Pollardなど)を作成しており、整数の壁と配列表現の長さの壁にぶつかるからです。

161
luiss

2つの制限があり、どちらもC++ではなくハードウェアによって強制されます。

最初の制限(決して到達することはできません)は、配列内のインデックス(およびそのサイズ)を記述するために使用されるサイズタイプの制限によって設定されます。システムのstd::size_tが取りうる最大値によって与えられます。このデータ型は常にシステムの最大整数型でなければなりません。

もう1つの制限は、物理メモリの制限です。配列内のオブジェクトが大きいほど、メモリがいっぱいであるため、この制限に早く到達します。たとえば、特定のサイズのvector<int>nは、通常、タイプvector<char>の配列の約4倍のメモリ(小さな定数値を引いたもの)を使用します。したがって、vector<char>には、メモリがいっぱいになる前にvector<int>よりも多くの項目が含まれる場合があります。ネイティブCスタイルの配列int[]およびchar[]についても同じカウントです。

また、allocatorはメモリを自由に管理できるため、この上限はvectorの構築に使用されるallocatorのタイプの影響を受ける場合があります。非常に奇妙ですが、それでも考えられないアロケーターは、オブジェクトの同一インスタンスがリソースを共有するような方法でメモリをプールできます。この方法では、多くの同一のオブジェクトをコンテナに挿入できます。そうしないと、利用可能なメモリをすべて使い果たしてしまいます。

それとは別に、C++は制限を強制しません。

154
Konrad Rudolph

誰もサイズの制限について言及していません スタックフレーム

メモリを割り当てることができる場所は2つあります。

  • ヒープ上(動的に割り当てられたメモリ)。
    ここでのサイズ制限は、使用可能なハードウェアと、未使用のデータを一時的に保存するために他のデバイスを使用してスペースをシミュレートするOSの機能の組み合わせです(つまり. ページをハードディスクに移動します)。
  • スタック上(ローカルで宣言された変数)。
    ここでのサイズ制限は、コンパイラで定義されています(ハードウェアの制限がある場合があります)。コンパイラのドキュメントを読むと、このサイズを微調整できます。

したがって、配列を動的に割り当てる場合(制限は大きく、他の投稿で詳細に説明されます。

int* a1 = new int[SIZE];  // SIZE limited only by OS/Hardware

または、配列がスタックに割り当てられている場合、スタックフレームのサイズによって制限されます。 N.B. ベクトルやその他のコンテナはスタック内にわずかに存在しますが、通常、データの大部分はヒープ上にあります。

int a2[SIZE]; // SIZE limited by COMPILER to the size of the stack frame
155
Martin York

理論的な観点ではなく実用的な観点から見ると、32ビットWindowsシステムでは、1つのプロセスで利用可能なメモリの最大合計量は2 GBです。より多くの物理メモリを備えた64ビットオペレーティングシステムに移行することで制限を破ることができますが、これを行うか、代替を探すかは、対象ユーザーとその予算に大きく依存します。 PAE を使用して拡張することもできます。

多くのコンパイラのデフォルトの構造アライメントは8バイトであるため、配列のタイプは非常に重要です。これは、メモリ使用量が問題になる場合は非常に無駄です。 Visual C++を使用してWindowsをターゲットにしている場合、これを克服する方法として #pragma pack ディレクティブを確認してください。

もう1つのことは、スパース行列、オンザフライ圧縮など、メモリ圧縮技術で何が役立つかを調べることです。これもアプリケーションに大きく依存します。投稿を編集して、実際に配列に含まれているものについてさらに情報を提供すると、より有用な回答が得られる場合があります。

編集:正確な要件に関するもう少しの情報を考えると、ストレージのニーズは7.6 GBから76 GBの非圧縮であるように見えます。これには、C++のメモリに配列として保存するためにかなり高価な64ビットボックスが必要になります。アクセス速度を想定し、ランダムアクセスを許可するメモリにデータを保存する理由を疑問視する。このデータを配列の外部に保存する最良の方法は、アクセス方法にほぼ基づいています。配列メンバーにランダムにアクセスする必要がある場合、ほとんどのアプリケーションでは、同時にアクセスされる傾向があるデータの塊をグループ化する方法があります。たとえば、大規模なGISおよび空間データベースでは、データは多くの場合、地理的エリアごとに並べられます。 C++プログラミング用語では、[]配列演算子をオーバーライドして、必要に応じて外部ストレージからデータの一部をフェッチできます。

13
SmacL

回答を要約して拡張し、質問に直接回答するには:

いいえ、C++は配列のdimensionsに制限を課しません。

しかし、アレイはメモリのどこかに保存する必要があるため、コンピュータシステムの他の部分によって課されるメモリ関連の制限が適用されます。これらの制限は、配列のdimensions(=要素の数)に直接関係するのではなく、むしろsize(=使用されるメモリの量)に関係することに注意してください。配列の次元(D)とメモリ内サイズ(S)は同じではありません。単一の要素( E):S= D * E

Now Eは以下に依存します:

  • 配列要素のタイプ(要素は小さくも大きくもできます)
  • メモリアライメント(パフォーマンスを向上させるために、要素はある値の倍数であるアドレスに配置されます。
    要素間の「無駄なスペース」(パディング)
  • オブジェクトの静的部分のサイズ(オブジェクト指向プログラミングでは、同じタイプのオブジェクトの静的コンポーネントは、そのような同じタイプのオブジェクトの数に関係なく、一度だけ保存されます)

また、スタック(自動変数:int t[N])またはヒープ(malloc()/newを使用した動的な割り当て、またはSTLメカニズムの使用)、またはプロセスの静的な部分に配列データを割り当てることにより、通常、さまざまなメモリ関連の制限が発生することに注意してくださいメモリ(静的変数:static int t[N])。ヒープに割り当てる場合でも、ヒープに割り当てられたメモリブロックへの参照を格納するために、スタック上に少しのメモリが必要です(ただし、これは通常無視できます)。

size_t型のサイズはプログラマーに影響を与えません(プログラマーはインデックス用にsize_t型を使用することを想定しています)。コンパイラプロバイダーは、typedefを最大に対応できる十分な整数型にする必要があるためです。特定のプラットフォームアーキテクチャで使用可能なメモリ量。

メモリサイズの制限の原因は

  • プロセスで使用可能なメモリ量(32ビットアプリケーションの場合は64ビットOSカーネルでも2 ^ 32バイトに制限されます)、
  • プロセスメモリの分割(例:スタックまたはヒープ用に設計されたプロセスメモリの量)、
  • 物理メモリの断片化(散在する小さな空きメモリフラグメントの多くは、1つのモノリシック構造の格納には適用されません)、
  • 物理メモリの量、
  • および仮想メモリの量。

アプリケーションレベルで「微調整」することはできませんが、別のコンパイラを使用したり(スタックサイズの制限を変更したり)、アプリケーションを64ビットに移植したり、別のOSに移植したり、物理/ (仮想?物理?)マシンの仮想メモリ構成。

上記のすべての要因を外部障害として、したがって実行時エラーの原因として扱い、プログラムコード内のメモリ割り当て関連エラーを慎重にチェックして対応することは珍しくありません(推奨されません)。

最後に:C++は制限を課していませんが、コードを実行する際にメモリに関連する不利な条件をチェックする必要があります...:-)

4
Artur Opalinski

上記に同意します。配列を初期化する場合

 int myArray[SIZE] 

sIZEは整数のサイズによって制限されます。ただし、mallocがNULLを返さない限り、メモリのチャンクをいつでもmallocしてポインタを保持できます。

4
Tarski

多くの優れた回答が指摘したように、C++コンパイラのバージョン、オペレーティングシステム、およびコンピューターの特性に依存する多くの制限があります。ただし、Pythonには、マシンの制限をチェックする次のスクリプトをお勧めします。

バイナリ検索を使用し、各反復で、サイズの配列を作成しようとするコードを作成して中間サイズが可能かどうかをチェックします。スクリプトはそれをコンパイルし(申し訳ありませんが、この部分はLinuxでのみ動作します)、成功に応じてバイナリ検索を調整しようとします。見てみな:

import os

cpp_source = 'int a[{}]; int main() {{ return 0; }}'

def check_if_array_size_compiles(size):
        #  Write to file 1.cpp
        f = open(name='1.cpp', mode='w')
        f.write(cpp_source.format(m))
        f.close()
        #  Attempt to compile
        os.system('g++ 1.cpp 2> errors')
        #  Read the errors files
        errors = open('errors', 'r').read()
        #  Return if there is no errors
        return len(errors) == 0

#  Make a binary search. Try to create array with size m and
#  adjust the r and l border depending on wheather we succeeded
#  or not
l = 0
r = 10 ** 50
while r - l > 1:
        m = (r + l) // 2
        if check_if_array_size_compiles(m):
                l = m
        else:
                r = m

answer = l + check_if_array_size_compiles(r)
print '{} is the maximum avaliable length'.format(answer)

マシンに保存して起動すると、作成可能な最大サイズが印刷されます。私のマシンでは2305843009213693951です。

3
Dmitry Torba

前の回答で言及されていないと思うことの1つ。

人々がデザインでそのようなものを使用しているとき、私は常にリファクタリングの意味で「悪臭」を感じています。

これは巨大な配列であり、効率の観点とパフォーマンスの観点の両方からデータを表現する最良の方法ではない可能性があります。

乾杯、

ロブ

2
Rob Wells

大きなデータを処理する必要がある場合は、管理可能なチャンクに分割する必要があります。すべての小型コンピューターのメモリに収まるわけではありません。ディスクのデータの一部(合理的に収まる範囲)をロードし、計算と変更を実行してディスクに保存し、完了するまで繰り返します。

2
Jay

現在のすべての答えがそうであるように、迷惑なほど非特異的であるため、それらはほとんど正しいですが、多くの警告があり、常に言及されているわけではありません。要点は、2つの上限があり、そのうちの1つだけが実際に定義されているものなので、 YMMV

1.コンパイル時の制限

基本的に、コンパイラが許可するもの。 x64 Windows 10ボックス上のVisual C++ 2017の場合、これは2GBの制限が発生する前のコンパイル時の最大制限です。

unsigned __int64 max_ints[255999996]{0};

代わりにこれを行った場合、

unsigned __int64 max_ints[255999997]{0};

私が得るだろう:

Error C1126 automatic allocation exceeds 2G

2Gが255999996/7とどのように相関するかはわかりません。私は両方の数字をグーグルで検索しましたが、関連する可能性のあるものは、 dcの精度の問題 に関するこの* nix Q&Aだけでした。いずれにせよ、どのタイプのint配列を埋めようとしているかは問題ではなく、割り当て可能な要素の数だけです。

2.実行時の制限

スタックとヒープには独自の制限があります。これらの制限は、利用可能なシステムリソースに基づいて変化する値と、アプリ自体の「重さ」の両方の値です。たとえば、現在のシステムリソースでは、これを実行できます。

int main()
{
    int max_ints[257400]{ 0 };
    return 0;
}

しかし、少し微調整すれば...

int main()
{
    int max_ints[257500]{ 0 };
    return 0;
}

バム!スタックオーバーフロー!

Exception thrown at 0x00007FF7DC6B1B38 in memchk.exe: 0xC00000FD:Stack overflow (parameters: 0x0000000000000001, 0x000000AA8DE03000).Unhandled exception at 0x00007FF7DC6B1B38 in memchk.exe: 0xC00000FD:Stack overflow (parameters: 0x0000000000000001, 0x000000AA8DE03000).

そして、アプリポイントの全体の重みを詳細に説明するために、これは良かったです。

int main()
{
    int maxish_ints[257000]{ 0 };
    int more_ints[400]{ 0 };
    return 0;
}  

しかし、これによりスタックオーバーフローが発生しました。

int main()
{
    int maxish_ints[257000]{ 0 };
    int more_ints[500]{ 0 };
    return 0;
}  
1

2D動的配列を作成することでこれを回避します。

long long** a = new long long*[x];
for (unsigned i = 0; i < x; i++) a[i] = new long long[y];

詳細はこちら https://stackoverflow.com/a/936702/3517001

0
Three

すでに指摘したように、アレイのサイズはハードウェアとOSによって制限されます(man ulimit)。しかし、あなたのソフトウェアはあなたの創造性によってのみ制限されるかもしれません。たとえば、「配列」をディスクに保存できますか?本当に長い長い整数が必要ですか?本当に密な配列が必要ですか?配列さえ必要ですか?

1つの簡単な解決策は、64ビットLinuxを使用することです。アレイに物理的に十分なRAMがない場合でも、プロセスで使用可能な仮想メモリは物理メモリよりもはるかに大きいため、OSはメモリを割り当てることができます。本当にアレイ内のすべてにアクセスする必要がある場合、ディスクに保存することになります。アクセスパターンに応じて、これを実行するより効率的な方法があります(つまり、mmap()を使用するか、ファイルにデータを順番に格納するだけです(この場合、32ビットLinuxで十分です)。

0
ejgottl