Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@solensen

VBA のソートの速度を比較

Last updated at Posted at 2019-08-27

VBA でソート方法ごとの速度比較

『アルゴリズム図鑑』(翔泳社)を読んで試したくなったので、VBAでソートアルゴリズムを試してみた。
（結果は一番下です）

比較方法

  • 要素数が判明している整数（重複無し）の配列を用意し、可能な限り配列内で Swap してソートする。
  • 配列に乱数が収まっている状態から計測開始、ソート（配列操作）終了時点で計測終了。
  • Swap の回数も計測する。（その際にカウント用の変数をインクリメントしているので、その時間の分だけすこし不公平かも）
  • If 文で大小比較する。Swap 処理は、別の変数を介して tmp ← a, a ← b, b ← tmp で行う。
  • ソートメソッドやワークシート関数を使って、シート上でのソートも試す。計測方法は上記の配列操作に準じる。

選手紹介

  • ソートメソッド ： Excel のソートメソッド。ワークシート上でソートします。
  • バブルソート ： 定番？ 直観的にわかりやすい。
  • 選択ソート ： Swap 回数は少ないので、線形探索の速度に左右される？
  • 選択ソート（ワークシート関数） ： 下手なコードより速いのか？ シート上で MIN関数 と MATCH関数 で実験。
  • 挿入ソート ： 内容的にはバブルソートとほぼ同じかな。
  • ヒープソート ： ソートに限らず、ヒープ自体の有用性も高い。
  • マージソート ： 実装が少しだけややこしい。
  • （異星人X） ： ？？？

（クイックソートは、力尽きたのでパスしてます。。）

実装について

  • ソートメソッド ： 乱数配列の内容がセル範囲に入力されている状態から計測開始して、ソートメソッド実行時間のみ計測してます。

  • バブルソート、挿入ソート ： 2重ループの外側で先頭からソート済にしていき、内側で後方から順に大小比較、Swap を進めていく感じです。

  • 選択ソート ： 2重ループの外側で先頭からソート済にしていき、内側で配列の（ソート未済の）全要素に順次アクセスしながら大小比較して、最小値を求めて、Swap しています。

  • 選択ソート（ワークシート関数） ： 乱数配列の内容がセル範囲に入力されている状態から計測開始して、WorksheetFunction のコードから、MIN で最小値取得、MATCH でその最小値の位置を取得し、（変数ではなく）シート上の別セルへのコピーでSwap をしています。

  • ヒープソート　：　ヒープは1次元配列に疑似的に構築しました。ヒープ構築と、ソートをそれぞれ分けて計測。
    （以降のコードはすべて主要処理のみの抜粋）

'ヒープ構築の部分のみ独立して、時間とSwap回数を計測した
'以下はヒープ構築部分

Dim StartTime: StartTime = Timer

    'Lstは乱数を格納済の配列、要素数(1 to cnt)
    HeapArray(1) = Lst(1)
    StepCnt = 1

    For i = 2 To cnt
        CurrentKey = i
        '乱数をひとつずつ、いったんヒープ配列の最後尾に追加
        HeapArray(CurrentKey) = Lst(CurrentKey)
        Do
            '1世代前までの要素数が、2 の何乗かを求める
            n = Int(WorksheetFunction.Log(CurrentKey, 2))
            '値が属する世代の、最初の要素の添え字を求める
            k = CurrentKey - (2 ^ n - 1)
            '大小比較の対象である、直接の親の添え字を求める
            p = 2 ^ (n - 1) - 1 + WorksheetFunction.Round(k / 2, 0)

　          '追加した要素が親より大きければ、そうでなくなるまでSwapを繰り返し
            'ヒープが構築される
            If HeapArray(CurrentKey) > HeapArray(p) Then
                'Swap
                buf = HeapArray(CurrentKey)
                HeapArray(CurrentKey) = HeapArray(p)
                HeapArray(p) = buf
                'Swap回数加算
                StepCnt = StepCnt + 1
                If p = 1 Then Exit Do
                CurrentKey = p
            Else
                Exit Do
            End If
        Loop
    Next i
    
    ResultCell.Offset(-1, 1) = Timer - StartTime

