1

我有以下数据类型：

ISet<IEnumerable<Foo>>

所以，我需要能够创建序列集。例如，这没关系：

ABC,AC,A

但这不是（因为这里重复了“AB”）：

AB,A,ABC,BCA,AB

但是，为了做到这一点 - 为了“设置”不包含重复项，我需要将我的数据包装IEnumerable在某种其他数据类型中：

ISet<Seq>
//where
Seq : IEnumerable<Foo>, IEquatable<Seq>

因此，我将能够比较两个序列，并为 Set 数据结构提供一种消除重复的方法。

我的问题是：是否有允许比较序列的快速数据结构？我在想，以某种方式Seq创建或添加两个时，会计算某种累积值。

换句话说，是否有可能以我可以这样做的方式实现 Seq：

var seq1 = new Seq( IList<Foo> );
var seq2 = new Seq( IList<Foo> )
seq1.equals(seq2) // O(1)

谢谢。

4

2 回答 2

2

我在下面提供了您的序列的实现。有几点需要注意：

  1. 这只适用于IEnumerable<T>每次枚举时返回相同的项目，并且这些项目在此对象的范围内没有发生变化。
  2. 哈希码被缓存。第一次请求它时，它会根据底层序列的完整迭代计算它（如果您知道更好的哈希码算法，请随意改进）。因为它只需要计算一次，如果你经常计算，这可以有效地考虑 O(1)。添加到集合可能会慢一些（第一次计算哈希值），但搜索或删除会非常快。

  3. equals 方法首先比较哈希码。如果散列码不同，则对象不可能相等（如果散列码在序列中的所有对象上都正确实现，并且没有任何变化）。只要您的冲突率较低，并且通常比较实际上不相等的项目，这意味着等于检查通常不会通过哈希码检查。如果他们这样做，则需要对序列进行迭代（没有办法解决这个问题）。因此，equals 的平均值可能为 O(1)，即使它最坏的情况仍然是 O(n)。

    公共类 Foo : IEnumerable { 私有 IEnumerable 序列；

    private int? myHashCode = null;

public Foo(IEnumerable<T> sequence)
{
    this.sequence = sequence;
}

public IEnumerator<T> GetEnumerator()
{
    return sequence.GetEnumerator();
}

IEnumerator IEnumerable.GetEnumerator()
{
    return sequence.GetEnumerator();
}

public override bool Equals(object obj)
{
    Foo<T> other = obj as Foo<T>;
    if(other == null)
        return false;

    //if the hash codes are different we don't need to bother doing a deep equals check
    //the hash code is cached, so it's fast.
    if (GetHashCode() != obj.GetHashCode())
        return false;

    return Enumerable.SequenceEqual(sequence, other.sequence);
}

public override int GetHashCode()
{
    //note that the hash code is cached, so the underlying sequence 
    //needs to not change.
    return myHashCode ?? populateHashCode();
}

private int populateHashCode()
{
    int somePrimeNumber = 37;
    myHashCode = 1;
    foreach (T item in sequence)
    {
        myHashCode = (myHashCode * somePrimeNumber) + item.GetHashCode();
    }

    return myHashCode.Value;
}

    }

于 2012-10-01T19:45:10.167 回答
1

O(1) 本质上意味着您不允许比较元素的值。如果您可以将序列表示为不可变对象的列表（在添加时进行缓存，因此在所有实例中都没有重复项），您可以实现它，因为您只需要比较第一个元素 - 类似于字符串实习的工作方式。

Insert 必须搜索“current”+“with this next”元素的所有元素实例。某种字典可能是合理的方法......

编辑：我认为它只是想提出suffix tree。

于 2012-10-01T19:38:06.660 回答