QA@IT

C#でList内の要素を高速で検索したい

36916 PV

現在、C#を勉強しているのですが、List内の要素を高速で検索したいという事が出てきました。
しかしこれをどうやって実装すればいいかわかりません。

一応私の試した方法を書かせていただきます。

まず私はListではなくDictionaryを使おうと考えました。
といいますのも、検索したい値をKeyとしたDictionaryであれば、foreach等でListを回すよりも高速に検索できると考えたからです。
しかしここで、問題がありました。というのも検索したい値は重複するのです。
DictionaryはKeyの重複は許可されないので、エラーになると推測されます。

DBに例えると、DBのカラムにindexを張ってそれに対してWhereする様な事を、C#でやりたいという事です。

ご回答いただけると助かります。よろしくお願いします。

回答

単に重複登録するとエラーがでて面倒だというだけなら、HashSetを使う手はありますが、
http://qa.atmarkit.co.jp/q/3405#answer_16241

なんとなく Listにしたいものが単純な値ではなく、クラスなり構造体という事なのだと思います。

件数が多くないなら、DictionaryのValueをListにしてインデックスのように持つというのはどうでしょう。

/// <summary>データの器となるクラス</summary>
public class Person {
    public string Id;
    public string FirstName;
    public string LastName;
}


public class MainClass {

    public List<Person> Sample(List<Person> persons, string searchLastName) {

        // Dictionary作成
        var dic = new Dictionary<String, List<Person>>();
        persons.ForEach(x => {
            // DictionaryにこのLastNameがまだ無ければリストを作成して登録
            if (!dic.Keys.Contains(x.LastName)) dic[x.LastName] = new List<Person>();
            // Listに追加
            dic[x.LastName].Add(x);
        });

        // 検索して見つかったListを返す。
        if (dic.Keys.Contains(searchLastName)) return dic[searchLastName];
        return null;
    }
}

Sampleメソッドに、元となるリストと、検索したいLastNameを渡すとマッチしたもののリストが返ります。
ここではDictionaryを毎回作ってますが、どっかで作って保持する形がいいでしょうね。
その場合 返したListをいじられるとDictionary内のListにも影響がでると思うので、Listを複製して返すことも検討してください。

編集 履歴 (1)
  • おお・・・なるほど・・・Dictionaryにリストを持たせて、それで結果を返すという事ですね。シンプルですし、実際に使ってみると早かったです。この方法でいこうと思います、ありがとうございました。 -

リストをソートしてバイナリサーチでどうでしょう。

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    public class Person
    {
        public Person(int id, string name)
        {
            Id = id;
            Name = name;
        }

        public int Id { get; set; }
        public string Name { get; set; }

        private class PersonComparer : IComparer<Person>
        {
            public int Compare(Person x, Person y)
            {
                return x.Id.CompareTo(y.Id);
            }
        }

        public static readonly IComparer<Person> Comparer = new PersonComparer();
    }

    static void Main(string[] args)
    {
        // 100 個の要素で 1 つの値が 10 個ずつ重複している
        var list = new List<Person>(
            Enumerable.Range(0, 100).Select((i) => new Person(i % 10, string.Format("Id{0:000}", i)))
        );

        // ソート
        list.Sort(Person.Comparer);

        // 検索する値
        int val = 2;

        // バイナリサーチ
        int index = list.BinarySearch(new Person(val, string.Empty), Person.Comparer);

        if (index < 0)
        {
            // 見つからなかった
            Console.WriteLine("notfound");
        }
        else
        {
            // 検索値の開始位置まで戻る
            for (; index >= 0; index--)
            {
                if (list[index].Id != val)
                {
                    break;
                }
            }

            // 戻りすぎているので進める
            index++;

            // 検索値の終了位置まで進む
            for (; index < list.Count; index++)
            {
                var item = list[index];

                if (item.Id != val)
                {
                    break;
                }

                // 検索にヒットしたインデックスと値を表示
                Console.WriteLine(string.Format("{0} => {1} {2}", index, item.Id, item.Name));
            }
        }

        Console.WriteLine("--- push any key ---");
        Console.ReadKey();
    }
}
編集 履歴 (1)
  • これはあらかじめデータがソートされているという前提になるので flied_onion さんの Dictionary に List を持たせる方法の方が良いです -
  • 要素にオブジェクトを使うように書き換えました -
  • バイナリサーチというメソッドがあったのですね。ソートされている場合は、ContainsよりもBinarySearchの方が早いそうですね、勉強になりました。今回はこの方法を使いませんでしたが、ソートされたリストを検索するさいには、この方法でいこうと思います。ありがとうございました。 -

