LoginSignup
63
61

More than 5 years have passed since last update.

一覧で検索するならListではなくHashSetにしましょう

Last updated at Posted at 2014-07-24

Javaで一覧に検索(contains)をかけるならListではなくSet使うのですが、
きっとC#も同じだよなーと思い計ってみました。

10万の文字列から重複チェックをしながら新しい一覧を作るのにかかった時間です。

メソッド 1回目 2回目 3回目
HashSet#Contains 37ms 29ms 22ms
List#Contains 80767ms 83324ms 88343ms
List#BinarySearch 267ms 321ms 437ms

結論:
順番を気にしない一覧ならListではなくHashSetを使いましょう。
どうしてもListならBinarySearchにしましょう。
100件くらいなら差はないんでしょうけど。

contains.cs
static void Main(string[] args)
{
    Random random = new Random();

    // テストデータ
    List<string> sample = new List<string>();
    for (int i = 0; i < 100000; i++)
    {
        string randomString = Convert.ToBase64String(BitConverter.GetBytes(random.Next()));
        sample.Add(randomString);
    }

    Stopwatch stopwatch;
    Console.WriteLine("===BEGIN===");

    // HashSet#Contains
    stopwatch = Stopwatch.StartNew();
    HashSet<string> set = new HashSet<string>();
    foreach (string str in sample)
        if (!set.Contains(str))
            set.Add(str);
    stopwatch.Stop();
    Console.Write("HashSet#Contains: ");
    Console.WriteLine(stopwatch.ElapsedMilliseconds);

    // List#Contains
    stopwatch = Stopwatch.StartNew();
    List<string> list = new List<string>();
    foreach (string str in sample)
        if (!list.Contains(str))
            list.Add(str);
    stopwatch.Stop();
    Console.Write("List#Contains: ");
    Console.WriteLine(stopwatch.ElapsedMilliseconds);

    // List#BinarySearch
    stopwatch = Stopwatch.StartNew();
    List<string> blist = new List<string>();
    foreach (string str in sample)
        if (blist.BinarySearch(str) < 0)
            blist.Add(str);
    Console.Write("List#BinarySearch: ");
    Console.WriteLine(stopwatch.ElapsedMilliseconds);

    Console.WriteLine("=== END ===");
    Console.Read();

}
63
61
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
63
61