簡潔と効率

埋め草記事その2です。

前回の最後に書きましたが、全部一気にListなりStreamなりに突っ込んでsort掛けて上から一個目と二個目を取り出すという実装は、要素数が少ないからできる力業なわけですね。簡潔にクリーンに書いた方が力業になっているというのが面白いところかなと思ったりするわけですが。

で、素朴側に振った実装はこういう感じです。元の投稿のコードとそんなに変わりませんけど、まあ多少は頑張ったと思ってください。

import java.util.Scanner;

public class SecondMax3 {
    public static void main(String[] args) {
        int upperLimit = Integer.parseInt(args[0]);
        try ( Scanner scanner = new Scanner(System.in)) {
            int max = Integer.MIN_VALUE;
            int secondMax = Integer.MIN_VALUE;
            boolean maxRepeated = false;

            int count = 0;
            while ( upperLimit == -1 || count++ < upperLimit ) {
                int num = scanner.nextInt();
                if ( num == -1 ) {
                    break;
                }
                if (num > max) {
                    secondMax = max;
                    max = num;
                    maxRepeated = false;
                } else if (num == max) {
                    maxRepeated = true; 
                } else if (num > secondMax) {
                    secondMax = num;
                }
            }

            if (maxRepeated) {
                System.out.println("Two same maximum numbers, no second max.");
            } else {
                System.out.println("Second max is " + secondMax);
            }
        }
    }
}

ちなみにコマンドライン引数に要素数を渡せるという仕組みになっています。エラー処理とか入れる余地があるんですが、まあ今回はこのままで。

前回のコードにも同じように修正を入れて、要素数を5の決め打ちから変更できるようにしました。

あと、指定した数の乱数を吐き出すプログラムも書きましたがコードは割愛。

検証結果

同じ乱数列を渡して二番目に大きい数を導き出す処理を実施する三つのプログラムの実行時間を計ります。

java GenerateNumbers <n> > <output file>
time java SecondMax* <n> < <output file>

というように実行します。結果をまとめたのが以下のような表になります。

n	Listで処理	Streamで処理	素朴に処理
10000	real 0m0.199s user 0m0.448s sys 0m0.065s	real 0m0.199s user 0m0.403s sys 0m0.052s	real 0m0.337s user 0m0.420s sys 0m0.081s
100000	real 0m0.483s user 0m1.042s sys 0m0.117s	real 0m0.448s user 0m0.939s sys 0m0.117s	real 0m0.388s user 0m0.716s sys 0m0.098s
1000000	real 0m2.157s user 0m2.234s sys 0m0.293s	real 0m2.165s user 0m2.211s sys 0m0.324s	real 0m1.625s user 0m1.331s sys 0m0.266s
10000000	real 0m22.229s user 0m18.337s sys 0m1.585s	real 0m20.415s user 0m16.647s sys 0m1.427s	real 0m12.212s user 0m6.663s sys 0m0.677s

まあこの結果は計算量を考えれば当然ではありますが。

ということで簡潔な実装と素朴な実装と効率的な実装、の話でした。