C言語とC++言語コミュの配列の容量について教えてください

はじめまして。

二次元配列を使ってプログラムを書いているのですが配列の容量はどのくらいですか。

私は30万×30万の配列を作りたいのですができますか。
もしできないようでしたら限界はどのくらいか教えてください。

今はこのように書いているのですが実行してくれません。
自分で試した限界は6000くらいだった気がします。

int M = 300000;
double** W = new double*[M];
for(i=0; i<M; i++)
{
W[i] = new double[M];
}

教えてください。よろしくお願いします。

コメント(55)

最初
全て
最新の40件

前

[16] mixiユーザー 08月20日 11:52

　主記憶上で 72GiB 領域取りたいなら、いくつかの PC を LAN で連結して、という案も考えられますが、ひとケタ違うとなると、やはり HDD を使うのが現実解かと・・・。
　処理速度と学習を追求するなら、7：sock/vuela さんと同じ事を考えます。

[17] mixiユーザー 08月20日 12:22

メモリマップドファイルなんていかがでしょう？
それでも一筋縄とはいかないけど。

[18] mixiユーザー 08月20日 12:27

ごめん、Windows前提とは書かれてませんね…

[19] mixiユーザー 08月20日 13:07

行列計算だと仮定すると、Strassenのアルゴリズムを再帰的に使えばいいと思う。

[20] mixiユーザー 08月20日 15:58

ああっ、1桁間違えてた…失礼しましたm(__)m
皆さんも夏バテには気をつけましょう。
でも夏バテじゃくて間違うならその方が深刻ですね。。。

30万×30万要素の精度が必須で無いなら、要素数を見直して問題サイズを
縮小するのもアリでしょうね。やはり、計算機での実装上の課題に取り組むよりは、
計算対象のモデルの妥当性をチェックする方に注力した方がトピ主さんにとっては、
嬉しいでしょうし。

[21] mixiユーザー 08月20日 23:46

みなさん貴重な意見をありがとうございます。

参考にさせていただきます。

[22] mixiユーザー 08月21日 15:35

> PC本体買い換えを含めて50万円とか100万円コースですね。

スパコンとか言いだすような規模でもないし、個人でも手が出るね。

[23] mixiユーザー 08月21日 17:08

まあ、メモリ2TBまでは今は市販のWindowsが動くサーバーでいけます。

[24] mixiユーザー 08月21日 17:13

>23
「サーバー」という概念が無意味

[25] mixiユーザー 08月21日 17:16

製品カテゴリ上というか→サーバー
いわゆるパソコンでは、24GBぐらいが私の知ってる限りではせいぜいかなと。

[26] mixiユーザー 08月21日 19:14

こうして、Folding@homeが誕生した。

[27] mixiユーザー 08月21日 21:48

30万×30万の行列の全要素を読み書きする必要はない、と考えるなら
struct { int x; int y; }; をキーとするハッシュマップで実現できるのでは？

[28] mixiユーザー 08月22日 22:35

>25
サーバーとかワークステーションとかその他色々な用途に作られる
ハイエンドな機器があって、それらの用途の一種がサーバーだし、
例えばそれの用途がwebクローラーであるならば、それはサーバーではなくクライアント。
それらの総称をサーバーと呼ぶのは根本的にカテゴライズの方法がおかしい。
DNSならばハイエンドなスペックでなくても十分にサーバーとして稼働させられることもあるわけで、
それがどの程度サーバーらしいのかの度合いと
それがどの程度高いスペックを持っているのかの度合いは
異なる次元の問題。

[29] mixiユーザー 08月22日 23:45

例えばHPはコンピュータ製品をデスクトップ、ノートブック、ワークステーション、サーバー、ブレード、というカテゴリわけで販売しています。
メモリが192GB載る機種は、サーバーとブレードの中位機種以上。ワークステーションでは最高機種の内の1モデルだけ、デスクトップ、ノートブックではゼロ。

[30] mixiユーザー 08月23日 08:10

10:
> 別のレイヤでどう工夫しても

どの部分に何の問題があるために当該手法は採用不可能で
一方として何の方法であれば十分に問題が解決されるのだと言っているのか
それら一連が全く意味不明だな。
だいたいメモリーをファイルに仮想化させるという話で、HDの速度を直結して考えること自体おかしな話だし。

[32] mixiユーザー 08月23日 13:38

その辺は個人の感覚でしょうが・・・・。
ストレートフォワードな実装が巨大二次元配列を使うものになるようなデータ処理で、アクセスの局所性がある筈と決めつけるなんてのは、脳天気すぎる、というのが僕の感覚です。

720GBの外部記憶装置上のデータをたとえば4GBメモリで処理するなら、ちょっとやそっとの局所性ではまともな速度になりません。ワーキングセットサイズが全体の0.5％かそこらでないといけないわけですから。

30万×30万のサイズとして、
data[x][y]からみてdata[x+1][y]もdata[x][y+1]も意味的には隣ですが、単純に二次元配列をファイルにマップしたらどちらか片方はdata[x+1][y]はdata[x][y]の30万要素向うの「遠く」になるわけで。

