3

私は与えられたlistitemクラスを持っています:

class Vector
{
    public int Column { get; set; }
    public int Row { get; set; }
    public int TableID { get; set; }

    public Vector(int column, int row, int tableID)
    {
        TableID = tableID;
        Row = row;
        Column = column;
    }
}

後で、このアイテムの型付きリストがあり、特定のベクトル (列、行、テーブル) がこのリストに既に追加されているかどうかを確認したいと考えています。もちろん、簡単な解決策：

    var items = new List<Vector>();
    items.Add(new Vector(1, 2, 3));
    items.Add(new Vector(5, 6, 7));

    for (int i = 0; i < 1000; i++)
    {
        if (items.Any(e => e.Column == 1 && e.Row == 2 && e.TableID == 3))
        {
            // do something
        }
    }

はい、機能していますが...リスト内のアイテムが増えるにつれて、一致するアイテムを見つけるためにすべてのアイテムを列挙する必要があるため、指数関数的に遅くなります。

最後に私の質問は次のとおりです。

Can you recommend other data structure to allow "fast contains"? I mean at least linear algorithm. Any will do, I need only store 3 related int and check the containment later.

4

5 に答える 5

2

「高速包含」を許可する他のデータ構造を推奨できますか?

すべてのベクトルは一意でなければならないため、 を使用して、適切なメソッドとHashSet<Vector>を実装できます。GetHashCodeEquals

class Vector 
{
    public int Column { get; set; }
    public int Row { get; set; }
    public int TableID { get; set; }

    public Vector(int column, int row, int tableID)
    {
        TableID = tableID;
        Row = row;
        Column = column;
    }

    public override int GetHashCode()
    {
        unchecked 
        {
            int hash = 17;
            hash = hash * 23 + Column.GetHashCode();
            hash = hash * 23 + Row.GetHashCode();
            hash = hash * 23 + TableID.GetHashCode();
            return hash;
        }
    }

    public override bool Equals(object obj)
    {
        if (obj == null || !(obj is Vector)) return false;
        Vector v2 = (Vector)obj;
        return Column == v2.Column && Row == v2.Row && TableID == v2.TableID;
    }
}

私の意見では、これは十分に速いはずです。

HashSet<Vector> items = new HashSet<Vector>();
bool isNew = items.Add(new Vector(1, 2, 3));
isNew = items.Add(new Vector(5, 6, 7));
isNew = items.Add(new Vector(5, 6, 7)); // false
于 2013-03-13T13:39:46.703 に答える
1

System.Collections.Generic.HashSetこれは、 （。Net 4.0以降を使用している場合）の完璧なユースケースに近いように聞こえます。

クラスにIEquatableを実装する必要があります。また、GetHashCodeの実装には少し注意する必要があります。これは、3つのコンポーネントの単純なxorにより、多くのハッシュ衝突が発生する可能性があるためです。同じテーブルが常に衝突します。それをより良くする方法のヒントについては、CRC32アルゴリズムを見てください。

あるいは、同じ結果を達成するための手っ取り早い方法は、Vector継承元を作成Tuple<int, int, int>し、フレンドリーな名前付きプロパティをプロキシにすることですItem1。MicrosoftはItem2、Item3適切なハッシュの実装についてすでに心配しています。

于 2013-03-13T13:31:14.733 に答える