ChatGPT大先生にとあるAny関数を使ったソースコードを添削していただくと、大体HashSetにしたほうがO(1)だから、こっちの方がいいよと仰います。
本当なのかいろいろと試してみたいと思います。
素のままの検索速度の差
順序がランダムな10000の数字の配列を用意します。その中から0を探すことを1000回行ったときの速度を計測しました。
Any関数の場合
var list = Enumerable.Range(0,10000).OrderBy(i=>Guid.NewGuid()).ToArray();
var stopwatch = Stopwatch.StartNew();
foreach(var i in Enumerable.Range(0,1000))
{
var flag = list.Any(x => x == 0);
}
stopwatch.Stop();
Console.WriteLine($"処理時間:{stopwatch.ElapsedMilliseconds}ms");処理時間:43ms 処理時間:41ms 処理時間:41ms 処理時間:41ms 処理時間:42ms 処理時間:17ms 処理時間:14ms 処理時間:14ms 処理時間:13ms 処理時間:13ms
HashSetの場合
var list = Enumerable.Range(0,10000).OrderBy(i=>Guid.NewGuid()).ToArray();
var stopwatch = Stopwatch.StartNew();
foreach(var i in Enumerable.Range(0,1000))
{
var hashSet = list.ToHashSet();
var flag = hashSet.Contains(0);
}
stopwatch.Stop();
Console.WriteLine($"処理時間:{stopwatch.ElapsedMilliseconds}ms");処理時間:131ms 処理時間:121ms 処理時間:110ms 処理時間:123ms 処理時間:169ms 処理時間:114ms 処理時間:120ms 処理時間:153ms 処理時間:143ms 処理時間:134ms
個人的には既に意外ですが、まさかのAny関数の勝利でした。
毎回ToHashSetする方がパフォーマンスとしては悪いという結果になりました。
ちなみにToHashSet()をタイマーの外で行うと、さすがO(1) の実行速度です。
var list = Enumerable.Range(0,10000).OrderBy(i=>Guid.NewGuid()).ToArray();
var hashSet = list.ToHashSet();
var stopwatch = Stopwatch.StartNew();
foreach(var i in Enumerable.Range(0,1000))
{
var flag = hashSet.Contains(0);
}
stopwatch.Stop();
Console.WriteLine($"処理時間:{stopwatch.ElapsedMilliseconds}ms");処理時間:0ms 処理時間:0ms 処理時間:0ms 処理時間:0ms 処理時間:0ms 処理時間:0ms 処理時間:0ms 処理時間:0ms 処理時間:0ms 処理時間:0ms
配列の中に別の配列の要素が含まれるか
とある大きい配列の中に、別で用意した配列が含まれているかのチェックをよくやることがあり、これをChatGPT先生に聞くと、HashSetを使ったほうが良いという回答をよく貰います。
文章だと分かりづらいので、例をソースコードで示すと、下記のようになります。
var list1 = [0,1,2,3,4,5,6,7,8,9]; var list2 = [2,5]; // 自分が提案した方法 var list3 = list1.Where(x => list2.Any(y => x == y)); // ChatGPT先生のリファクタリング結果 var hashSet = list2.ToHashSet(); var list4 = list1.Where(x => hashSet.Contains(x));
実際の実務で使うコードは、オブジェクトの配列となるため、これよりも複雑ですが、大雑把に言えば、このようになります。もちろん配列の大きさ、検索するオブジェクトの位置によって実行速度は大きく変わってきますが、ここでは、大量のオブジェクトの中を検索するという前提で考えていきます。
Any関数を使う場合
var list = Enumerable.Range(0,10000).OrderBy(i=>Guid.NewGuid()).ToArray();
var list2 = Enumerable.Range(0,1000);
var stopwatch = Stopwatch.StartNew();
foreach(var i in Enumerable.Range(0,1000))
{
var flag = list.Any(x => list2.Any(y => y == x));
}
stopwatch.Stop();
Console.WriteLine($"処理時間:{stopwatch.ElapsedMilliseconds}ms");処理時間:182ms 処理時間:174ms 処理時間:172ms 処理時間:171ms 処理時間:181ms 処理時間:176ms 処理時間:175ms 処理時間:176ms 処理時間:181ms 処理時間:190ms
Any関数が二つあって一見、何をやってるのか非常に分かりにくいので、出来れば、これは避けたいです。
HashSetを使う場合
var list = Enumerable.Range(0,10000).OrderBy(i=>Guid.NewGuid()).ToArray();
var list2 = Enumerable.Range(0,1000);
var stopwatch = Stopwatch.StartNew();
foreach(var i in Enumerable.Range(0,1000))
{
var hash = list2.ToHashSet();
var flag = list.Any(x => hash.Contains(x));
}
stopwatch.Stop();
Console.WriteLine($"処理時間:{stopwatch.ElapsedMilliseconds}ms");処理時間:12ms 処理時間:7ms 処理時間:7ms 処理時間:7ms 処理時間:7ms 処理時間:7ms 処理時間:6ms 処理時間:6ms 処理時間:8ms 処理時間:10ms
！！
list2が大きい場合、list2をHashSetにする方が速くなりました。