例えば(今回の質問ではちょっと考えにくいけど)30万×30万要素の二分ヒープを作れ、なんて問題で一番上のレベルでメモリ上の配列を二分ヒープにする場合のアルゴリズムが動いていたら、下層でがんばるにも無理がある。

まぁ、当初の質問者はこれ以上情報を提供する意欲がないようなので、無益な水掛け論になっちゃいますね。
30万×30万画素の画像をJPG圧縮するなんてのが問題の実体だったら笑う。

[33] mixiユーザー 08月23日 13:58

配列の使い道を質問者がはっきりさせてくれないとこれ以上の議論ができないですね。
大規模な配列でdouble型を使うあたり精度が必要な科学計算の匂いはしますけど…

[34] mixiユーザー 08月23日 17:36

> 単純に二次元配列をファイルにマップしたらどちらか片方はdata[x+1][y]はdata[x][y]の30万要素向うの「遠く」になるわけで。

そういうのは operator[] 以下の実装問題でどうにでもなる。
こういうマッパーライブラリーを作るときは1要素単位でマップするのではなく、
OSのディスクキャッシュと同様の動きで、ある程度の大きさのブロック単位の処理となって
不要なブロックだけをスワップアウトして、
最近よく利用されているブロックはすべてメモリー上だし、
ファイルに対するアクセスもfseekはO(1)なのだから
『30万要素向うの「遠く」』であっても300万要素向こうであっても
一回の移動にかかる時間は同じ。

[36] mixiユーザー 08月23日 18:09

＞『30万要素向うの「遠く」』であっても300万要素向こうであっても
＞一回の移動にかかる時間は同じ。
理論上はね。
最近よく利用されるブロックと次に計算で使うブロックが一致しているとは限らない（というか、専用にプリフェッチャを作らない限りけっこうな頻度でキャッシュミスが発生する）から、
一回の移動にかかる時間はSSDでも使ってない限り物理的なデータの位置に左右されることになるよ。

まあ結局はoperator[]以下の実装次第なんだけれども。

[37] mixiユーザー 08月23日 18:25

> 一回の移動にかかる時間はSSDでも使ってない限り物理的なデータの位置に左右されることになるよ。

fseekの1回あたりのコストがO(1)ではなくて、それより大きなオーダーだということ?
具体的にどういうオーダー?

[38] mixiユーザー 08月23日 18:31

> 一回の移動にかかる時間はSSDでも使ってない限り物理的なデータの位置に左右されることになるよ。

そもそもファイルより向こう側の都合は、この問題の本質ではない。
fuse介してfsを用意して、その実体はネットワークを介して分散された他のホストの主記憶を利用してもいいわけ。
特定デバイスのみの弱点を提示して、それ特有の問題点を理由に
ファイルにマップされる仮想配列というコンテナークラスの弱点だと認識するのはそもそもの考え方がおかしい。

[39] mixiユーザー 08月23日 19:25

fseekのコストはO(1)ですしその手のコンテナクラスの弱点とも言ってませんよ。
そもそもデータがローカルの主記憶に収まりきらない（かどうかは質問者に聞かないと分からないですが収まらない場合が多いでしょうからそう仮定しています）時点でオーダーの考えは実用的では無いというだけ。
高々数十μ秒のコンテナクラスやらfseekやらにかかる時間と、種類によってμ秒単位だったりミリ秒単位だったりするデバイスのどちらを考えるほうが実用的かは明らかだと思いますよ。

[40] mixiユーザー 08月23日 22:46

> オーダーの考えは実用的では無いというだけ。

オーダーの考え方が実用的かどうかはどうでもいいし、
実用的に関する話なんかどこにもでてきてないはずだが。

[41] mixiユーザー 08月23日 23:38

すみません

プログラムの知識がなさすぎて皆さんの話ついていけてません

僕はただ配列でどのくらいの規模ができるか知りたかっただけですので

[43] mixiユーザー 08月24日 00:02

ううむ、プログラムを実際に作る立場だと非常識に思える「30万×30万のdouble型の配列」ということでどんな素敵なことをやるのかと思っちゃいました。

32bitのwindowsだとユーザエリアが2GBでしたから (2GB/8)^0.5 = 15811.388
他の変数がなくて、プログラムが小くて、同時に動いている他のプログラムがなければ 15000×15000 くらいの配列が取れそうですね。
(コンパイルオプションの設定もチューニング必要ですよ)

[44] mixiユーザー 08月24日 00:14

> デカイ配列を使うなら…
> mallocとかで動的にメモリを確保したほうが良いかも知れません

主記憶を越えるmallocなんて発想が駄目すぎるだろう。

[45] mixiユーザー 08月24日 00:14

昔、俺が通っていた大学には768GBのメモリを載せた計算用サーバがあったので
そんな計算をしたい場合、そのような施設を借りる方法を考えた方が良いかと。

環境にもよりますが、
経験的にはWindowsの32bit環境でnewで安全に取れるサイズは200MB程度かと。
いろいろなソフトが動いている中で、連続したメモリアドレスを取るのは難しいね。

WindowsXP-64bitで物理メモリを4GB積んで、
30MB×68個=約2GBを確保したことあるけど、一般PCではこのくらいが限界かなー

