エクセルVBAで、ソートアルゴリズムとデータの違いによるソート処理時間比較

前回まででいろいろなソートアルゴリズムをVBAで書くのは満足したので今回はそれらを使って計測

計測した環境は

OS：Windows 10 Home 64bit

エクセル：エクセル2007

CPU：AMD PhenomⅡ X3 720BE @3.0GHz

OS以外は2007年から使い続けている10年前のパソコン

前回までの結果

これで使っていたデータは1から10000までのランダムな数値、これの1万件だった

件数を変化させたら処理時間はどう変わるのか、10倍の10万件にしたら処理時間も10倍になるのか10^2で100倍になるのかとか

ランダム数値のデータ作成するマクロ

Sub ランダム数値1万件の配列作成()
    Dim c As Long: c = 10000
    Dim v() As Variant
    ReDim v(c - 1)
    Randomize
    For i = 0 To c - 1
        v(i) = CLng(c * Rnd)
    Next
End Sub

だいたいこんな感じで作成

まずは時間がかかる組で千件から1万件の変化

件数を10倍にしたら処理時間は約100倍になっている

Wikipediaとかの説明に

計算量はO (n^2)

とかあるnってのが件数でOが計算量ってことかなあ

これなら件数が10件なら計算量は10^2=100

100件なら100^2=10000になるから

100件の計算量は10件の100倍であっている

グラフで

対数目盛で

だいたい件数に比例しているかな？

シェーカーソートが遅くなっている

倍率で比較

件数が増えるとシェーカーソートは遅くなるのかなあ

バブルソートは100前後で変化しないと思っていたけど

逆に効率良くなっている傾向

10万件やそれ以上は日が暮れそうなので測らない

と言うか1回計測したんだけど20分くらいたっても終わらないから諦めた

10万件を予測すると

バブルソート1で1万件は18秒だからそれの100倍で1800秒

1800/60=30分かかる

100万件なら

30*100=3000分=3000/60=50時間

50時間！

日が2回暮れる

次は速い組で比較

1万、10万、100万、1000万でそれぞれ計測

速いねえ

バブルソートで50時間(予測)だったのがクイックソートなら4.5秒

それに件数が10倍になっても100倍にはなっていない

グラフで

やっぱり普通のグラフだとよくわからない

対数で

件数に比例しているみたいだけど

よくわからないので

倍率で比較

時間がかかる組では100倍前後だったけど

速い組は10倍前後

これをグラフで

コムソートはブレているなあ、データの内容に影響されやすいのかしら

マージソートはトップダウン型もボトムアップ型も変化が少ない

それ以外のシェルソート、ヒープソート、クイックソートは

件数が増えると効率良くなっている

特にクイックソートはただでさえ速いのにより効率的になっている

やっぱりクイックソートなんだなあ

同じ値がたくさんあるデータの場合

ここまでは同じ数値がほとんどないデータだった

これを1から10までのランダムな数値にしたらどうなるのか、つまり同じ値がたくさんあるデータ

データ作成するマクロ

'ランダム数値配列を作成
'cが要素数、vrに100を指定した場合は1から100の間の数値
Function RandomValue(c As Long, vr As Long) As Long()
    Dim v() As Long
    ReDim v(c - 1)
    Randomize
    For i = 0 To c - 1
        v(i) = CLng(vr * Rnd)
    Next
    RandomValue = v
End Function

件数と数値の範囲を指定して作成

同じ値がたくさんあるデータだと選択ソート以外は速くなっている

1秒以下のものは見づらいので分けたグラフ

おお、シェルソートは2倍も速くなってクイックソートより速くなっている

コムソートも2割以上速くなっている

ソート率による処理時間の変化

これまでのデータは普通にバラバラなのでソート率0%

ソートが終わっているデータはソート率100%

ほとんど順番通りにソートされているのがソート率99%

この3つをそれぞれのアルゴリズムで比較

ソート率99%のデータ作成するマクロ

'99%ソート済みの配列を作成
Function Sort99Value(c As Long, vr As Long) As Long()
    Dim v() As Long
    ReDim v(c - 1)
    Randomize
    For i = 0 To c - 1
    If CLng(c * Rnd) < c / 100 Then
        v(i) = CLng(vr * Rnd)
    Else
        v(i) = i
    End If
    Next
    Sort99Value = v
End Function

連番の中に100分の1の確率でランダムな数値を入れているだけだから、99%っていってもだいたい99%かなあってぐらいのができあがる

100%は普通の連番なので

'連番の配列を作成
Function SortedValue(c As Long) As Long()
    Dim v() As Long
    ReDim v(c - 1)
    For i = 0 To c - 1
        v(i) = i
    Next
    SortValue = v
End Function

時間がかかる組で

ソート済みに対してはシェーカーソートと挿入ソートは、比較処理のループは1回で終わるし交換処理は1回も発生しないから圧倒的に速い

その他もソート済みのほうがかなり速くなっているのは以外だったなあ、あんまり変わらないと思っていた、これは交換する処理コストが結構掛かるってことかな

バブルソート3は交換処理を軽くするために下準備をする処理を入れてバブルソート2より速くしたんだけど、交換が発生しない場合は逆にその下準備の分だけ遅くなってバブルソート2と逆転しているのが面白い、こうなるんだなあ

速い組

ヒープソートはバラバラよりソート済みのほうが遅くなっているのが面白い

こういう結果を見るまでは気づかなかったけど、なんとなく想像できる

たぶんヒープ構造を作成する部分で時間の大半を使っていて

ソート部分ではそんなにかかっていないはず

マージソートは相変わらずマイペース、バブルソートもこんなのを想像していたんだけどねえ

そしてここでもシェルソートがクイックソートより速い場面がでてきた、それでもやっぱりクイックソートは速いなあ

1万件ソートではコムソートとシェルソートはほとんど差がないから同じくらいだと思っていたけどいろいろ見たらシェルソートのほうが速いねえ

処理時間計測に使ったマクロ

Sub 計測2()
    Dim r As Range
    Set r = Sheets("all").Range("c185") 'タイム記入セル
    Const l As Long = 5 'ループ回数指定
   '実行するプロシージャ名
   '全部
    Const ff As String = "testBubble1,testBubble2,testBubble3,testShaker2,testShaker3,testComb2_2,testInsertion2,testShellSort2,MergeSort2,testMerge2BU,SelectSort,HeapSort3_1,testQuick4"
   '速い組
   'Const ff As String = "testComb2_2,testShellSort2,MergeSort2,testMerge2BU,HeapSort3_1,testQuick4"
   '時間がかかる組
   'Const ff As String = "testBubble1,testBubble2,testBubble3,testShaker2,testShaker3,testInsertion2,SelectSort"

    Dim fName() As String
    fName = Split(ff, ",")
    vv = RandomValue(10000, 10) 'ランダム数値配列取得
   ' vv = SortValue(100000) '100%ソート済みの配列
   ' vv = Sort99Value(100000, 100000) '99%ソート済みの配列

    Dim i As Long, j As Long
    Dim v As Variant
    Dim st As Single, t As Single
    For j = 0 To UBound(fName)
        t = 0
        For i = 0 To l - 1
            v = vv '配列をコピー
            st = Timer
            Application.Run fName(j), v 'ソート
            t = t + Timer - st
        Next
        r.Offset(j, 0).Value = t / l '平均値をセルに記入
    Next
    MsgBox "計測完了"
End Sub