イノベーション エンジニアブログ


株式会社イノベーションのエンジニアたちの技術系ブログです。ITトレンド・List Finderの開発をベースに、業務外での技術研究などもブログとして発信していってます!


このエントリーをはてなブックマークに追加

アルゴリズム計算量入門 〜 ②

どうも、bigenです。
なぜ2本連続で書いているかというと、先週のブログ当番をブッチしてしまった罰ゲームです!

そんなわけで、 前回の記事に引き続き、ソートアルゴリズムの計算量について見ていこうと思います。

【前回の記事のまとめ】
バブルソート: 時間計算量 O(n2), 空間計算量O(n)
バケツソート: 時間計算量 O(m + n), 空間計算量O(m + n)
マージソート: 時間計算量 O(n log n), 空間計算量O(n)
【まとめおわり】

今回は、実際にphpでそれぞれのアルゴリズムを動かして、「計算量本当にそれであってんの?」っていうのを見ていきたいと思います。

前提条件

OS: macOS High Sierra ver.10.13.5
CPU: 第7世代の2.3GHzデュアルコアIntel Core i5プロセッサ
メモリ: 8GB 2,133MHz LPDDR3メモリ
PHP version: 7.1.16

対象とする問題は、

1~mの範囲のランダムな自然数n個からなる配列を昇順にソートする

としています。
ソースは初心にかえって自力で用意しました。
記事の末尾に付録としておいておきますので、暇な方はご参照ください。

また、全体の流れとして、この後

データの数nや、データの取りうる種類mを増やした時に、計算時間とメモリの消費がどのように変化するか

を実測で見ていきます。

計算時間について

時間計算量は、それぞれ

バブルソート: 時間計算量 O(n2)
バケツソート: 時間計算量 O(m + n)
マージソート: 時間計算量 O(n log n)

でした。
O(n2)は「nが10倍になったら計算時間は100倍」
O(m+n)は「nが10倍になったら計算時間も10倍、mが10倍になったら計算時間も10倍」
O(n log n)は「nが10倍になったら計算時間は(10*ちょっと)倍、nが大きいほどちょっとは小さくなる」
という意味です。

データの数が増える場合(nが増える場合)

まずはデータの範囲は1~100の自然数に固定(m=100)し、データの数nを変化させた時に計算時間がどうなるか見ていきましょう。

Table 1. 計算時間(s) , m = 100
n=100 n=1000 n=10000 n=100000

バブルソート

0.0002770

0.0278578

2.7695038

287.1152839

バケツソート

0.0000241

0.0000670

0.0005970

0.0061991

マージソート

0.0002079

0.0030000

0.1332741

11.2226848

バブルソートから見てみると、nが10倍になるにつれ、ほぼ100倍→10000倍→1000000倍ときれいに遅くなっていますね。
典型的なO(n2)の増え方です。 アルゴリズムがシンプルなのもあり、他の依存要素が少ないため綺麗に比例してくれました。

バケツソート は、n:100 → 1000は3倍程度しか増えていませんが、n: 1000 →10000 → 100000はほぼ10倍ずつ増えています。 これは、nが小さい領域ではデータの範囲mに依存する分が大きかったためでしょう。
n=100: 100(mに依存する時間) + 20(nに依存する時間) = 120
n=1000: 100(mに依存する時間) + 200(nに依存する時間) = 300(3倍ぐらい)
n=10000: 100(mに依存する時間) + 2000(nに依存する時間) = 2100(9倍ぐらい)
n=10000: 100(mに依存する時間) + 20000(nに依存する時間) = 20100(10倍ぐらい)
みたいな感じで増えていっただろうっていうことですね。
理論通りのO(m+n)っぽい増え方をしてくれています。

マージソートは、理論どおりにはいってくれませんでした。
nが10倍ずつ増えていくとき、計算時間は
15倍→45倍→80倍
と増えています。理屈上は増え方が減っていってほしいのですが・・・。
原因としては、再起呼び出し条件が最適化されていなかったりするところでしょうか。
(呼ばなくていい再帰呼び出しをしている箇所がある)
それでも、計算量の増え方は、バブルソートよりかなり遅いのが見て取れます。

データの取りうる範囲が大きくなる場合(mが増える場合)

次に、データの数nを固定(n=100)して、データの取りうる範囲mを大きくしてみます。

Table 2. 計算時間(s) , n = 100
m=100 m=1000 m=10000 m=100000

バブルソート

0.0003309

0.0002930

0.0003278

0.0002920

バケツソート

0.0000350

0.0000579

0.0004789

0.0067119

マージソート

0.0002470

0.0002210

0.0002301

0.0002169

バブルソートマージソートデータの取りうる範囲mに依存していないことが見て取れます。

また、バケツソートだけm=1000~100000の間で大体10倍ずつ増えていっていることが分かります。
O(m + n)っぽいですね!

メモリ使用量について

空間計算量はそれぞれ、

バブルソート: 空間計算量 O(n)
バケツソート: 空間計算量 O(m + n)
マージソート: 空間計算量 O(n)

でした。

メモリ使用量を計測するのは難しいのですが、phpではざっくり図るために
memory_get_peak_usage()memory_get_usage()の差を使って計測しました。
計算の前後で増えたメモリ割り当て量が分かります。
ノイズが多いので正確ではないですが、大体の増え方はつかめるんじゃないでしょうか。

データの数が増える場合(nが増える場合)

まずはじめに、データの取りうる範囲mを固定(m=100)して、データの数を増やしたときに割当てメモリがどう増えるか見てみましょう

Table 3. メモリ使用量(byte) , m = 100
n=100 n=1000 n=10000 n=100000

バブルソート

36544

36920

528440

4198480

バケツソート

36544

45168

536688

4206728

マージソート

36544

95784