X58チップセットで豪華なPCを組めば、物理メモリ24GB載せて、OSを64bitにすれば、そのうち20GB位は確保できそうですが、そんな環境限定のソフトなんて誰が使うのか･･･

[46] mixiユーザー 08月24日 00:47

> 32bitのwindowsだとユーザエリアが2GBでしたから (2GB/8)^0.5 = 15811.388

配列が仮想化されていれば、32bitでもそんな制約に縛られた設計をする必要なし。
operator[]の引数を64bitにするか、
一つ目のoperator[]のreturnがproxyになるだけでいい。
処理系やOSが64bitアドレッシングに対応していなくても
あたかもそれに対応しているかのような姿で
アプリケーションが巨大配列を利用することは簡単。
その環境下で数百GBの巨大配列に接触可能な状況を用意して
その内数GBしか使わないような疎行列を処理すれば、
時間資源と空間資源に対する負荷は仮想的に用意された巨大配列の大きさの影響を受けず
保存した要素の個数にだけ影響を受ける。
そうしておけば、仮想的に用意されようとしている巨大配列の大きさについての制限はとても緩く、
また保存される要素数の理論上の制限は存在せず、増やせば負荷が増えるだけということになる。

実際に保存される要素の量が結局のところ主記憶内に用意に納まる程度に小さいような疎行列であるならば
ファイルにいつでもスワップできる準備ができていても現実にはスワップされないために
時間資源への負担が少なく、
主記憶から溢れるような規模になったとしても、必要に応じて必要なだけのスワップ処理をすることで
時間資源の負担を増やすことと引き替えに理論上は正しく動作を続行できる。
こういう戦略についてsaitohさんはわけのわからない物言いを付けているようだが
そこから発生する戦略特有の問題は何になるのか
そしてそれを解決させる他の方法に何になるのか
についての話が全く出てきやしないので、
現時点で主記憶を越えるような規模の巨大配列を使う方法として
十分にパフォーマンスを発揮し、かつ制約の少ない、総合的に無難な戦略になるだろう。
もっと良い戦略を出してくれる人がいたらとてもありがたいんだけどね。

[48] mixiユーザー 08月24日 03:05

トピ主さんは具体的に何かがしたいわけではなく、どの程度巨大な配列がアロケートできるかが知りたかったってことではないでしょうか
そんなに不思議な疑問（興味）でも無いように感じます。

先日長野の一般の方が円周率５兆桁を計算したニュースが流れましたが、使用されたPCはデュアルCPUマザーの12slotに8Gで96GBだったようです。現時点で個人で手が届くのはここら辺が限界でしょうか。ただメモリーの大容量化の速度は速く、720G位なら買ってくればいいなんていう時代も案外もうすぐだったりして

[49] mixiユーザー 08月24日 08:39

>44
言葉不足でしたね。
「配列サイズを30万じゃなくて、動作可能なサイズに減らした上で動かすとしたら」という前提を書いてなかった。

問題の特性もまったく明らかになってないのに、、なんで「そんなの実装次第でどうにでもなる」と言い切れるのが不思議。
仮想記憶だって、仮想空間使用量：実メモリ割当量は１０：１あたりがいいところで、ものによっては１：２くらいでスラッシングが起きたりする。
もちろん逆に、巨大なデータをそこそこのメモリで処理して破綻しない事例もあるのは知ってます。

ま。正体不明なモノに甘い見積もりはしないという僕が悲観的すぎるのか。

[50] mixiユーザー 08月24日 09:09

とりあえず主さんの環境は300MB弱は動的確保できるんだなぁとか書いとく。

[51] mixiユーザー 08月24日 09:21

> 問題の特性もまったく明らかになってないのに、、なんで「そんなの実装次第でどうにでもなる」と言い切れるのが不思議。

OSの仮想メモリーの設計も、仮想配列コンテナーの設計も、
ある特定の問題の特性を明らかにした上でそれに依存して作られる性質ではないのだがな。
理論上は主記憶のサイズによる制限がなくて、正しく処理可能で、資源が十分ならばパフォーマンスも実用的で、
後は要求の量と資源の量のバランスの問題というところまで持っていけば、
そちら側の問題を解決するだけで結果が出る。
saitohさんがOSを作ろうとしたら、どういう使われ方をするか分からないってことで
いつまでたっても仮想メモリーは設計しないことになるな。

[52] mixiユーザー 08月24日 09:25

> 単純に二次元配列をファイルにマップしたらどちらか片方はdata[x+1][y]はdata[x][y]の30万要素向うの「遠く」になるわけで。

一番の問題は、この『30万要素向うの「遠く」』ってところだ。
その「遠く」ってところに何の問題があるのかが不明すぎる。
遠さについて負荷がO(n)になるとでも言いたいかのような表現なのだが
それについてもっと詳細を書かれないと意味不明すぎ。

[53] mixiユーザー 08月24日 10:06

30万×30万じゃなくてたとえば4096×4096とかなら結構大きな問題はあるかも
ヒント：CPUのキャッシュライン

ログインすると、残り21件のコメントが見れるよ