１. はじめに
昨今では、ライブラリの充実や、APIの発達によってほしい情報をいとも簡単に取れてきちゃう世の中です。
そうするとアルゴリズムを学ぶ機会というのは少なくなってきています。※別に悪いわけではないです
もし、自分の使用する言語に欲する処理がライブラリ等で恩智が受けれない場合、ライブラリを自作するしかありません。
しかも自作なので、パフォーマンスが劣悪であったり、バグを生んでしまう可能性があります。
自分自身が技術的負債を抱えていたプロジェクトを担当していた経緯があり今回はパフォーマンスに影響するソートのアルゴリズムに着目していきます!
２. 計算量について(パフォーマンス)
今回はある配列をソートしたいと考えます。
でも使用している言語にソートのライブラリ等がなく、恩智を受けることが出来ません。
なので、自作ライブラリをつくるしかありません。
ソートのアルゴリズムは多く存在しています。どれを使用すればいいか悩んでいる人もいると思います。
ですが、ぶっちゃけクイックソートをマスターしておけば大丈夫なはずです!
名前の通り、数あるソート中で最速だからです。※間違ってたらコメントおねがいします
計算量としては平均𝑂(𝑛 log 𝑛)です。
バブルソートというアルゴリズムがありますが、処理が単純ですが計算量が最悪の場合𝑂(𝑛2)です。
どなたかのQitaの記事にあったのですが少し参考にさせていただきます。※探しておきます
配列の要素数が200,000だったとします。
処理スペックにもよりますが、n = 200,000だった場合、100MIPSの処理能力だと
・バブルソート 𝑂(𝑛2) 40,000,000,000で400秒
・クイックソート 𝑂(𝑛 log 𝑛) 3,522,000で1秒以下
となり明白に差が出てしまいます。アルゴリズムを間違うだけでこうなります。怖い・・ｶﾞｸｶﾞｸ((( ;ﾟДﾟ)))ﾌﾞﾙﾌﾞﾙ
なのでクイックソートを実装します。
３. 実装
実行クラス
class Program
{
static void Main(string[] args)
{
var nums = new int[] { 4, 1, 5, 2, 9, 7, 3, 6, 8 };
//Lengthは要素数を返すのでindexと揃える為にマイナスする
QuickSort(nums, 0, nums.Length -1) ;
//バイナリーサーチ
var result = BinarySearch(nums, 5);
}
public static void QuickSort<T>(T[] array, int first, int last) where T : IComparable<T>
{
// 範囲が一つだけなら処理を抜ける
if (first >= last) return;
// 配列の中央値を取得する。始端、中端、終端
T pivot = Median(array[first], array[(first + last) / 2], array[last]);
var left = first;
var right = last;
while (true)
{
//配列の左から検索し、pivotより大きい値のインデックスを記憶する。
while (array[left].CompareTo(pivot) < 0) left++;
//配列の右から検索し、pivotより小さい値のインデックスを記憶する。
while (array[right].CompareTo(pivot) > 0) right--;
// 始端が終端を超えたら終了
if (left >= right) break;
// 見つかった要素を交換
Swap(ref array[left], ref array[right]);
left++; right--;
}
QuickSort(array, first, left - 1);
QuickSort(array, right + 1, last);
}
/// <summary>
/// 中央値を求める
/// </summary>
private static T Median<T>(T x, T y, T z) where T : IComparable<T>
{
if (x.CompareTo(y) < 0)
{
return x.CompareTo(z) < 0 ? (y.CompareTo(z) < 0 ? y : z) : x;
}
else
{
return y.CompareTo(z) < 0 ? (x.CompareTo(z) < 0 ? x : z) : y;
}
}
/// <summary>
/// 値を交換し、並び変える
/// </summary>
private static void Swap<T>(ref T x, ref T y) where T : IComparable<T>
{
var tmp = x;
x = y;
y = tmp;
}
/// <summary>
/// 二分探索
/// </summary>
public static int? BinarySearch(int[] array, int item)
{
var low = 0;
var high = array.Length - 1;
while (low <= high)
{
var mid = (low + high) / 2;
var guess = array[mid];
if (guess == item)
{
return mid;
}
else if (guess < item)
{
low = mid + 1;
}
else
{
high = mid - 1;
}
}
return null;
}
}
解説
言語はc#です。もっともポピュラーなやり方で実装しました。簡単にまとめると
・配列の中央値を取得する。これを怠ると計算量が最悪になる可能性がある
・配列の両端から中央値をベースに比較し、要素交換する。
・中央値以下と中央値以上で再びソートする。
でしょうか。調べたらもっとわかりやすい図入りの記事はあるので是非みてください。
ついでですが、サーチも実装しました。2分探索(バイナリサーチです)。
ソート済であれば、O(log n)で早いです。
ソート→検索という流れは、パフォーマンスに影響しやすいのでペアで実装しました。
４. まとめ
ぶっちゃけ、ソート・検索については最近の言語であればライブラリを使えばクリア出来ます。
この記事で伝えたいのは、ある程度、脳内にアルゴリズムを蓄えておくことが重要と伝えたいのです。
今の時代、ネットですぐにコードを拾ってこれます。便利な代わりに直ぐに脳内から押し出され、数日後には
記憶に残ってないことが多々あり、開発者としての責務を放り出してしまうことがあります。
実はクイックソートの過程で、ライブラリの恩智を受けれない場面が存在しました。
「中央値を求める」、「2分探索」の場面です。やはり、使用する言語によっては自身で自作せざる得ない場面というのが出てきます。また、恩智を受けれてもプログラム計算量が適切じゃない場面があるかもしれません。
アルゴリズムというのは「考え方」であり、言語に依存しません。どの言語にも適応できます。
もし、興味がある方はアルゴリズムを是非、脳内にメモリしておいてください。