はじめに

業務でシステムの改修をしているときに学んだアルゴリズム的なことをメモ代わりにアウトプットします。本来はC#だったけど家にC#環境が無いのでJavaで書く。

状況

本来は配列じゃなくて配列っぽいもう少し複雑なもので中身の要素も沢山あったんだけど、まぁ簡単に言えば商品のデータ(名前とか値段とか)とその商品の在庫数を沢山持っている配列があった。

Launcher.java

ArrayList<Object[]> syohinList = new ArrayList<Object[]>();

//                   商品名   在庫数
Object[] syohin1 = {"りんご",  5};
Object[] syohin2 = {"ぶどう",  20};
Object[] syohin3 = {"みかん",  0};
Object[] syohin4 = {"キウイ",  10};
Object[] syohin5 = {"バナナ",  15};

syohinList.add(syohin1);
syohinList.add(syohin2);
syohinList.add(syohin3);
syohinList.add(syohin4);
syohinList.add(syohin5);

//商品の残在庫数を確認
for ( int i = 0; i < syohinList.size(); ++i ) {
    System.out.println(syohinList.get(i)[0] + "  残在庫:" + syohinList.get(i)[1]);
}

//出力結果
りんご  残在庫:5
ぶどう  残在庫:20
みかん  残在庫:0
キウイ  残在庫:10
バナナ  残在庫:15

それで自分の作業の中に残在庫が0の商品を配列から削除する機能を実装するというものがあった。

やったこと

無難にfor文で配列の回数分繰り返して残在庫が0だったら配列から削除するという風にコードを書いた。

Launcher.java

ArrayList<Object[]> syohinList = new ArrayList<Object[]>();

//                   商品名   在庫数
Object[] syohin1 = {"りんご",  5};
Object[] syohin2 = {"ぶどう",  20};
Object[] syohin3 = {"みかん",  0};
Object[] syohin4 = {"キウイ",  10};
Object[] syohin5 = {"バナナ",  15};

syohinList.add(syohin1);
syohinList.add(syohin2);
syohinList.add(syohin3);
syohinList.add(syohin4);
syohinList.add(syohin5);

for ( int i = 0; i < syohinList.size(); ++i ) {
    //商品の在庫が0だったら配列から削除
    if ((int)syohinList.get(i)[1] == 0) {
        syohinList.remove(i);
    }
}

//商品の残在庫数を確認
for ( int i = 0; i < syohinList.size(); ++i ) {
    System.out.println(syohinList.get(i)[0] + "  残在庫:" + syohinList.get(i)[1]);
}

//出力結果
りんご 残在庫:5
ぶどう 残在庫:20
キウイ 残在庫:10
バナナ 残在庫:15

うん、ちゃんと消えている。しかし実は問題が。

発生した問題

この方法は、0番目から要素を調べて条件に合えば(在庫が0だったら)要素から削除するというものだけど、ある条件下で削除漏れが発生する。具体的に言うと連続して削除条件を満たす要素が来たとき。

Launcher.java

ArrayList<Object[]> syohinList = new ArrayList<Object[]>();

//                   商品名   在庫数
Object[] syohin1 = {"りんご",  5};
Object[] syohin2 = {"ぶどう",  20};
Object[] syohin3 = {"みかん",  0}; //削除対象
Object[] syohin4 = {"キウイ",  0}; //削除対象
Object[] syohin5 = {"バナナ",  15};

syohinList.add(syohin1);
syohinList.add(syohin2);
syohinList.add(syohin3);
syohinList.add(syohin4);
syohinList.add(syohin5);

for ( int i = 0; i < syohinList.size(); ++i ) {
    //商品の在庫が0だったら配列から削除
    if ((int)syohinList.get(i)[1] == 0) {
        syohinList.remove(i);
    }
}

//商品の残在庫数を確認
for ( int i = 0; i < syohinList.size(); ++i ) {
    System.out.println(syohinList.get(i)[0] + "  残在庫:" + syohinList.get(i)[1]);
}

//出力結果
りんご 残在庫:5
ぶどう 残在庫:20
キウイ 残在庫:0 //何故か消えてない
バナナ 残在庫:15

