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
        }
    }

是的，它正在工作，但是......我担心随着列表中越来越多的项目它会呈指数级增长，因为你必须枚举所有项目才能找到匹配的项目。

最后我的问题是：

你能推荐其他数据结构来允许“快速包含”吗？我的意思是至少线性算法。任何都可以，我只需要存储 3 个相关的 int 并稍后检查容器。

4

5 回答 5

5

您可以IEquatable<T>为您的类（方法public bool Equals(T other)和public override int GetHashCode()）实现接口并使用 HashSet 来存储唯一项：

class Vector :  IEquatable<Vector>
{
    /*Some fields and methods*/

    public bool Equals(Vector other)
    {
        if (ReferenceEquals(other, null)) return false;

        if (ReferenceEquals(this, other)) return true;

        return Column.Equals(other.Column) && Row.Equals(other.Row) && TableID.Equals(other.TableID);
    }

    public override int GetHashCode()
    {
        return Column.GetHashCode() ^ Row.GetHashCode() ^ TableID.GetHashCode();
    }
}

并使用哈希集：

var set = new HashSet<Vector>();
    var vect = new Vector { ... };
set.Add(vect);
于 2013-03-13T13:26:12.920 回答
2

你能推荐其他数据结构来允许“快速包含”吗？

由于所有向量都必须是唯一的，因此您可以使用 aHashSet<Vector>并实现适当的方法GetHashCode和Equals：

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 实现要小心，因为三个组件的简单异或可能会导致大量哈希冲突，例如第 1 行第 2 列和第 2 行第 1 列同一张桌子总是会发生碰撞；查看 CRC32 算法以获取有关如何做得更好的提示。

或者，实现相同结果的一种快速而肮脏的方法是让您Vector继承自Tuple<int, int, int>并让友好的命名属性成为 的代理Item1，Item2并且Item3- 微软已经担心实现一个好的散列。

于 2013-03-13T13:31:14.733 回答
0

一种方法是从值构造一个键或散列，并使用它将向量存储在散列表中。

另一种方法是对数组进行排序，然后使用二进制方法作为 contains，它为 contains 方法提供 log(n) 而不是线性 n。

于 2013-03-13T13:26:29.033 回答
0

您可以尝试使用哈希表，如果正确实施，访问时间是恒定的（在完美世界中）或使用有序二叉树，查找值的最大步骤数是 log base 2 n 其中 n 是元素数，并且对数的结果被四舍五入，在现实生活中，它的大部分时间都比对数结果的步数少，这是正确的，前提是它被正确实现并且你有一个平衡的二叉树

哈希表比二叉树更快但更难实现，所以由你决定

于 2013-03-13T13:28:19.297 回答