各言語において扱える配列の大きさについて

Question

配列におさめる数を比較的小さな数とした場合、
各言語（例、C, C++, Python, Ruby, Haskell 等）において扱える配列の大きさはどれくらいでしょうか？

また、もしそれ以上の大きさの配列が必要な計算が出てきた場合
どう対処すればよろしいでしょうか？

Answer 1

###Ruby

Ruby(2.4.0, macOS 10.12.2, 64bit)でArray.new(サイズ)をpry上で試して見ました。

• 2**63 〜 : Cでのlongに変換できないというエラー
• 2**60 〜 2**63-1 : サイズが大きすぎるというエラー
• 2**43ぐらい 〜 2**60-1 : メモリ確保失敗でエラー
• 2**32ぐらい 〜 2**43ぐらい : 作ろうとするが50GiBぐらいメモリをとったぐらいで落ちた(pryで試したから？)
• 0 〜 2**32ぐらい : できる、しかし、2**32だと32GiBとかあり得ないぐらいメモリが消費される。重いけど、一応動くようだ。

言語仕様上は特に制限が無いためシステムが許す限り無限大と思われます。Cでの実装上の限界としてlong(macOS 64bitでは64bitになる)が収まる2**63-1があるようですが、実際は2**60-1以下に制限されているようです。さらに、それが収まるだけのメモリが必要です。メモリさえ収まればいくらでもいけますが、1要素あたり8バイト必要なようですので、2**60-1を収めるには、8EiB(エクスビバイト)が認識できるシステムが必要でしょう。RHEL7ですら理論上はメモリの最大が64TiBのため、2**43が限界になると思われます。

###C

たしか、配列の添字がintに制限されていたはずです(ちょっと曖昧、C11のドラフトをさらっと見たけど、見つけられなかった)。現在のほとんどのシステムではintは32bitのため、最大値が2^31-1になりますが、Cの規格上はintは16bit以上であればいくらでも大きくてもいいので、システムによってはより大きい値を扱えるかも知れません。

###ECMAScript

言語仕様として、Arrayのlengthプロパティが2^32未満(2^32-1以下)という制約があります。実際は、動作する環境のメモリ次第と思われます。

参考: ECMAScript® 2016 Language Specification#9.4.2Array Exotic Objects

Answer 2

以前c言語とGo言語で巨大な配列のソートを比較した際に、メモリについてもわかったことがあったので。

C言語

例えばc言語をwindows上で動かそうとすると(bcc)、int型(32bit)の配列が25万強でスタックオーバーフローになりプログラムが強制終了します。
c言語をlinux上で動かすと(gcc)、250万件ほどです。
OSないしコンパイラによって差が出るみたいですね。

解決策として、malloc()という関数でヒープ領域を確保することが挙げられます。(free()での開放を忘れずに)

Go言語等

スタックオーバーフローは自動的にヒープ領域を確保しない言語だから起こることで、Goなどの高水準な言語はint型(64bit)が1億件だろうとメモリの確保を意識せず動作します。(メモリに余裕があれば)

また、ガベージコレクションに対応していればc言語のfree()のような開放をする必要が無くなります。

つまり、高水準な言語では基本的に確保も開放も自動なので、極端にいえば「自分のPCの空きメモリサイズ=確保できる配列サイズ」だと考えてもいいでしょう。

しかし、ヒープ領域はわざわざメモリが空いていることを確認して確保しにいくのでスタック領域よりも低速であることに気をつけてください。

Answer 3

・扱える配列の大きさはどれくらい・・・扱う言語のインデックスが６４ビットまで使えて、（スワップ等）メモリ管理が出来れば搭載されているHDDの空き容量が限界と思います。
・それ以上の大きさの配列が必要な・・・上記以外に可決策はないと思います
蛇足・・・６４ビットは18446744073709551615 or 9223372036854775807です。
もしint=4byteなら36,893,488,147,419,103,228byte・・・HDD増設でも無理かorz
昔エラトステネスの篩を作ったときintで２０億ぐらは行けましたｗ（FreeBSD clang メモリ８GB）
[加筆]
もし、出現する数値に偏り（同じ数値が連続するなど）があるなら圧縮すればもっと入ると思います。
e.g.
1,2,3,3,3,4,5,5,5,5,6・・・
[1,1][1,2][3,3][1,4][4,5][1,6]など

Answer 4

各言語において扱える配列の大きさはどれくらい

言語といってもたくさんありますし環境によって違う場合もあるかと思います。特定の言語の仕様を知りたければ言語仕様を学ぶべきではないでしょうか。それはともかく指標の順番に連続領域に確保されるようなタイプの配列と仮定すると指標となる整数が30bit前後ならば多くの言語で(言語仕様上は)扱えそうな印象です。ただ性能的に搭載したメモリーの制約を受けるでしょうから多くの場合ずっと小さなサイズとして設計するのが適切と思います。

それ以上の大きさの配列が必要な計算

これは「単純な配列ではなくアプリケーションの要求に応じた別の構造を用いる」としか言えないと思います。大きなサイズの配列を扱わなければならない応用として思い浮かぶのは例えば「疎な配列」ですが、そうした場合特別な配列(SparsArrayなどと呼ぶと思います)を用いるかも知れません。要素の充填率が高い配列ならば疎な配列は使えないのでアクセスの局所性に配慮して配列の代替構造やアルゴリズムを考えることになるでしょう。

ご質問の内容は少々漠然としていると思います。この質問の意図に何か背景があるならもっと具体的に質問したほうがいいかも知れません。