トップ > 重複チェックのアルゴリズム（２重ループ）

重複チェックのアルゴリズム（２重ループ）

仕事をしていると、相互チェック（重複エラーチェック）を実装することがある。しかし、アルゴリズムを考えるのが苦手だ。ここにメモとして残しておきたい。

 

画面イメージ

一覧形式の入力項目にエラーチェックを実装しようとする。

製品入庫登録

　

 

No.製品番号数量
1
2
3
4
5

 

仕様

①登録ボタンを押下後、製品番号が重複している場合、エラーを表示する。

 

エラーを画面上部に表示する場合

重複データを単純に知らせたい場合、画面の上部もしくはJavaScriptのalertでポップアップエラーを表示することがある。

製品入庫登録

　

 

No.製品番号数量
1
2
3
4
5

ソース

ボタンを押した時に呼び出される関数は、下記に記載。

  1. function buttonfunction1() {
  2.     var ary = new Array(5);
  3.     ary[0] = document.getElementById('seiban1_1').value;
  4.     ary[1] = document.getElementById('seiban1_2').value;
  5.     ary[2] = document.getElementById('seiban1_3').value;
  6.     ary[3] = document.getElementById('seiban1_4').value;
  7.     ary[4] = document.getElementById('seiban1_5').value;
  8.    
  9.     var count = 0;
  10.     var errorFlg = false;
  11.    
  12.     for (i = 0; i < 5; i++) {
  13.         if (ary[i] == "") {
  14.             count++;
  15.             continue;
  16.         }
  17.         for (j = 0; j < 5; j++) {
  18.             if (i == j) {
  19.                 continue;
  20.             }
  21.             if (ary[i] == ary[j]) {
  22.                 errorFlg = true;
  23.             }
  24.         }
  25.     }
  26.     if (count == 5) {
  27.         document.getElementById('msg1').innerHTML = "<font color='red'>登録データがありません。</font>";
  28.         return;
  29.     }
  30.     if (errorFlg) {
  31.         document.getElementById('msg1').innerHTML = "<font color='red'>製品番号が重複しています。</font>";
  32.     } else {
  33.         document.getElementById('msg1').innerHTML = "登録しました。";
  34.     }
  35. }

解説

大きな処理は３つ。

配列・変数の定義、重複判定処理、メッセージ・エラー表示。

これに付け加えて重複判定ではForの入れ子で実装している。

  1. 2～7行目　入力項目を配列にセット。
  2. 9行目　全てが空行か判定する変数（※１）
  3. 10行目　重複行があるか判定する変数（※２）
  4. 11行目　For文　全行判定します。
  5. 12～16行目　空行の場合、次の行に移る。空行判定変数（※１）にインクリメント。
  6. 17行目　For文　現在行との重複行を全行判定します。
  7. 18～20行目　自行の場合は、次の行に移る。
  8. 21～23行目　値が同じ場合、重複エラー変数（※２）をtrue。
  9. 26～29行目　空行判定変数（※１）が全行の場合、エラーを表示。処理終了。
  10. 31行目　重複エラー変数（※２）がtrueの場合、エラーを表示。
  11. 33行目　そうでない場合、登録成功。

今回は、全行が空行か判定を重複判定処理に組み込んでしまったが、これは重複判定処理の前に実装しておいたほうがいい。 だって、入力行数が100行になったら、100×100=10,000回施行してしまう。

というわけでこれを改善していこう。

問題はなんだったのか？

上記のソースの問題は、行数がn行あると、試行回数がn2になってしまう。この考え方を計算量オーダーとか言ったりするが、これはまたの話。

さて、このことから重複計算処理になにかしらの手を加えなければならない。

ここで、机上デバッグしてみる。

机上デバッグ

ここでの机上デバッグは、ソースコードの妥当性というよりも変数遷移の書き出しをしてみるとする。

i = 0 のとき、
　j = 0 のとき、i 行と同じなので重複判定対象外。
　j = 1 のとき、i 行と重複判定。
　　・・・
　j = 4 のとき、i 行と重複判定。
i = 1 のとき、
　j = 0 のとき、i 行と重複判定。
　j = 1 のとき、i 行と同じなので重複判定対象外。
　j = 2 のとき、i 行と重複判定。
　　・・・
　j = 4 のとき、i 行と重複判定。
・・・
i = 4 のとき、
　j = 0 のとき、i 行と重複判定。
　j = 1 のとき、i 行と重複判定。
　　・・・
　j = 4 のとき、i 行と同じなので重複判定対象外。

かなり長くなってしまったが、おやおや、（i = 0, j = 1）の判定と（i = 1, j = 0）の判定は同じですよね？ だって同じ配列なんですもん。

ということは、i = 1 のときは、j = 2 から判定すればいいんですよね？
（もしくは、i = 3 のときは 0,1,2を判定すればよい。）

重複判定処理　修正版①

重複判定を自行より大きい行とする場合。

  1.     for (i = 0; i < 5; i++) {
  2.         if (ary[i] == "") {
  3.             count++;
  4.             continue;
  5.         }
  6.         for (j = i + 1; j < 5; j++) {
  7.             if (ary[i] == ary[j]) {
  8.                 errorFlg = true;
  9.             }
  10.         }
  11.     }

重複判定処理　修正版②

重複判定を自行までの行とする場合。

  1.     for (i = 0; i < 5; i++) {
  2.         if (ary[i] == "") {
  3.             count++;
  4.             continue;
  5.         }
  6.         for (j = 0 j < i; j++) {
  7.             if (ary[i] == ary[j]) {
  8.                 errorFlg = true;
  9.             }
  10.         }
  11.     }

結論

修正版を使うと、ソースをステップ数（計算量オーダー）が減ってスリムに見えてくるようになりましたね。

次は、各行にエラーを表示する処理を考えます。

 より計算量を減らす考え方はこちら

instery.hatenablog.com