計算量の増加で実行時errorが発生した時の対処法

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
Prai

計算量の増加で実行時errorが発生した時の対処法

#1

投稿記事 by Prai » 11ヶ月前

[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だと実行できました(かなり遅いですが,,,)

Prai

Re: 計算量の増加で実行時errorが発生した時の対処法

#2

投稿記事 by Prai » 11ヶ月前

Error内容

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

アバター
あたっしゅ
記事: 258
登録日時: 9年前
住所: 東京23区
連絡を取る:

Re: 計算量の増加で実行時errorが発生した時の対処法

#3

投稿記事 by あたっしゅ » 11ヶ月前

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

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


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

何これ ? おかしいですよ、カテジナさん。
手提鞄あたっしゅ、[MrAtassyu] http://ameblo.jp/mratassyu/
手提鞄屋魚有店(てさげかばんやうおありてん)
レスがついていないものを優先して、レスしています。時々、見当外れなレスをします。

Prai

Re: 計算量の増加で実行時errorが発生した時の対処法

#4

投稿記事 by Prai » 11ヶ月前

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

アバター
みけCAT
記事: 6235
登録日時: 9年前
住所: 千葉県
連絡を取る:

Re: 計算量の増加で実行時errorが発生した時の対処法

#5

投稿記事 by みけCAT » 11ヶ月前

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など)に置いて処理を行う(スワップ)ことになり、
アクセスに時間がかかったことが考えられます。
したがって、データの量を減らすことで高速化できるかもしれません。

それでもダメなら、アルゴリズムや処理方法を見直すことで扱うデータの量を減らすべきでしょう。
例えば、動的計画法は全部の状態を保持せず、前の状態と今の状態だけを保持して処理ができる場合があります。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

Prai

Re: 計算量の増加で実行時errorが発生した時の対処法

#6

投稿記事 by Prai » 11ヶ月前

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

かずま

Re: 計算量の増加で実行時errorが発生した時の対処法

#7

投稿記事 by かずま » 11ヶ月前

情報の提示は具体的にお願いします。
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が発生した時の対処法

#8

投稿記事 by かずま » 11ヶ月前

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

コード:

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

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

返信

“C言語何でも質問掲示板” へ戻る