【初心者】O記法に縛られず、具体例を計測して現実的なデータに合わせようという話
Dictionary<string,T> vs. (string, T)[]
文字列をキーにして何らかの値を保持しており、値の検索を行いたいという、まぁまぁありそうなケースを考えます。
配列の検索はO(n)、DictionaryはO(1)なので、Dictionaryの方がO記法では有利ですが、要素数が多ければ有利という話でしかありません。
要素数が少ない場合を実際に見てみましょう。
計測には一般的な手法としてBenchmarkDotNetを使用します。
internal class Program { private static void Main(string[] args) { BenchmarkRunner.Run<TestClass>(); } } [MemoryDiagnoser] public class TestClass { private (string Key, int value)[] _array; private Dictionary<string, int> _dictionary; private string[] _keys; private const int LoopCount = 100000; private const int ElemNum = 30; // ランダムな文字列を頭に付ける（雑にGUIDなのであんまり長くしない） private const int KeyPrefixLength = 10; [GlobalSetup] public void Setup() { _array = Enumerable.Range(0, ElemNum).Select(i => { var prefix = Guid.NewGuid().ToString().Substring(0, KeyPrefixLength); return (prefix + i, i); }).ToArray(); _dictionary = _array.ToDictionary(x => x.Key, x => x.value); _keys = _array.Select(x => x.Key).ToArray(); } [Benchmark] public void ArraySearch1000() { for (int i = 0; i < LoopCount; i++) { var key = _keys[i % _keys.Length]; int value = -1; foreach (var kv in _array) { if (kv.Key == key) { value = kv.value; break; } } } } [Benchmark] public void DictionarySearch1000() { for (int i = 0; i < LoopCount; i++) { var key = _keys[i % _keys.Length]; int value = -1; if (_dictionary.TryGetValue(key, out value)) { value = _dictionary[key]; } } } }
大したコードではありませんが、（nfadopfuhdfuw1, 1）, （yrgfscndsafu2, 2）,…みたいな配列およびDictionaryを作って、何度も何度も文字列のキーを参照して目的の数値を探します。
ランダムな文字列は、文字列を現実的な長さにした方がいいかなと思っただけなのであまり関係無いです。（嘘です。意味はあります。後で説明します。）
結果
ElemNumを10-40に変えてみて、それぞれの計算時間です。
| Method | Mean | Error | StdDev | Gen 0 | Gen 1 | Gen 2 | Allocated |
|---|---|---|---|---|---|---|---|
| ArraySearch_ElemNum10 | 1.967 ms | 0.0056 ms | 0.0052 ms | - | - | - | - |
| ArraySearch_ElemNum20 | 2.979 ms | 0.0082 ms | 0.0073 ms | - | - | - | - |
| ArraySearch_ElemNum30 | 4.420 ms | 0.0294 ms | 0.0275 ms | - | - | - | - |
| ArraySearch_ElemNum40 | 5.804 ms | 0.0151 ms | 0.0141 ms | - | - | - | - |
| DictionarySearch_ElemNum10 | 4.362 ms | 0.0134 ms | 0.0125 ms | - | - | - | - |
| DictionarySearch_ElemNum20 | 4.137 ms | 0.0158 ms | 0.0148 ms | - | - | - | - |
| DictionarySearch_ElemNum30 | 4.446 ms | 0.0065 ms | 0.0057 ms | - | - | - | - |
| DictionarySearch_ElemNum40 | 3.996 ms | 0.0147 ms | 0.0137 ms | - | - | - | - |
結果の解釈
ElemNum=30でいい勝負です。それ未満では配列の方が有利ですね。偶然インデックスの大きい検索ばかり行われたら、ElemNum=15くらいでいい勝負でしょうか？
O(n)やO(1)はまぁまぁ正しそうですが、でもこの結果なら、Dictionaryの方が速い！と単純に解釈するべきではないですよね。
とはいえ、めちゃくちゃ大きな差でもないですから、Dictionaryがダメ、ということでもないです。
オーダーはオーダーでしかなく絶対的な指標ではないので、色んな条件を踏まえて、オーダーに反する選択をするのも許されるよ、という話です。
おまけ：文字列のPrefixはなんだったのか
試しに、ElemNum=30で固定し、KeyPrefixLengthを0-30に変えて計測してみましょう。
| Method | Mean | Error | StdDev | Gen 0 | Gen 1 | Gen 2 | Allocated |
|---|---|---|---|---|---|---|---|
| ArraySearch_Prefix0 | 4.357 ms | 0.0155 ms | 0.0145 ms | - | - | - | - |
| ArraySearch_Prefix10 | 4.420 ms | 0.0294 ms | 0.0275 ms | - | - | - | - |
| ArraySearch_Prefix20 | 4.400 ms | 0.0240 ms | 0.0224 ms | - | - | - | - |
| ArraySearch_Prefix30 | 4.400 ms | 0.0231 ms | 0.0216 ms | - | - | - | - |
| DictionarySearch_Prefix0 | 3.562 ms | 0.0692 ms | 0.0769 ms | - | - | - | - |
| DictionarySearch_Prefix10 | 4.446 ms | 0.0065 ms | 0.0057 ms | - | - | - | - |
| DictionarySearch_Prefix20 | 5.012 ms | 0.0145 ms | 0.0136 ms | - | - | - | - |
| DictionarySearch_Prefix30 | 5.465 ms | 0.0331 ms | 0.0310 ms | - | - | - | - |
DictionaryはPrefixが長くなると増えてますが、Arrayの方は増えてないですね。
これはDictionaryの検索のために使用されるGetHashCodeが意外と重くて、文字列が長いだけ重くなっていくということですね。
まぁこんな感じで、オーダーは大事だけど、実際には色んな要素があるので、計算時間なんか計測しなきゃわからないです。
安易に決めつけないようにしましょう。
もちろん、要素数1000とかで配列使うわけないので、オーダーも大事ですよ。
