解析エンジニアの自動化 blog

コツコツと自動化した方法を残す blog

VBA による大量データの高速ソート




こんにちは。
仕事の自動化にやりがいと達成感を感じるガッくんです。




この記事の目次




目的


ファイル出力の記事を書きたいのですが、ファイル出力するためのテキスト処理を作成したところ、とんでもなく処理に時間がかかり、ファイル出力の前に色々と高速化について取り組んでます。

この記事では既に定説のようになりつつあるソートの高速化を検証します。

結論としては Excel のソート機能を VBA から動作させるのが一番早いということになりました。
この記事では下の①〜④の実行時間を調べました。
①For 〜 Next の空回し速度
クイックソートによるソート
③ソート用データのコピー
④シート上でのソート




関数

For 〜 Next の空回し

そもそも For 〜 Next の速度を知らなかったので、確認のためにやってみました。

ソースコード
〜For 〜 Next の空回し〜


Sub For文の実行時間について()
   
    ' 開始時刻の記録
    開始時刻 = Time
   
    ' 繰り返し回数の設定
    ' この設定を 50,000 ~ 1,000,000 まで変更した
    データ数 = 50000
   
    ' カウンター
    cnt = 1
   
    ' 繰り返し処理
    For i = 1 To データ数
       
        ' 進捗出力
        If (i / データ数) * 100 > cnt Then
            Debug.Print Application.WorksheetFunction.RoundDown((i / データ数) * 100, 0) & " % 完了  Time: " & Time
            cnt = cnt + 1
        End If
       
        DoEvents
       
    Next i
   
    ' 終了時刻の記録
    終了時刻 = Time
   
    ' プログラムの実行時間を計算
    実行時間 = DateDiff("s", 開始時刻, 終了時刻)
   
    ' 実行時間をイミディエイトウィンドウに出力
    Debug.Print "Start: " & 開始時刻 & vbNewLine & "End: " & 終了時刻 & vbNewLine & "実行時間: " & 実行時間 & " sec"
   
End Sub

ソースコード①の実行時間

ただの空回しなのになかなか時間がかかりました。100万回の繰り返しは実用的とは言えない状況でした。
For 〜 Next の空回しにかかった時間の表とグラフを図1に示します。

図1 For 〜 Next 空回しの実行時間とグラフ

ソート用データ

今回、検証のために用意したデータを図2に示します。

図2 ソート用データ

クイックソート

有名なアルゴリズムです。
For 〜 Next の空回し時間から期待は薄いですが、やってみます。

ソースコード
クイックソート


'------------------------------------------------------------------------------
' 引数1:配列1(ソートする2次元配列)
' 引数2:定数1(ソート対象最小行)
' 引数3:定数2(ソート対象最大行)
' 引数4:定数3(配列1におけるソートキー列)
' 動作:引数1の配列で引数2から引数3までの行を引数4の列をキーにして並び変える。
'------------------------------------------------------------------------------
Sub クイックソート(ByRef data, Min, Max, key)
   
    Dim i As Double
    Dim j As Double
    Dim k As Double
   
    Dim 基準1 As Variant
    Dim 基準2 As Variant
   
    基準1 = CDbl(data(Int((Min + Max) / 2), key))
    i = Min
    j = Max
   
    Do
        Do While CDbl(data(i, key)) < 基準1
            i = i + 1
            DoEvents
        Loop
        
        Do While CDbl(data(j, key)) > 基準1
            j = j - 1
            DoEvents
        Loop
       
        If i >= j Then Exit Do
        For k = LBound(data, 2) To UBound(data, 2)
            基準2 = data(i, k)
            data(i, k) = data(j, k)
            data(j, k) = 基準2
        Next
        DoEvents
        i = i + 1
        j = j - 1
    Loop
   
    If (Min < i - 1) Then
        Call クイックソート(data, Min, i - 1, key)
    End If
   
    If (Max > j + 1) Then
        Call クイックソート(data, j + 1, Max, key)
    End If
   
End Sub

ソースコード②の実行時間

やはり100万回の繰り返しは無謀でした。
クイックソートにかかった時間の表とグラフを図3に示します。

図3 クイックソートの実行時間とグラフ

シート上でのソート

Excel のソート機能を VBA から動作させます。
実際にプログラムに組み込む事を考えると、ソート前のデータを別シートにコピーして、コピーデータをソートする事にします。
という事で、コピペのスピードから確認します。

ソースコード
〜ソート用データコピー〜


