GWいかがお過ごしでしょうか。
私は転職して、本格的に開発側へシフトしたこともあって
いろいろなアルゴリズムに触れる機会が増えています。
また、JS系のライブラリやフレームワークを業務で使う事が多いので
今回は計算量を題にして、JavaScriptのプログラミングにも触れながらまとめてみようと思います。
計算量って？
情報科学の処理量を表し、アルゴリズムの処理時間を比較するために用いられます。
計算量は、オーダー記法を用いて表現します。
例えば処理するデータ数をnとしたとき、O(1)やO(n)といった書き方をします。
O(1)といった表記は、定数オーダーともいい、データ量に寄らずに処理時間が一定であることを表しています。
O(n)は、処理時間がデータn個に比例することを表しています。
また、例えば処理時間がデータn個の2倍かかるとした場合、計算量をO(2n)と書きたくなりますが
この定数2は無視をしてO(n)と書きます。
どう使われる？
O(1)とO(n)では、データ量が増えるとO(1)のほうが早そうですよね。
計算量を出すことで、処理時間を予測することは、アルゴリズムやデータ構造の選定に役立つわけです。
ソートアルゴリズムの計算量
今回は代表的なソートのアルゴリズムの計算量を見ていきます。
バブルソート
配列の要素の前から順番に比較してソートをします。
計算量は、O(n^2)になります。
クイックソート
基準値（ピボット）を決めてそれよりも大きい値小さい値を集めます。
この処理を再帰的に行ってソートをします。
計算量は、ピボットの選び方によって異なりますが、平均するとO(nlogn)になります。
（最悪計算量はO(n^2))
マージソート
配列を最小単位まで分割し、それぞれをマージしながらソートをする。
計算量はO(nlogn)になります。
計算量（処理時間）を確かめてみる
せっかくなので、今学習中のJavaScriptでモジュールを作って確認してみます。
バブルソート
'use strict';
// バブルソート
function bubbleSort(array) {
let result = Array.from(array);
for(let e = result.length - 1; e > 0; e--){
for(let i = 0; i < e; i++){
if(result[i] > result[i + 1]){
[result[i], result[i+1]] = [result[i+1], result[i]];
}
}
}
return result;
}
module.exports = bubbleSort;
クイックソート
'use strict';
function quickSort(array, start = 0, end = array.length - 1){
// クイックソート
if(end <= start){
return;
}
const pivot = selectPivot(array, start, end);
let left = start;
let right = end;
while(true){
while(array[left] < pivot) { left++; }
while(array[right] > pivot) { right--; }
if(left >= right) { break; } // leftとrightが逆転 = 探索終了
[array[left], array[right]] = [array[right], array[left]];
left++;
right--;
}
// 前半後半で、再起処理
quickSort(array, start, left - 1);
quickSort(array, right + 1, end);
// ピボットを選ぶ
function selectPivot(array, start , end){
// 配列の先頭、中央、末尾の中央値をピボットとする。
const [x, y, z] = [ array[start],
array[Math.floor((start + end) / 2.0)],
array[end] ];
if(x > y){
return y < z ? y :
z < x ? x : z;
} else {
return z < y ? y :
x < z ? x : z;
}
}
}
module.exports = quickSort;
マージソート
'use strict';
// マージソート
function margeSort(array){
if( array.length < 2 ){ return array; }
const middle = Math.floor(array.length / 2.0);
let left = array.slice(0, middle);
let right = array.slice(middle);
return marge(margeSort(left), margeSort(right));
// 配列をソートしながら一つに統合する
function marge(left, right){
let result = [];
let leftIndex = 0;
let rightIndex = 0;
while(leftIndex < left.length && rightIndex < right.length){
if(left[leftIndex] < right[rightIndex]){
result.push(left[leftIndex++]);
}else{
result.push(right[rightIndex++]);
}
}
return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
}
module.exports = margeSort;
処理時間を計測するためのモジュール
引数で与えた関数の処理時間を計測します。
（ブラウザ上で動かすなら、console.time系ではなくてperformance.now()とか使うといい）
'use strict';
function measureElapseTime(func, dataNum, targetName){
let measureTarget = `${targetName} times elapse time`;
// ランダムな配列データを作成
const array = [];
for(let i = 0; i < dataNum; i++) {
const value = Math.random();
array.push(value);
}
console.time(measureTarget);
func(array);
console.timeEnd(measureTarget);
}
module.exports = measureElapseTime;
仕様例
今回はサンプルデータを10000として計測してみます。
const measureElapsetime = require('./measureTime');
const bubleSort = require('./bublesort');
const quickSort = require('./quicksort');
const margeSort = require('./margesort');
const dataNum = 10000;
measureElapsetime(bubleSort, dataNum, 'BubleSort');
measureElapsetime(quickSort, dataNum, 'QuickSort');
measureElapsetime(margeSort, dataNum, 'margeSort');
実行結果
BubleSort times elapse time: 315.860ms
QuickSort times elapse time: 18.161ms
margeSort times elapse time: 17.550ms
確かに、クイックソートや、マージソートのほうがバブルソートのよりも約20倍早いことがわかります。
（もう少し早くなっても良さそうですが…）
また、クイックソートとマージソートの平均計算量が同等（O(nlogn)）なので、近いこともわかります。
終わりに
他にもヒープソートやバケットソートなど、ソートアルゴリズムはまだまだあります。
これらをソースコードにして、処理時間を確かめてみるのもいいかもしれません。
参考
「Subterranean Flower Blog」 【連載記事】JavaScriptでプログラミングを学ぶ その5：データ構造とアルゴリズム