続いてヒープソート本体

    For i = cnt To 3 Step -1
        'Swap、ヒープの先頭（最大値）を、配列の末尾に移動している
        buf = HeapArray(i)
        HeapArray(i) = HeapArray(1)
        HeapArray(1) = buf
        'Swap回数加算
        StepCnt = StepCnt + 1
        
        CurrentKey = 1

        '先頭に持ってきた値を子と大小比較
        '子より小さければ、そうでなくなるまで Swap を繰り返す
        Do
            'n、k はヒープ構築時と同じ
            'cは子の添え字、2分木なので2つ
            n = Int(WorksheetFunction.Log(CurrentKey, 2))
            k = CurrentKey - (2 ^ n - 1)
            c1 = 2 ^ (n + 1) - 1 + k * 2 - 1
            c2 = c1 + 1
            If c2 >= i Then Exit Do
            
            '子の内､大きい方を取得
            If HeapArray(c1) < HeapArray(c2) Then
                cMax = c2
            Else
                cMax = c1
            End If
            
            '大きい方の子と比較
            If HeapArray(CurrentKey) < HeapArray(cMax) Then
                '子が大きい場合は、子と Swap
                buf = HeapArray(CurrentKey)
                HeapArray(CurrentKey) = HeapArray(cMax)
                HeapArray(cMax) = buf
                
                CurrentKey = cMax
                'Swap回数加算
                StepCnt = StepCnt + 1
            Else
                '子より大きいことが確定したら、ヒープ復元完了
                Exit Do
            End If
        Loop
    Next i
    
    If HeapArray(2) < HeapArray(1) Then
        '最後に Swap
        buf = HeapArray(2)
        HeapArray(2) = HeapArray(1)
        HeapArray(1) = buf
        'Swap回数加算
        StepCnt = StepCnt + 1
    End If
    
    ResultCell.Offset(-1, 3) = Timer - StartTime

ここでも、ヒープの構造を維持するためのSwapが大半となる。
（ソート自体は、完成したヒープからポップして、配列の後方から詰めていくのみ）

  • マージソート ： マージ部分はいったん別配列に格納し、マージ後に元の配列に戻す（Swap回数はソート時のみ計上し、ソート済の配列を元の配列に写す際は計上していない）
    Dim StepCnt As Long: StepCnt = 0
    StartTime = Timer

    Do
        For i = 1 To cnt Step StepInterval
            If i + StepInterval / 2 <= cnt Then
                LeftHead = 0: RightHead = 0
                ReDim tmpLst(1 To cnt): tmpIdx = 1
                
                If i + StepInterval - 1 > cnt Then
                    MaxIdx = cnt
                Else
                    MaxIdx = i + StepInterval - 1
                End If
                
                'i to MaxIdx（= StepInterval） は、分割後の部分 × 2つ分の長さで、マージの範囲
                For j = i To MaxIdx
                    If i + StepInterval / 2 + RightHead <= cnt And i + LeftHead <= cnt And LeftHead < StepInterval / 2 And RightHead < StepInterval / 2 Then
                       '分割後の左右の先頭どちらか小さい方を、一時配列の先頭から詰めていく
                        If Lst(i + LeftHead) <= Lst(i + StepInterval / 2 + RightHead) Or RightHead >= StepInterval / 2 Then
                            tmpLst(tmpIdx) = Lst(i + LeftHead)
                            LeftHead = LeftHead + 1
                            StepCnt = StepCnt + 1
                        ElseIf Lst(i + LeftHead) > Lst(i + StepInterval / 2 + RightHead) Or LeftHead >= StepInterval / 2 Then
                            tmpLst(tmpIdx) = Lst(i + StepInterval / 2 + RightHead)
                            RightHead = RightHead + 1
                            StepCnt = StepCnt + 1
                        End If
                    '分割配列の右側を全て一時配列に格納後、残る左側も全て一時配列へ追加
                    ElseIf LeftHead < StepInterval / 2 Then
                        For k = LeftHead To StepInterval / 2 - 1
                            If i + LeftHead <= cnt Then
                                tmpLst(tmpIdx) = Lst(i + LeftHead)
                                LeftHead = LeftHead + 1
                                tmpIdx = tmpIdx + 1
                                StepCnt = StepCnt + 1
                            End If
                        Next k
                    '分割配列の左側を全て一時配列に格納後、残る右側も全て一時配列へ追加
                    ElseIf RightHead < StepInterval / 2 Then
                        For k = RightHead To StepInterval / 2 - 1
                            If i + StepInterval / 2 + RightHead <= cnt Then
                                tmpLst(tmpIdx) = Lst(i + StepInterval / 2 + RightHead)
                                RightHead = RightHead + 1
                                tmpIdx = tmpIdx + 1
                                StepCnt = StepCnt + 1
                            End If
                        Next k
                    End If
                    
                    '分割後のマージ処理は、一時配列（tmpLst）に先頭から詰めていくため
                    '一時配列の添え字を1つインクリメントする
                    tmpIdx = tmpIdx + 1
                Next j
                
                'マージ（tmpLst）ができたら、元のリストのマージ範囲に、
                'マージ（ソート）済の配列を戻す
                tmpIdx = 1
                For j = i To MaxIdx
                    Lst(j) = tmpLst(tmpIdx)
                    tmpIdx = tmpIdx + 1
                Next j
            End If
        Next i
        
        '一周マージしたら、マージ範囲の大きさ（StepInterval）を2倍にして、
        'ふたたび先頭からループ処理
        StepInterval = StepInterval * 2
    Loop While StepInterval < cnt * 2
    
    ResultCell.Offset(-1, 1) = Timer - StartTime
    ResultCell.Offset(-1, 2) = StepCnt