1112040

8477032

バブルソートバケツソートはほぼ同じ増え方をしています。
n=1000~100000の間で大体10倍ずつ増えています。
O(n)とかO(m+n) っぽいですね。
少し不安定なのでもう少し様子をみたかったのですが、バブルソートはデータ数がこれ以上増えると計算時間がなかなかのものだったので諦めました。

マージソートも、他の2つに比べてメモリが多いように見えますが、増え方を見ると10倍ずつ大きくなっており、結局 O(n)っぽいですね。
計算通りでした。

データの取りうる範囲が大きくなる場合(mが増える場合)

次に、データの数nを固定(n=100)して、データの取りうる範囲mを増やしてみました。

Table 4. メモリ使用量(byte) , n = 100
m=100 m=1000 m=10000 m=100000

バブルソート

36544

36544

36544

36544

バケツソート

36544

45168

536688

4206728

マージソート

36544

36544

36544

36544

phpの基本使用料が36500byteぐらい使うのは良いとして、バケツソートだけ m=1000~100000の間で大体10倍ずつ増えていくのが分かりました。
O(m+n)っぽいですね。
また、バブルソートマージソートデータの範囲mには依存していないことも分かります。
どちらも計算通り、といったところでしょうか。

まとめ

全体として、理論上の増え方になかなか近い実測値が出たんじゃないでしょうか。

みなさんも、エンジニアであれば
「とりあえず動かしてみたけど結果が返ってこない。あと1分で終わるかもしれないし、1年かもしれない。いつまで待てばいいんだ?」
みたいな時ありますよね?

あらかじめプログラムの計算量がわかっていると、データ数だけ見れば「数時間」なのか「数日」なのか「数年」なのかぐらいは大体分かるのです。
すごい!

また、O(n)のような書き方をオーダー記法ビッグオー記法といったりするのですが、これをわかってると
「そのアルゴリズムってどれぐらい早いの?」
「エヌログエヌオーダーだぜ!今までのエヌニジョウオーダーとは比べ物にならないぜ!」
みたいな会話ができるわけですね。
すごい!!

興味ある方は、ぜひ色々調べてみてください。
こちらからは以上です。

付録

ソースコードはこちら。 GitHubはこちら。 https://github.com/bigen1925/complexity_of_sort_algorithm

<?php
//////////////
// Usage
// Call from command line
// $ php sort.php <number_of_data> <max_range_of_data> <kind_of_sort_method>
// Sample: $ php sort.php 1000 100 bubble
//////////////

// データの数
$length_array = (int)$argv[1] ?: 1000;
// データのとりうる値の上限
$max_range = (int)$argv[2] ?: 100;
// ソートアルゴリズム
$sort_method = $argv[3] ?: "all";

// 計測
main($length_array, $max_range, $sort_method);

function main($length_array, $max_range, $sort_method)
{
    // 1~max_rangeまでの数字から成る、ランダムな順序の数列を生成
    $array = array();
    for ($i=0; $i < $length_array; $i++) {
        $array[] = rand(1, $max_range);
    }

    // 初期の割当メモリ
    $initial_memory_usage = memory_get_usage();

    if ($sort_method === "all" || $sort_method === "bubble") {
        $time_start = microtime(true);
        bubbleSort($array);
        $time = microtime(true) - $time_start;
        echo "bubbleSort:: {$time}s\n";
    }

    if ($sort_method === "all" || $sort_method === "buckets") {
        $time_start = microtime(true);
        bucketsSort($array, $max_range);
        $time = microtime(true) - $time_start;
        echo "bucketsSort:: {$time}s\n";
    }

    if ($sort_method === "all" || $sort_method === "merge") {
        $time_start = microtime(true);
        mergeSort($array);
        $time = microtime(true) - $time_start;
        echo "mergeSort:: {$time}s\n";
    }

    // プログラム実行中に追加で割り当てられたメモリ量
    $used_memory = memory_get_peak_usage() - $initial_memory_usage;
    echo "used_memory:: {$used_memory}\n";
}

// バブルソート
// @param array @array ソートしたい自然数配列
// @return array ソート済みの配列
function bubbleSort(array $array)
{
    $length = count($array);
    for ($i=0; $i < $length; $i++) {
        for ($j=0; $j < $length - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }
    return $array;
}

// バケツソート
// @param array $array ソートしたい自然数配列
// @param integer $max_range データのとりうる最大値
// @return array ソート済みの配列
function bucketsSort(array $array, $max_range)
{
    $length = count($array);
    $buckets = array_fill(1, $max_range, 0);
    $sorted_array = array();

    foreach ($array as $value) {
        $buckets[$value]++;
    }

    foreach ($buckets as $value => $count) {
        for ($i = 0; $i < $count; $i++) {
            $sorted_array[] = $value;
        }
    }

    return $sorted_array;
}

// マージソート
// @param array $array ソートしたい自然数配列
// @return array ソート済み配列
function mergeSort(array $array)
{
    $length = count($array);
    $sorted_array = array();

    if ($length > 1) {
        $mid_index = floor(($length + 0.5) / 2);
        $left_array = array_slice($array, 0, $mid_index);
        $right_array = array_slice($array, $mid_index);

        $left_array = mergeSort($left_array);
        $right_array = mergeSort($right_array);
        while (count($left_array) || count($right_array)) {
            if (count($left_array) == 0) {
                $sorted_array[] = array_shift($right_array);
            } elseif (count($right_array) == 0) {
                $sorted_array[] = array_shift($left_array);
            } elseif ($left_array[0] > $right_array[0]) {
                $sorted_array[] = array_shift($right_array);
            } else {
                $sorted_array[] = array_shift($left_array);
            }
        }
    } else {
        $sorted_array = $array;
    }

    return $sorted_array;
}