質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.51%

  • Java

    13829questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

java 配列 上限解放

解決済

回答 5

投稿

  • 評価
  • クリップ 0
  • VIEW 271

keyakizaka17

score 2

解決したいこと

javaを使って全探索で問題を解くアルゴリズムを作っています。動的計画法との計算時間の比較を行いたいため非効率であることは承知の上で行っています。しかし、要素数が31個以上で全探索を解くとOutof Memory Errerが起き計算ができなくなります。

配列の上限解放について、解決できるよい方法があれば教えていただけるとありがたいです。

static final int N = 30;    // 製品数
    static final int W = 20;// 重量上限
    static int[] w = new int[N]; // 製品iの重量
    static int[] v = new int[N]; // 製品iの価値
    static int[] b = new int[N]; // 入れるか入れないかの0-1変数
    static int i = 0;
static int allCombi(int[] optimal){
        System.out.println("全組み合わせとその時の価値合計および重量合計");
//        int i = 0; // 組み合わせ番号
        for(int i = 0; i < (int)Math.pow(2.0,N); i++){
            val[i] = 0;
            wgt[i] = 0;
            for(int k = 0; k < N; k++){
                b[N - k - 1] = (i >>> k & 1) == 1 ? 1 : 0;
                // 目的関数
                val[i] += b[k]*v[k]; // val[i] = b[0]*v[0]+b[1]*v[1]+b[2]*v[2]+b[3]*v[3]+b[4]*v[4]+b[5]*v[5];
                // 重量合計
                wgt[i] += b[k]*w[k]; // wgt[i] = b[0]*w[0]+b[1]*w[1]+b[2]*w[2]+b[3]*w[3]+b[4]*w[4]+b[5]*w[5];
            }
            System.out.printf("%2d %d %d %d %d %d %d %2d %2d\n", i + 1, b[0], b[1], b[2], b[3], b[4], b[5], val[i], wgt[i]);
            if(max[0] < val[i] && wgt[i] <=W){
                max[0] = val[i];
                max[1] = wgt[i];
                max[2] = i + 1;
                for(int j = 0; j < N; j++){
                    optimal[j] = b[j];
                }
            }
        }
        System.out.println();
        return max[0];
    }
String str;
        i = 0;
        int sol;
        String[] s = {"詰めない", "詰める"}; // 解表示用文字列
        // データの読み込み
        try{
            File data = new File("C:\\Users\\fit-user\\Desktop\\data1.csv");
            BufferedReader br = new BufferedReader(new FileReader(data));
            while((str = br.readLine()) != null){
                String[] st = str.split(",", 0);
                w[i] = Integer.parseInt(st[0]);
                v[i] = Integer.parseInt(st[1]);
                System.out.printf("%2d %2d %2d\n",i, w[i], v[i]);
                i++;
            }
        }catch(FileNotFoundException e){
            System.out.println("ファイルが見つかりませんでした.");
        }catch(IOException e){
            System.out.println("入出力でエラーが発生しました");
        }
                // 全組み合わせ列挙で解く場合
        System.out.println("全組み合わせ列挙で解いた場合");
        t0 = System.nanoTime();
        sol = allCombi(optimal); // 全組み合わせ列挙メソッドの呼び出しと最適値の受け取り
        System.out.println(max[2] + "番目の組み合わせが最適解");
        // 最適解の表示
        for(int i = 0; i < N; i++){
            System.out.println("製品" + i + ":" + s[optimal[i]]);
        }
        System.out.println("最適値:" + sol);
        System.out.println("重 量:" + max[1]);
        time = System.nanoTime() - t0;
        System.out.printf("実行時間...%ntime: %f ms.%n", time/1000000.0);

 開発環境

開発環境としてはequlipseを使っています。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 5

checkベストアンサー

+4

valwgtの定義部分がないためforで回している添字からの推測なりますが、N個の要素に対する全ての組合せ数である2^N(2のN乗)個の要素からなる配列を用意しているのだと思います。31個の場合は2^31個の要素の配列、32個の場合は2^32個の要素の配列ということでしょう。