結果（所要時間）

要素数 ⇒ 10000 20000 30000 40000 50000
SortMethod 0.0078 0.0172 0.0234 0.0249 0.0363
BubbleSort 7.44 30.03 67.99 120.24 190.92
SelectionSort 2.32 9.37 21.73 38.47 60.32
WorksheetFunction 10.58 22.43 35.93 50.11 65.73
InsertionSort 7.64 30.90 69.40 123.85 193.37
HeapBuild 0.20 0.39 0.58 0.77 0.95
HeapSort 0.51 1.12 1.75 2.40 3.10
MergeSort 0.91 3.55 7.97 14.29 41.32
X 0.58 - - - 14.61

※単位は秒。
　5回試行の平均を、見やすい桁数で四捨五入済み。
　『X』のみ、実数の乱数を1回ソート。

順位（要素数50,000）

  1. ソートメソッド：100倍以上違う。要素数50,000でバブルソートの5,000倍高速になる。
  2. ヒープソート：0.04秒を切る異次元のソートメソッドを除けば、ヒープの構築を含めても約4秒と非常に速い。
  3. X：正体は JavaScript で書いたバブルソートでした（Chrome で実行）。VBA より10倍以上速い。。
  4. マージソート：ヒープソートよりかなり遅い。実装が悪かったのかも？
  5. 選択ソート：他のソートより Swap の回数が圧倒的に少ない分、線形探索にておおよそ(要素数 ^ 2 / 2 )回も配列の値にアクセスしているにも関わらず、Swap の多いバブルソート等よりは非常に速くなっている。
  6. 選択ソート（ワークシート関数）：予想以上に遅かったが、要素数が増えるほど、メモリ上での配列操作の選択ソートに肉薄。Swap をセルへのコピーで行っていたが、変数を使ってメモリ上での操作に変えれば、配列での選択ソートよりも速くなりそう。
  7. バブルソート：他のソートに比べると極めて遅い。やはりなるべく避けるべき。
  8. 挿入ソート：バブルソートの兄弟のようなもの？

分かったこと

  • ソートメソッド 0.04秒 > ヒープソート 4秒 >（JS バブルソート 14秒）> マージソート 41秒 >（以下1分以上）、といったところ。

  • 可能な限り、超高速のソートメソッドで処理すべき。（いろいろな人が言っていることだとは思うが、ここまで早いとは。しかもコードも圧倒的に簡単）

  • **ヒープソートは、簡単に配列で（疑似的）ヒープを実装でき、かなり高速。**データ構造としても、ヒープの応用も色々あるようなので、Excel VBA だけで使える高性能なデータベースが必要な場合、非常に有力な選択肢になると思われる。

  • Excel VBA はただでさえ遅い（JS の10倍以上時間がかかっている）上に、数十万件以上の大量データを扱うことが結構あるので、間違っても安易にバブルソートなどの遅いソートを実装してはいけない。（まあソートメソッドさえ知っていれば、普通はそういうことは無いと思うが）

検証結果の実用性

実務では独自のソートをするとか、複数のキーでソートするとか、要素数が変動するとか、もっと複雑で、そう簡単ではないと思う。（その点、ヒープは要素の追加、削除にも強くて有能）

マシンスペック依存なので、計測した絶対値にもさほど意味がないが、ざっくりなベンチマークくらいには使えるかも？

個人的にはヒープが好きになった。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?