1

次のデータ型があります。

ISet<IEnumerable<Foo>>

そのため、一連のシーケンスを作成できる必要があります。たとえば、これは問題ありません:

ABC,AC,A

しかし、これはそうではありません (「AB」がここで繰り返されるため):

AB,A,ABC,BCA,AB

しかし、これを行うには、「セット」に重複が含まれないようにするIEnumerableには、他の種類のデータ型でmy をラップする必要があります。

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

したがって、2 つのシーケンスを比較し、Set データ構造に重複を排除する方法を提供できます。

私の質問は: シーケンスを比較できる高速なデータ構造はありますか? Seqどういうわけか、作成または2つ追加すると、何らかの累積値が計算されると考えています。

言い換えれば、私がこれを行うことができるような方法で 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 メソッドは、最初にハッシュ コードを比較します。ハッシュ コードが異なる場合、オブジェクトが等しい可能性はありません (ハッシュ コードがシーケンス内のすべてのオブジェクトに適切に実装され、何も変更されていない場合)。衝突率が低く、通常、実際には等しくないアイテムを比較している限り、これは、等値チェックがそのハッシュ コード チェックを通過しないことが多いことを意味します。その場合、シーケンスの反復が必要です (それを回避する方法はありません)。そのため、最悪の場合でも O(n) であっても、equals は平均 O(1) になる可能性があります。

    public class 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) は基本的に、要素の値を比較できないことを意味します。シーケンスを不変オブジェクトのリストとして表すことができる場合（すべてのインスタンスで重複しないように追加時にキャッシュを使用）、最初の要素を比較するだけで済みます-文字列のインターンの仕組みと同様です。

挿入は、「現在の」+「この次の」要素の要素のすべてのインスタンスを検索する必要があります。ある種の辞書は合理的なアプローチかもしれません...

編集:サフィックス treeを考え出そうとしただけだと思います。

于 2012-10-01T19:38:06.660 に答える