みかんは消えているけどキウイが消えていない。

原因

要素が削除されることによってその後の要素が前にズレてくることが原因だった。

Launcher.java

ArrayList<Object[]> syohinList = new ArrayList<Object[]>();

//                   商品名   在庫数
Object[] syohin1 = {"りんご",  5};
Object[] syohin2 = {"ぶどう",  20};
Object[] syohin3 = {"みかん",  0}; //削除対象
Object[] syohin4 = {"キウイ",  0}; //削除対象
Object[] syohin5 = {"バナナ",  15};

syohinList.add(syohin1);
syohinList.add(syohin2);
syohinList.add(syohin3);
syohinList.add(syohin4);
syohinList.add(syohin5);

//商品の残在庫数を確認
for ( int i = 0; i < syohinList.size(); ++i ) {
    System.out.println("配列" + i + " " + syohinList.get(i)[0] + " " + "残在庫:" + syohinList.get(i)[1]);
}

System.out.println("------------------------"); //区切り線（見やすくするため）

for ( int i = 0; i < syohinList.size(); ++i ) {
    //商品の在庫が0だったら配列から削除
    if ((int)syohinList.get(i)[1] == 0) {
        syohinList.remove(i);
    }
}

//商品の残在庫数を再確認
for ( int i = 0; i < syohinList.size(); ++i ) {
    System.out.println("配列" + i + " " + syohinList.get(i)[0] + " " + "残在庫:" + syohinList.get(i)[1]);
}

//出力結果
配列0 りんご 残在庫:5
配列1 ぶどう 残在庫:20
配列2 みかん 残在庫:0
配列3 キウイ 残在庫:0
配列4 バナナ 残在庫:15
------------------------
配列0 りんご 残在庫:5
配列1 ぶどう 残在庫:20
配列2 キウイ 残在庫:0 //みかんが消えてズレた
配列3 バナナ 残在庫:15 //みかんが消えてズレた

ループごとに細かく見ていくと、

//1回目のループ：配列[0]を調べる
配列[0] りんご 残在庫:5    //残在庫0じゃないので削除しない
配列[1] ぶどう 残在庫:20   //まだ調べてない
配列[2] みかん 残在庫:0    //まだ調べてない
配列[3] キウイ 残在庫:0    //まだ調べてない
配列[4] バナナ 残在庫:15   //まだ調べてない

//2回目のループ：配列[1]を調べる
配列[0] りんご 残在庫:5    //調べた
配列[1] ぶどう 残在庫:20   //残在庫0じゃないので削除しない
配列[2] みかん 残在庫:0    //まだ調べてない
配列[3] キウイ 残在庫:0    //まだ調べてない
配列[4] バナナ 残在庫:15   //まだ調べてない

問題はここから。

//3回目のループ：配列[2]を調べる
配列[0] りんご 残在庫:5    //調べた
配列[1] ぶどう 残在庫:20   //調べた
配列[2] みかん 残在庫:0    //残在庫0なので削除する
配列[3] キウイ 残在庫:0    //まだ調べてない
配列[4] バナナ 残在庫:15   //まだ調べてない

これで配列[2]の要素が削除されて配列[3]の要素(キウイ)が配列[2]に、配列[4]の要素(バナナ)が配列[3]にズレてくる。

//3回目のループ：配列[2]を調べた
配列[0] りんご 残在庫:5    //調べた
配列[1] ぶどう 残在庫:20   //調べた
配列[2] キウイ 残在庫:0    //まだ調べてない
配列[3] バナナ 残在庫:15   //まだ調べてない

そうここです、現在の状況としては配列[2]まで調べたのですが、その配列[2]にまだ調べてない要素が入ってしまったのです。

//4回目のループ：配列[3]を調べる
配列[0] りんご 残在庫:5    //調べた
配列[1] ぶどう 残在庫:20   //調べた
配列[2] キウイ 残在庫:0    //調べてないのに結果的に飛ばされた
配列[3] バナナ 残在庫:15   //残在庫0じゃないので削除しない

