プログラマ専用SNS ミクプラ

[1] 質問文
初心者です、よろしくお願いします。
私は現在4次元配列を用いたプログラム(int flag[N][N][N][N])を作成しています。
そこでNの値を大きくしていくことで問題が発生しました。
Nの値が16,32,64,128までは段々と処理が重くなりますが動作しました。
しかし、Nの値を256にした時に実行時Errorが発生しました。(はじめにコンパイルError(サイズが大きすぎます)が発生しましたが、mallocを使うことで解消しました。(int ****flagとした))

　[1.1] 自分が今行いたい事は何か
Nの値が256の場合でも動作するようにしたい。(可能であるなら高速化まで,,,)

　[1.2] どのように取り組んだか(プログラムコードがある場合記載)
必要であれば後程記載します。

　[1.3] どのようなエラーやトラブルで困っているか(エラーメッセージが解る場合は記載)
計算量の増加による実行時Errorだと思われます。

　[1.4] 今何がわからないのか、知りたいのか
Nの値が256の時に動作するための解決策または改善策。

[2] 環境 　
　[2.1] OS ： Windows,
　[2.2] コンパイラ名 ： gcc

[3] その他
　WindowsだとNの値が256では実行時Errorが発生しましたが,Macだと実行できました(かなり遅いですが,,,)

Error内容

クラッシュプロセスにアタッチできません。
このコマンドを実行するための十分な記憶域がありません。

64bit OS で、64 bit コンパイラを使う。

今の mac は、64bit OS で、64 bit コンパイラだから実行できたのでは ?
ただ、Windows とだけしか書かないのは、どういう事情があるのでしょうか ?


＞計算量の増加による実行時Errorだと思われます。

何これ ? おかしいですよ、カテジナさん。

回答ありがとうございます、やってみます

int flag[N][N][N][N]は、Nの4乗個のintを確保します。
intが4バイトでN=256の場合、これは16GBになります。
そのプログラムで何をやっているかがわかりませんが、
処理内容によっては1要素のサイズを必要最低限まで減らすことで、メモリの使用量を減らすことができます。
例えばintからcharにすることで、扱える値の範囲が-128～127または0～255になる代わりに、
合計サイズを4GBに減らせます。 (もしかしたら環境によっては違うかもしれません)
さらに1要素あたり1ビットに(unsigned char flag[N][N][N][N / 8])することができれば、
合計サイズを512MBに減らせます。

重くなった原因として、主記憶(RAM)に入り切らない大量のデータを扱ったため、
データを主記憶より遅いディスク(HDDやSSDなど)に置いて処理を行う(スワップ)ことになり、
アクセスに時間がかかったことが考えられます。
したがって、データの量を減らすことで高速化できるかもしれません。

それでもダメなら、アルゴリズムや処理方法を見直すことで扱うデータの量を減らすべきでしょう。
例えば、動的計画法は全部の状態を保持せず、前の状態と今の状態だけを保持して処理ができる場合があります。

回答ありがとうございます、参考になります。

情報の提示は具体的にお願いします。
flag[j][k][m] にはどういう値が入るのですか？
0～255 それとも 0～1 ?

もし、0～1 なら、char flag[N][N][N][N>>3]; で、
flag[j][k][m] = 1 は、flag[j][k][m>>3] |= 1<<(m&7)、
flag[j][k][m] = 0 は、flag[j][k][m>>3] &= ~(1<<(m&7))、
flag[j][k][m] の参照は、flag[j][k][m>>3]>>(m&7) & 1
となるでしょう。

すみません。プレビューを忘れて [ i]が消えてしまうのに気づきませんでした。