13

整数の複数のリストを含む HashSet があります-つまりHashSet<List<int>>

一意性を維持するために、現在 2 つのことを行う必要があります。 1. を使用して重複を探し、既存のリストを手動でループしますSequenceEquals。2. 現在機能するように個々のリストを並べ替えますSequenceEquals。

これを行うより良い方法はありますか？HashSet.Add()一意性を自動的に処理できるように HashSet に提供できる既存の IEqualityComparer はありますか?

var hashSet = new HashSet<List<int>>();

for(/* some condition */)
{
    List<int> list = new List<int>();

    ...

    /* for eliminating duplicate lists */

    list.Sort();

    foreach(var set in hashSet)
    {
        if (list.SequenceEqual(set))
        {
            validPartition = false;
            break;
        }
    }

    if (validPartition)
           newHashSet.Add(list);
}
4

5 に答える 5

7

これは間違ったところから始まりHashSet<ReadOnlyCollection<>>ます。リストを変更して設定された述語を無効にすることはできないため、これが原因である必要があります。これにより、コレクションをセットに追加するときに、O（n）でハッシュコードを計算できます。そして、すべてのハッシュが等しいことが判明した場合に、非常にまれなO（n ^ 2）の最悪のケースで、それがすでにセットに含まれているかどうかを確認するO（n）テスト。計算されたハッシュをコレクションとともに保存します。

于 2011-04-01T20:26:43.117 に答える
6

IEnumerable<T>これは、要素ごとにを比較する可能な比較対象です。追加する前に、手動で並べ替える必要があります。

ソートを比較器に組み込むこともできますが、それは賢明な選択ではないと思います。リストの標準形を追加する方が賢明なようです。

このコードは、一般的な差異を利用しているため、.net4でのみ機能します。以前のバージョンが必要な場合は、に置き換えるかIEnumerable、Listコレクション型の2番目のジェネリックパラメーターを追加する必要があります。

class SequenceComparer<T>:IEqualityComparer<IEnumerable<T>>
{
    public bool Equals(IEnumerable<T> seq1,IEnumerable<T> seq2)
    {
        return seq1.SequenceEqual(seq2);
    }
    
    public int GetHashCode(IEnumerable<T> seq)
    {
        int hash = 1234567;
        foreach(T elem in seq)
            hash = unchecked(hash * 37 + elem.GetHashCode());
        return hash;
    }
}

void Main()
{
    var hashSet = new HashSet<List<int>>(new SequenceComparer<int>());

    List<int> test=new int[]{1,3,2}.ToList();
    test.Sort();
    hashSet.Add(test);

    List<int> test2=new int[]{3,2,1}.ToList();
    test2.Sort();       
    hashSet.Contains(test2).Dump();
}
于 2011-04-01T20:29:58.980 に答える
2

アレイだけを使用していない理由はありますか？int[]パフォーマンスが向上します。また、リストに重複が含まれていると思います。そうでない場合は、セットを使用しているだけで問題はありません。

に追加すると、内容は（ほとんど）変更されないようHashSetです。1日の終わりには、にフォールバックする比較機能を使用する必要がありますSequenceEqual。しかし、毎回それを行う必要はありません。代わりに、または指数関数的な数のシーケンス比較を実行します（たとえば、ハッシュセットが大きくなるにつれて、SequenceEqual既存の各メンバーに対して実行します）。適切なハッシュコードを事前に作成する場合、そのような比較をほとんど実行する必要がない場合があります。SequenceEqual適切なハッシュコードを生成するオーバーヘッドは、おそらく、リストごとに1回だけ実行するのとほぼ同じです。

したがって、特定のを初めて操作するときはList<int>、順序付けられた数列に基づいてハッシュを生成し、それをキャッシュする必要があります。次にリストを比較するときに、キャッシュされた値を使用できます。頭のてっぺんにある比較器（おそらく静的辞書？）を使ってこれをどのように行うかはわかりませんが、Listこれを簡単に行うラッパーを実装することはできます。

これが基本的な考え方です。もろくないことを確認する必要があります（たとえば、メンバーが変更されたときにキャッシュされたハッシュコードを無効にすることを確認してください）が、それはあなたが使用している方法の典型的な状況になるとは思われませんこれ。

public class FasterComparingList<T>: IList<T>, IList, ... 
    /// whatever you need to implement
{
   // Implement your interfaces against InnerList
   // Any methods that change members of the list need to
   // set _LongHash=null to force it to be regenerated
   public List<T> InnerList { ... lazy load a List }
   public int GetHashCode()
   {
       if (_LongHash==null) {
           _LongHash=GetLongHash();
       }
       return (int)_LongHash;
   }
   private int? _LongHash=null;
   public bool Equals(FasterComparingList<T> list)
   {
       if (InnerList.Count==list.Count) {
           return true;
       }
       // you could also cache the sorted state and skip this if a list hasn't
       // changed since the last sort
       // not sure if native `List` does
       list.Sort();
       InnerList.Sort();
       return InnerList.SequenceEqual(list);
   }
   protected int GetLongHash()
   {
       return .....
       // something to create a reasonably good hash code -- which depends on the 
       // data. Adding all the numbers is probably fine, even if it fails a couple 
       // percent of the time you're still orders of magnitude ahead of sequence
       // compare each time
   } 
}

リストを追加しても変更されない場合、これは非常に高速です。リストが頻繁に変更される可能性がある状況でも、新しいハッシュコードを作成する時間は、シーケンス比較を実行する場合とそれほど変わらない可能性があります（たとえあったとしても）。

于 2011-04-01T20:33:50.317 に答える
0

IEQualityComparer を指定しない場合は、デフォルトの型が使用されるため、IEQualityComparer の独自の実装を作成し、それを HashSet のコンストラクターに渡す必要があると思います。これが良い例です。

于 2011-04-01T19:38:26.163 に答える