[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が発生した時の対処法
Re: 計算量の増加で実行時errorが発生した時の対処法
64bit OS で、64 bit コンパイラを使う。
今の mac は、64bit OS で、64 bit コンパイラだから実行できたのでは ?
ただ、Windows とだけしか書かないのは、どういう事情があるのでしょうか ?
>計算量の増加による実行時Errorだと思われます。
何これ ? おかしいですよ、カテジナさん。
今の mac は、64bit OS で、64 bit コンパイラだから実行できたのでは ?
ただ、Windows とだけしか書かないのは、どういう事情があるのでしょうか ?
>計算量の増加による実行時Errorだと思われます。
何これ ? おかしいですよ、カテジナさん。
VTuber:
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。
中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。
東上☆海美☆(とうじょう・うみみ)
http://atassyu.php.xdomain.jp/vtuber/index.html
レスがついていないものを優先して、レスするみみ。時々、見当外れなレスしみみ。
中の人:
手提鞄あたッしュ、[MrAtassyu] 手提鞄屋魚有店
http://ameblo.jp/mratassyu/
Pixiv: 666303
Windows, Mac, Linux, Haiku, Raspbery Pi, Jetson Nano, 電子ブロック 持ち。
Re: 計算量の増加で実行時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など)に置いて処理を行う(スワップ)ことになり、
アクセスに時間がかかったことが考えられます。
したがって、データの量を減らすことで高速化できるかもしれません。
それでもダメなら、アルゴリズムや処理方法を見直すことで扱うデータの量を減らすべきでしょう。
例えば、動的計画法は全部の状態を保持せず、前の状態と今の状態だけを保持して処理ができる場合があります。
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など)に置いて処理を行う(スワップ)ことになり、
アクセスに時間がかかったことが考えられます。
したがって、データの量を減らすことで高速化できるかもしれません。
それでもダメなら、アルゴリズムや処理方法を見直すことで扱うデータの量を減らすべきでしょう。
例えば、動的計画法は全部の状態を保持せず、前の状態と今の状態だけを保持して処理ができる場合があります。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)
Re: 計算量の増加で実行時errorが発生した時の対処法
情報の提示は具体的にお願いします。
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
となるでしょう。
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
となるでしょう。
Re: 計算量の増加で実行時errorが発生した時の対処法
すみません。プレビューを忘れて [ i]が消えてしまうのに気づきませんでした。