写入快速包含列表的方法，列表项是一个向量

本文关键字：列表 向量 一个 包含 方法 | 更新日期: 2023-09-27 18:03:37

我有给定的列表项类:

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并稍后检查包含

写入快速包含列表的方法，列表项是一个向量

您可以为您的类(方法public bool Equals(T other)和public override int GetHashCode())实现IEquatable<T>接口，并使用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();
    }
}

和使用hashset:

var set = new HashSet<Vector>();
    var vect = new Vector { ... };
set.Add(vect);

你能推荐其他允许"快速包含"的数据结构吗?

由于所有向量必须是唯一的，您可以使用HashSet<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

这听起来接近System.Collections.Generic.HashSet的完美用例(如果您使用的是。net 4.0或更高版本)。

你需要在你的类上实现IEquatable，并且对你的GetHashCode实现要小心一点，因为这三个组件的简单xor可能会导致大量的哈希冲突，例如，同一表中的第一行第二列和第二行第一列总是会发生冲突;关于如何做得更好，请参考CRC32算法。

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

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

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

你可以尝试使用哈希表,如果正确实现的访问时间是常数(在完美世界)或者使用有序二叉树,最大数量的步骤来找到一个值是log 2 n, n是元素的数量,和对数的结果集合起来,在现实生活中大部分的时间不如日志步骤的结果,这是正确的,这是正确实现,你有一个平衡的二叉树

哈希表比二叉树更快，但更难实现，所以这取决于你

相关文章：