Sub ソート用データコピー()
    ' 繰り返し回数の設定
    ' この設定を 50,000 ~ 1,000,000 まで変更した
    データ数 = 1000000
   
    ' 開始時刻の記録
    開始時刻 = Time
   
    ' 実行時間をイミディエイトウィンドウに出力
    Debug.Print
   
    ' 並び変え用配列の取得
    With ThisWorkbook.Sheets("ソート用データ")
       
        並び変え用配列 = .Range(.Cells(4, 2), .Cells(4 + データ数 - 1, 4))
       
    End With
   
    ' 並び変え用配列の出力
    With ThisWorkbook.Sheets("シートソート")
       
        .Range(.Cells(4, 2), .Cells(4 + UBound(並び変え用配列, 1) - 1, 2 + UBound(並び変え用配列, 2) - 1)) = 並び変え用配列
       
    End With
   
    ' 終了時刻の記録
    終了時刻 = Time
   
    ' プログラムの実行時間を計算
    実行時間 = DateDiff("s", 開始時刻, 終了時刻)
   
    ' 実行時間をイミディエイトウィンドウに出力
    Debug.Print "データ数: " & データ数 & vbNewLine & _
                "Start: " & 開始時刻 & vbNewLine & _
                "End: " & 終了時刻 & vbNewLine & _
                "実行時間: " & 実行時間 & " sec" & vbNewLine
   
End Sub

ソースコード③の実行時間

コピーの処理だけなので、100万行のデータコピー処理にかかった時間は微妙です。
50万行のデータコピーまでならなんとか速いと言えるかどうかです。

図4 ソート用データコピーの実行時間とグラフ

ソースコード
〜シート上でのソート〜


Sub シートソート()
   
    ' 繰り返し回数の設定
    ' この設定を 50,000 ~ 1,000,000 まで変更した
    データ数 = 1000000
   
    ' 並び変えの Key 列の設定
    ' この設定を 1 ~ 3 まで変更した
    Key列 = 1
   
    ' 開始時刻の記録
    開始時刻 = Time
   
    ' 並び変え用配列の取得
    With ThisWorkbook.Sheets("ソート用データ")
       
        並び変え用配列 = .Range(.Cells(4, 2), .Cells(4 + データ数 - 1, 4))
       
    End With
   
    ' コピー出力先シートの初期化
    With ThisWorkbook.Sheets("シートソート")
       
        .Range(.Cells(4, 2), .Cells(4 + UBound(並び変え用配列, 1) - 1, 2 + UBound(並び変え用配列, 2) - 1)).ClearContents
       
    End With
   
    ' 並び変え用配列の出力
    With ThisWorkbook.Sheets("シートソート")
       
        .Range(.Cells(4, 2), .Cells(4 + UBound(並び変え用配列, 1) - 1, 2 + UBound(並び変え用配列, 2) - 1)) = 並び変え用配列
       
        Set 並び変え範囲 = .Range(.Cells(4, 2), .Cells(4 + UBound(並び変え用配列, 1) - 1, 2 + UBound(並び変え用配列, 2) - 1))
       
        Set 並び変えKey = .Range(.Cells(4, 2 + Key列 - 1), .Cells(4 + UBound(並び変え用配列, 1) - 1, 2 + Key列 - 1))
       
    End With
   
    ' ソートの条件設定
    With ThisWorkbook.Sheets("シートソート")
       
        .Sort.SortFields.Clear
       
        .Sort.SortFields.Add key:=並び変えKey _
            , SortOn:=xlSortOnValues, Order:=xlAscending, DataOption:=xlSortNormal
       
    End With
   
    ' ソートの実行
    With ActiveWorkbook.Worksheets("シートソート").Sort
       
        .SetRange 並び変え範囲
        .Header = xlNo
        .MatchCase = False
        .Orientation = xlTopToBottom
        .SortMethod = xlPinYin
        .Apply
       
    End With
   
    ' 終了時刻の記録
    終了時刻 = Time
   
    ' プログラムの実行時間を計算
    実行時間 = DateDiff("s", 開始時刻, 終了時刻)
   
    ' 実行時間をイミディエイトウィンドウに出力
    Debug.Print "データ数: " & データ数 & vbNewLine & _
                "Start: " & 開始時刻 & vbNewLine & _
                "End: " & 終了時刻 & vbNewLine & _
                "実行時間: " & 実行時間 & " sec" & vbNewLine
   
End Sub

ソースコード④の実行時間

事前にクイックソートでのソートをやっていたのですっごく速く感じましたが、微妙な時間は必要なようです。
ソート用データには Double 型の値を1列目に入れているので1列目に key にソートするとやはり整数型の値を key にするよりは時間がかかります。

図5 シート上でのソートの実行時間とグラフ

最後に

クイックソートとシート上でのソートはやはりシート上でのソートの方が実行時間は短いようです。
図6に結果をまとめ表とグラフを示しますが、一目瞭然でシート上でのソートが速いです。

図6 シート上でのソートの実行時間とグラフ




コメント

シート上でのソートは Excel が 1,048,576 行までしかないので、 1,048,576 行を超える配列は扱えないのが難点ですね。




以上