性能的にどうなのかわかりませんが(まともに動作するのかどうかもわかりませんが・・・)、GetHashCode で無理やり重複させなくするのとかはどうなんでしょうかね?

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    public class Person
    {
        public Person(int id, string name)
        {
            Id = id;
            Name = name;
            Dummy = 0;
        }

        private Person(int id, string name, int dummy)
        {
            Id = id;
            Name = name;
            Dummy = dummy;
        }

        public static Person Begin(int id)
        {
            return new Person(id, string.Empty, -1);
        }

        public static Person End(int id)
        {
            return new Person(id, string.Empty, +1);
        }

        public int Id { get; set; }
        public string Name { get; set; }
        public int Dummy { get; set; }
    }

    class PersonComparer : IComparer<Person>
    {
        public int Compare(Person x, Person y)
        {
            if (x.Id < y.Id)
            {
                return -1;
            }
            if (x.Id > y.Id)
            {
                return +1;
            }
            if (x.Dummy < y.Dummy)
            {
                return -1;
            }
            if (x.Dummy > y.Dummy)
            {
                return +1;
            }

            return x.GetHashCode().CompareTo(y.GetHashCode());
        }
    }

    static void Main(string[] args)
    {
        var list = new SortedSet<Person>(new PersonComparer());

        for (var i = 0; i < 100; i++)
        {
            list.Add(new Person(i%10, string.Format("Id{0:000}", i)));
        }

        Console.WriteLine("Count: " + list.Count);

        Console.WriteLine("\nAll");

        foreach (var item in list)
        {
            Console.WriteLine(string.Format("  {0} => {1}", item.Id, item.Name));
        }

        Console.WriteLine("\nId = 2..3");

        foreach (var item in list.GetViewBetween(Person.Begin(2), Person.End(3)))
        {
            Console.WriteLine(string.Format("  {0} => {1}", item.Id, item.Name));
        }

        Console.WriteLine("--- push any key ---");
        Console.ReadKey();
    }
}
編集 履歴 (0)
  • 追加時に並べたものも持ってしまうのは面白いですね。
    まだコードを見ただけの印象でしかないですが、GetHashCodeはEqualsとともにオーバーライドされることがあるので、その時にComparerで矛盾が起きないかが少し気になっています。(コードに影響が出るかまではみれていませんが、一意を期待してGetHashCodeを使っていたのにオーバーライドされてて予期せず同じとされていたなど)
    -
  • そもそも既定の実装でも一意な値を返すことは保証されていませんでした・・・ http://msdn.microsoft.com/ja-jp/library/system.object.gethashcode%28v=vs.100%29.aspx "GetHashCode メソッドの既定の実装では、異なるオブジェクトに対してそれぞれ一意な値が返されることは保証されません" -
  • Hashアルゴリズムによりますが、大きな素数で割ったあまりをハッシュ値にしているようなケースでは、その素数よりも多くの要素を用意すれば衝突は起こる事になります。たとえば (4294967296L).GetHashCode() == (1L).GetHashCode() は Trueです。値はぶん回して比較して見つけました。 -
  • 普通のオブジェクトの GetHashCode なら C のポインタのように CLR がオブジェクトを識別するためのキー的な何かが返るかなーと思ったのですが、一意性のために使うべきではないみたいですね -
  • なるほど、GetHashCodeというメソッドがあったのですね、勉強になりました。この方法もありだとはおもうのですが、少し直感的ではないか思ったので、今回は使いませんでした。ですが、もっと複数のメンバ変数が絡んだKeyを使う場合等には、この方法を使わせていただこうと思います。ありがとうございました。 -
ウォッチ

この質問への回答やコメントをメールでお知らせします。