結論から言うとJavaの言語仕様とJavaVMの制限から不可能です。

まず、Javaの言語仕様として配列の添字はintであるという制限があります。intの最大値は2^31-1ですので、どうやっても0~2^31-1、つまり2^31個の要素の配列しか作れません。さらに、new int[X]とするときのXintです。ここに入る最大の数は2^31-1であり、結局、2^31-1個の配列が限界になります。

ここにJavaVMの制限が加わります。
参考: Java の配列要素数の上限 - 地平線に行く
64bit環境でも2^31-3が最大であり、それ以上は無理となります。定義部分がないため確実なことは言えませんが、Math.powで2^31を計算してもintにキャストすると2^31-1に丸め込まれますので、その大きさで配列を作ろうとしたのでしょう。しかし、上のJavaVMの制限によりOutOfMemoryErrorが発生したと考えられます。

つまり、JavaとJavaVMと配列を使う限り、どんなにメモリを積んだり、オプションでヒープサイズなどを調整しても、2^31個の要素の配列を作ることは不可能になるということです。なお、longを使えばと思うかも知れませんが、Javaの配列は添字アクセス等がintになるため、結局キャストが必要になり、意味がありません。ArrayListもintであり同じです(そもそもArrayListは内部で配列を使って実装されています)。LinkedListであれば実装上の制限がないように思えますが、size()等がintを使うため、同じと思われます(ここら辺は試してません)。

巨大な配列を作らなくても計算できるアルゴリズムに変更するしかないと思われます。または、かなり遅くなりますが、外部ファイルに配列でやろうとしていたことを入れていくという手段ぐらいしかないかと思います(intの2^31個保存するのに8GBのファイルになりますけど)。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/07/12 12:08

    わかりやすい回答をありがとうございます
    現実的には無理なのですね!
    そのことがわかってよかったです!
    回答ありがとうございました!

    キャンセル

+2

val とwgt の定義ってどこにあるんでしょうか

そもそも2の31乗個の配列ってのは何バイトになるか計算してみようよ

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+2

for(int i = 0; i < (int)Math.pow(2.0,N); i++){
このループをなんとかする必要があります。

N = 4 の場合 は i は [0, 1, ... 15] となります。配列サイズは 16 必要です。
これを [0, 1] [2, 3] ... [14, 15] と 8 つに分けて、計算すれば各処理では配列サイズは 2 で済みます。

8 つにわけるのを、1つのプログラムで 8 つに分けて処理するか、
8 つの マシンに分けて処理するか ...

あるいは、問題を [1], [2], .... [14] に完全に分けてて MessageQue にして、ひとつずつ処理していくか...

結果の総数がメモリ量を超えるようなら、DB に保存したり、なんらかのテキストファイルに書き出すようにする必要があります。

昔に書いた記事ですが、組み合わせをためしていって魔法陣を求めるのを複数マシンに分散させてみたことがある。

プログラムの自動テストでもその実行時間を縮めるために、複数 CPU / 複数マシンに処理を振分けるといった方法をとることがあります。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/07/13 07:43

    そのような方法は初めて見ました!
    ご回答ありがとうございます!!

    キャンセル

  • 2018/07/13 08:05

    "できない" といわれても鵜呑みにせずに、どんな手段をつかってでもなんとかすることを考えてみる (世の中では類似問題をどうやって解決しているのか調べる) のが良いと思います。

    キャンセル

+1

JavaVMで使用するメモリ空間の構成とJavaVMオプション

VMのメモリー量を増やせば解決しませんか?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

取り敢えずリストを使うなりすれば、ソフトウェア的には可変な配列もどきを作れます。

いうまでもないですが、ハードウェア的な限界があることは別問題です。どれだけ大きなメモリを使おうとしているか見積もりましたか?

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.51%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • Java

    13829questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。