Dictionaryの格納件数による速度低下検証

検索が超速なことで知られるDictionaryですが、
実はデータ件数が増えすぎると急に遅くなるという欠点もあります。

これがどの程度なのかを検証してみましょう。

検証ソースコード

Dictionaryの処理を「格納(Add)」「Key取得」「KeyからItem取得」に分け、
それぞれの処理時間を計測してみました。

なお、Windows11/Corei5/メモリ16G/Excel365 での検証です。

' Dictionary速度検証
Sub Dictionaryのデータ格納と要素アクセスの所要時間()

    Dim 開始時刻 As Double, 終了時刻 As Double

    ' 格納時間
    開始時刻 = Timer
    
    Dim ディクショナリ As Dictionary
    Set ディクショナリ = Getデータn件のDictionary(1000000)
    
    終了時刻 = Timer
    Debug.Print "格納時間：" & (終了時刻 - 開始時刻) & "秒"

    
    ' Keyの取得時間
    開始時刻 = Timer
    
    Dim x, key
    For Each key In ディクショナリ.Keys
        x = key
    Next

    終了時刻 = Timer
    Debug.Print "Key取得：" & (終了時刻 - 開始時刻) & "秒"

    ' Itemの取得時間
    開始時刻 = Timer

    For Each key In ディクショナリ.Keys
        x = ディクショナリ.Item(key)
    Next

    終了時刻 = Timer
    Debug.Print "Item取得：" & (終了時刻 - 開始時刻) & "秒"

End Sub

' 格納用関数
Function Getデータn件のDictionary(n As Long) As Dictionary
    
    Set Getデータn件のDictionary = New Dictionary
    
    Dim i As Long
    For i = 1 To n
        Getデータn件のDictionary.Add i, ""
    Next
    
End Function

検証結果

計測結果がこちらとなります。

データ件数	格納時間	Key取得	Item取得
10万件	0.1秒	0.0秒	0.1秒
20万件	0.3秒	0.0秒	0.3秒
30万件	0.8秒	0.0秒	0.8秒
40万件	1.8秒	0.0秒	2.2秒
50万件	3.4秒	0.0秒	4.5秒
60万件	5.5秒	0.0秒	7.3秒
70万件	8.2秒	0.0秒	10.9秒
80万件	11.1秒	0.0秒	15.2秒
90万件	14.7秒	0.0秒	19.9秒
100万件	19.5秒	0.0秒	25.6秒

格納・Item取得ともに、みごとに二乗に比例していますね。

近似曲線を引いてみると、二次曲線(放物線)とピッタリ一致しました。

Key取得（ただのForEach文）はすべて0であることからわかる通り、
時間がかかるのはKey-Itemの紐づけと取得のようです。

しかし流石はDictionaryというべきでしょうか、
10万件から1件検索を10万回やっても0.1秒というのはとんでもない速度です。

100万回の検索を30秒以内でこなせる機能自体が少ないので、
速度低下してもなお最速はDictionaryになってしまうことも多そうです。

※ KeyからItemを取得するのを検索と表現しましたが実際に行われているのはハッシュ計算です。

さてこの対策ですが、Dicitonaryを複数に分割するという方法が考えられます。

Dictionaryを小分けにした場合は、

• 100万件のデータを50万件のDictionary2個に分ける ⇒ 約3倍速
• 100万件のデータを30万件のDictionary3個に分ける ⇒ 約9倍速
• 100万件のデータを10万件のDictionary10個に分ける ⇒ 約100倍速

という速度向上効果を見込める計算になります。

ただし、Dictionaryを分けると当然Keyも分かれてしまうので、
存在チェックや検索が大変になってしまいます。

やみくもに件数で分けると、

• すべてのDictionaryからKeyを探す
• どのDictionaryにも入っていなかったらAdd

みたいな処理を書く羽目になってしまいますからね。

こうならないよう、例えば「Keyの頭文字で分ける」「Keyの桁数で分ける」など、
Dictionaryの分割に明確なルールをつけるとよいと思います。

なんなら分けたDictionaryを格納する親Dicitonaryを作れば、

Dic商品コード("A")("A10000")

のような記述で各Itemの取得ができるようになります。

このあたりの設計は腕の見せ所だと思いますので、
データの形式に合わせていろいろと仕様を考えてみてください。

おまけ：Keys(i)の速度低下検証

Dictionaryのよくある間違い記述として、

ディクショナリ.Keys(i)

というコードが挙げられます。

Keysは各キーにアクセスするプロパティではなく、
全Keyを一次元配列として取り出すメソッドである
ことに注意してください。

たまに見る↓のコード、一見正しいように見えますが、
このコードは配列をループの回数だけ毎回生成してしまうコードです。

Dim x, i
For i = 0 To ディクショナリ.Count - 1
    x = ディクショナリ.Keys(i)
Next

　
この間違いによる速度低下がどの程度かを見てみましょう。

' Dictionary速度検証
Sub DictionaryのIndexアクセスによる速度低下検証()

    Dim ディクショナリ As Dictionary
    Set ディクショナリ = Getデータn件のDictionary(50000)
    
    Dim 開始時刻 As Double, 終了時刻 As Double
    
    ' Keyの取得時間
    開始時刻 = Timer
    
    Dim x, i
    For i = 0 To ディクショナリ.Count - 1
        x = ディクショナリ.Keys(i)
    Next

    終了時刻 = Timer
    Debug.Print "Key取得：" & (終了時刻 - 開始時刻) & "秒"

End Sub

データ件数	格納時間
1万件	1.0秒
2万件	4.1秒
3万件	13.3秒
4万件	42.5秒
5万件	74.5秒

お話にならない速度低下ですね(´∀｀;)

よく見るとわかりますが、先ほどとデータ件数の桁が違います。

こちらも二乗に比例する速度低下になっていますので、
おそらく10万件では30分をゆうに超えてくると思います。

しかもこれ、ソースを見てわかる通りただKeyを取得しただけでこれです。
KeyからItemを取得するなどは一切していません。

この記述による速度低下はかなり致命的ですから、
間違ってもこの記述をしないよう気を付けましょう。

この記述で書かれたコードがネット上にも割とありますので、
持ってきたコードがこうなっていないかのチェックもお忘れなく。

詳しくはこちらをどうぞ
www.limecode.jp