処理時間はデータ量に比例しない場合の考察と対策

処理時間（計算量）はデータ量に比例するとは限りません。
例えば、データ量が10倍になったからと言って、処理時間も10倍になるとは限りません。

処理時間が何倍になるかは、アルゴリズムにより決まります。
アルゴリズム次第では、データ量が10倍になった時に処理時間が100倍になることも有り得ます。

今回は、試しに、Java作成したソート処理の実行時間を測ってみます。
アルゴリズムはバブルソートです。

【サンプルコード】

・BubbleSort.java

import java.util.ArrayList;
import java.util.Collections;

public class BubbleSort {

    public static void main(String［］ args) {

        // データ量（どちらかの行をコメントアウト）
        int num = 10000;
        // int num = 100000;
        
        // ソート対象の配列
        ArrayList＜Integer＞ array = new ArrayList＜＞();
        for (int i = 0; i ＜ num; i++) {
            array.add(i);
        }
        Collections.shuffle(array);

        // 回答の配列
        ArrayList＜Integer＞ answer = new ArrayList＜＞();
        for (int i = 0; i ＜ num; i++) {
            answer.add(i);
        }

        // ソート処理実行
        long startTime = System.currentTimeMillis();
        sort(array);
        long endTime = System.currentTimeMillis();

        // 回答通りか確認
        int diffCount = 0;
        for (int i = 0; i ＜ num; i++) {
            if (array.get(i).intValue() != answer.get(i).intValue()) {
                System.out.println((i + 1) + "つ目の要素の内容を出力");
                System.out.println("　結果：" + array.get(i));
                System.out.println("　回答：" + answer.get(i));
                diffCount++;
            }
        }
        if (diffCount == 0) {
            System.out.println("差異無し。");
        }

        // 秒数出力
        System.out.println((endTime - startTime) + " ミリ秒");

    }

    static void sort(ArrayList＜Integer＞ array) {
        // 左から順番に値を確定させていく
        // 添字の最小は0、最大はarray.size() - 1
        for (int i = 0; i ＜ array.size() - 1; i++) {
            // 走査は右から
            for (int j = array.size() - 1; j ＞ i; j--) {
                // 入れ替え処理（左が右より大きければ入れ替え）
                if (array.get(j - 1) ＞ array.get(j)) {
                    int tmp = array.get(j - 1);
                    array.set(j - 1, array.get(j));
                    array.set(j, tmp);
                }
             }
        }
    }

}

import java.util.ArrayList;

import java.util.Collections;

public class BubbleSort {

public static void main(String［］ args) {

// データ量（どちらかの行をコメントアウト）

int num = 10000;

// int num = 100000;

// ソート対象の配列

ArrayList＜Integer＞ array = new ArrayList＜＞();

for (int i = 0; i ＜ num; i++) {

array.add(i);

}

Collections.shuffle(array);

// 回答の配列

ArrayList＜Integer＞ answer = new ArrayList＜＞();

for (int i = 0; i ＜ num; i++) {

answer.add(i);

}

// ソート処理実行

long startTime = System.currentTimeMillis();

sort(array);

long endTime = System.currentTimeMillis();

// 回答通りか確認

int diffCount = 0;

for (int i = 0; i ＜ num; i++) {

if (array.get(i).intValue() != answer.get(i).intValue()) {

System.out.println((i + 1) + "つ目の要素の内容を出力");

System.out.println("　結果：" + array.get(i));

System.out.println("　回答：" + answer.get(i));

diffCount++;

}

if (diffCount == 0) {

System.out.println("差異無し。");

}

// 秒数出力

System.out.println((endTime - startTime) + " ミリ秒");

}

static void sort(ArrayList＜Integer＞ array) {

// 左から順番に値を確定させていく

// 添字の最小は0、最大はarray.size() - 1

for (int i = 0; i ＜ array.size() - 1; i++) {

// 走査は右から

for (int j = array.size() - 1; j ＞ i; j--) {

// 入れ替え処理（左が右より大きければ入れ替え）

if (array.get(j - 1) ＞ array.get(j)) {

int tmp = array.get(j - 1);

array.set(j - 1, array.get(j));

array.set(j, tmp);

}

【実行時間】

・データ量が10000レコードの場合

　１回目：1272ミリ秒
　２回目：2826ミリ秒
　３回目：1075ミリ秒

　１回目：1272ミリ秒

　２回目：2826ミリ秒

　３回目：1075ミリ秒

・データ量が100000レコードの場合

　１回目：335986ミリ秒
　２回目：305728ミリ秒
　３回目：289040ミリ秒

　１回目：335986ミリ秒

　２回目：305728ミリ秒

　３回目：289040ミリ秒

以上のように、データ量が10倍になった場合に、実行時間も100倍（実測ではそれ以上）になりました。

なぜ実行時間がデータ量に比例しないのかと言うと、このアルゴリズムでは二重ループが発生するからです。
二重ループの中の処理が行われる回数は、10000レコードの場合は「1万 * 1万」（正確には「1万 * 9999」）回ですが、100000レコードの場合は「10万 * 10万」（正確には「10万 * 99999」）回となり、100倍の差となります。
この差が、実行時間にも反映されます。

専門用語で言うと、このような概念は「O(オーダ)」と呼ばれます。
（詳しくは、以前の記事で紹介しています）

実務でも、大量のデータを処理する必要がある場合は、「O(オーダ)」の概念や、最適なアルゴリズムを意識する必要があります。
基礎的なアルゴリズムは、情報処理技術者試験で学ぶことができます。
また、競技プログラミングでは最適なアルゴリズムを考えさせる問題が頻出なので、詳しく学びたい方は手を出してみると面白いと思います。

いかがでしたでしょうか。

「処理時間はデータ量に比例するとは限らない」というのは、アルゴリズムや性能問題を学んだことがない人にとっては意外なことだと思います。
システムには性能問題（Webページの動作が遅い、夜間バッチが決められた時刻までに終わらずにサービス開始時刻になってもシステムを利用できない、等）がつきものです。
そうした性能問題は、データ量の増加に対して処理時間が指数関数的に増えることで引き起こされていることも少なくありません。

この記事を通して、アルゴリズムや性能問題への興味を持つ人が一人でも増えれば幸いです。