数万件のデータの中から、条件に合う1件を探す処理を書いたことはないでしょうか。Forループで1件ずつ照合するコードは、書き方としては素直です。ただし件数が増えると、極端に遅くなることがあります。
前回の記事「バブルソートとクイックソートの速度差を実測比較」では、ソートの実装によって速度が大きく変わることを実測しました。今回はVBAシリーズの最終回として、「検索」における同じ問題と、その解決策である連想配列（Dictionaryオブジェクト）を扱います。
Forループでの検索が遅くなる理由
あるデータの一覧から、特定の1件を探す処理を考えます。Forループで先頭から1件ずつ比較していく方法（線形探索）は、最悪の場合、件数と同じ回数だけ比較が必要です。
問題は、この検索を何度も繰り返すケースです。たとえば6万件のデータに対して、別の6万件それぞれについて該当する行を探す、という処理をすると、比較の回数は最大で6万×6万回、つまり36億回近くに達します。件数が増えるほど、この回数は掛け算的に膨らみます。
以前紹介した、新卒時代に書き直した激重マクロにも、実はこの検索の遅さが関係していました。顧客データと車両データを突き合わせて該当行を抽出する処理で、片方のデータを1件ずつForループで探していたためです。
連想配列（Dictionary）ならキーで直接探せる
VBAには、キーと値の組み合わせでデータを持てる「Dictionaryオブジェクト」があります。あらかじめキーを登録しておけば、Existsメソッドでそのキーが存在するかどうかを直接調べられます。先頭から順に見ていく必要がありません。詳しい仕様はMicrosoft LearnのExistsメソッドのページにまとまっています。
連想配列の基本的な使い方は、以前の記事「個数を数える3つの方法とその速度比較」でも触れています。
Sub DictionaryExistsDemo()
Dim dict As Object
Set dict = CreateObject("Scripting.Dictionary")
dict.Add 1001, "Aさん"
dict.Add 1002, "Bさん"
dict.Add 1003, "Cさん"
If dict.Exists(1002) Then
MsgBox "1002は存在します：" & dict(1002)
Else
MsgBox "1002は存在しません"
End If
End Sub実際に実行すると、次のように動作します。
検証コードの考え方
今回の検証では、線形探索とDictionaryのキー検索を、同じ条件で比較しました。検索する部分だけを取り出すと、次のようになります。
' 線形探索
Dim found As Boolean
found = False
For i = 1 To UBound(masterIDs)
If masterIDs(i) = targetID Then
found = True
Exit For
End If
Next i' Dictionaryのキー検索
found = dict.Exists(targetID)線形探索は、先頭から1件ずつ照合するため、目的のデータが後ろにあるほど時間がかかります。Dictionaryは内部でキーをハッシュ化して管理しているため、件数が増えてもキー検索1回あたりの時間はほとんど変わりません。
実測結果
6万件のデータから対象を探す処理を、6万回繰り返した場合の所要時間を比較しました（3回実行した平均値）。
| 検索方法 | 所要時間（平均） |
|---|---|
| 線形探索（Forループ） | 32.333秒 |
| Dictionaryのキー検索 | 0.221秒 |
同じ処理を、Dictionaryを使うだけで約146倍速くできました。
線形探索は、検索1回あたり平均で件数の半分（3万件）を比較すると考えられるため、6万回の検索では合計およそ18億回の比較が発生します。一方Dictionaryは、キーの登録に6万回、検索に6万回、合計12万回程度の処理で済みます。比較回数だけで見ると差はさらに大きくなりますが、Dictionaryのキー検索1回あたりの処理（ハッシュの計算など）は単純な値比較より重いため、実際の速度差は146倍程度に収まったと考えられます。
速度ではなく、実務でよく書く「マスタ参照＋存在チェック」の書き方を知りたいときは、【VBA】マスタ参照の存在チェックをDictionaryに置き換えるを参照してください。Foundフラグの線形探索をExistsに書き換えたときの、結果の違いをまとめています。
まとめ
この記事で、VBAシリーズは全3回で完結です。
1話目「処理が遅い本当の原因｜シート操作が重くなる仕組み」で紹介した、新卒時代の激重マクロのエピソードには、今回扱った検索の遅さも関係していました。シートの操作、ソートの実装、検索の方法。それぞれの場面で「何をやっているか」を理解しておくと、AIに実装を任せる場合でも、処理が遅くなっていないかに気づきやすくなります。
コメント