ループの間で上手く抜けられた感じですね。
どうしたのものかと思っていたら、先輩にこういう時は最大値からマイナスしていって逆から調べていけば良いというアドバイスを貰った。なるほど。なんか昔授業でやったことあるような。
ただその後設計の変更で結局forは使わなくても良いことになって実装は行わなかった。しかし気になったので家で動きをちょっと考えてみた。

解決策

こんなコードを書いてみた。

Launcher.java

ArrayList<Object[]> syohinList = new ArrayList<Object[]>();

//                   商品名   在庫数
Object[] syohin1 = {"りんご",  5};
Object[] syohin2 = {"ぶどう",  20};
Object[] syohin3 = {"みかん",  0}; //削除対象
Object[] syohin4 = {"キウイ",  0}; //削除対象
Object[] syohin5 = {"バナナ",  15};

syohinList.add(syohin1);
syohinList.add(syohin2);
syohinList.add(syohin3);
syohinList.add(syohin4);
syohinList.add(syohin5);

//後ろから調べる
for ( int i = syohinList.size() - 1; i >= 0; --i ) {
    //商品の在庫が0だったら配列から削除
    if ((int)syohinList.get(i)[1] == 0) {
        syohinList.remove(i);
    }
}

//商品の残在庫数を確認
for ( int i = 0; i < syohinList.size(); ++i ) {
    System.out.println("配列" + i + " " + syohinList.get(i)[0] + " " + "残在庫:" + syohinList.get(i)[1]);
}

今までは配列の前から調べてた(昇順)けど、今度は**配列の後ろから見ていく形(降順)**にした。

配列0 りんご 残在庫:5
配列1 ぶどう 残在庫:20
配列2 バナナ 残在庫:15

うん、上手く消えているみたい。動きをまたループごとに見ていくと、

//1回目のループ：配列[4]を調べる
配列[0] りんご 残在庫:5    //まだ調べてない
配列[1] ぶどう 残在庫:20   //まだ調べてない
配列[2] みかん 残在庫:0    //まだ調べてない
配列[3] キウイ 残在庫:0    //まだ調べてない
配列[4] バナナ 残在庫:15   //残在庫0じゃないので削除しない

//2回目のループ：配列[3]を調べる
配列[0] りんご 残在庫:5    //まだ調べてない
配列[1] ぶどう 残在庫:20   //まだ調べてない
配列[2] みかん 残在庫:0    //まだ調べてない
配列[3] キウイ 残在庫:0    //残在庫0なので削除
配列[4] バナナ 残在庫:15   //調べた

配列[3]の要素(キウイ)が削除されて配列[4]の要素(バナナ)が新しく配列[3]に入れられるが降順なので問題無し。

//3回目のループ：配列[2]を調べる
配列[0] りんご 残在庫:5    //まだ調べてない
配列[1] ぶどう 残在庫:20   //まだ調べてない
配列[2] みかん 残在庫:0    //残在庫0なので削除
配列[3] バナナ 残在庫:15   //調べた

配列[2]の要素(みかん)が削除されて配列[3]の要素(バナナ)が新しく配列[2]に入れられるがもう調べてあるので問題無し。

//4回目のループ：配列[1]を調べる
配列[0] りんご 残在庫:5    //まだ調べてない
配列[1] ぶどう 残在庫:20   //残在庫0じゃないので削除しない
配列[2] バナナ 残在庫:15   //調べた

//5回目のループ：配列[0]を調べる
配列[0] りんご 残在庫:5    //残在庫0じゃないので削除しない
配列[1] ぶどう 残在庫:20   //調べた
配列[2] バナナ 残在庫:15   //調べた

こんな感じです。動作的にもオールオッケーだと思います。(多分)

おわりに

多分アルゴリズムの考え方的にはかなり基本的な所の話になると思う。なんか昔聞いたことあるような気がするし。ただ最近Rubyとかやってて便利なメソッドに頼りっぱなしだったのでこう言う考え方を鍛えるのも大切だと思いました。

参考

https://www.javadrive.jp/start/for/index2.html
http://d.hatena.ne.jp/nattou_curry_2/20090726/1248600833