いくつかの Linq.Enumerable 関数は を受け取ります。を実装するために をIEqualityComparer<T>
適応させる便利なラッパー クラスはありますか? 1 つ書くのは簡単ですが (正しいハッシュコードの定義に関する問題を無視すれば)、すぐに使えるソリューションがあるかどうか知りたいです。delegate(T,T)=>bool
IEqualityComparer<T>
Dictionary
具体的には、キーのみを使用してメンバーシップを定義し、(異なるルールに従って値を保持しながら) sに対してセット操作を実行したいと考えています。
ベストアンサー1
の重要性についてGetHashCode
他の人は既に、カスタムIEqualityComparer<T>
実装はGetHashCode
実際にメソッドを含める必要があります;しかし誰も説明しようとしないなぜ細部まで。
理由は次の通りです。あなたの質問ではLINQ拡張メソッドについて具体的に言及されています。全てこれらの多くは、効率化のために内部的にハッシュ テーブルを利用しているために、適切に動作するためにハッシュ コードに依存しています。
取るDistinct
たとえば、 です。この拡張メソッドがメソッドだけを利用した場合の影響を考えてみましょうEquals
。 しかない場合、シーケンス内で項目が既にスキャンされているかどうかをどのように判断するのでしょうか。既に調べた値のコレクション全体を列挙し、一致をチェックします。これにより、最悪のケースでは O(N) アルゴリズムではなく O(N 2 ) アルゴリズムを使用するEquals
ことになります。Distinct
幸いなことに、そうではありませんDistinct
。ただ使用Equals
; 使用GetHashCode
も同様です。実際、それは絶対にではないIEqualityComparer<T>
適切なものがなければ適切に機能しないGetHashCode
以下は、これを説明する架空の例です。
次のようなタイプがあるとします。
class Value
{
public string Name { get; private set; }
public int Number { get; private set; }
public Value(string name, int number)
{
Name = name;
Number = number;
}
public override string ToString()
{
return string.Format("{0}: {1}", Name, Number);
}
}
ここで、あるList<Value>
要素を一意の名前ですべて検索したいとします。これはDistinct
カスタム等価比較子を使用するのに最適な使用例です。それではComparer<T>
、アクの答え:
var comparer = new Comparer<Value>((x, y) => x.Name == y.Name);
Value
さて、同じプロパティを持つ要素が多数ある場合Name
、それらはすべて によって返される 1 つの値にまとめられるはずですDistinct
よね? 見てみましょう...
var values = new List<Value>();
var random = new Random();
for (int i = 0; i < 10; ++i)
{
values.Add("x", random.Next());
}
var distinct = values.Distinct(comparer);
foreach (Value x in distinct)
{
Console.WriteLine(x);
}
出力:
x: 1346013431 x: 1388845717 x: 1576754134 x: 1104067189 x: 1144789201 x: 1862076501 x: 1573781440 x: 646797592 x: 655632802 x: 1206819377
うーん、それはうまくいかなかったですね?
どうですかGroupBy
? 試してみましょう:
var grouped = values.GroupBy(x => x, comparer);
foreach (IGrouping<Value> g in grouped)
{
Console.WriteLine("[KEY: '{0}']", g);
foreach (Value x in g)
{
Console.WriteLine(x);
}
}
出力:
[キー = 'x: 1346013431'] x: 1346013431 [キー = 'x: 1388845717'] x: 1388845717 [キー = 'x: 1576754134'] x: 1576754134 [キー = 'x: 1104067189'] x: 1104067189 [キー = 'x: 1144789201'] x: 1144789201 [キー = 'x: 1862076501'] x: 1862076501 [キー = 'x: 1573781440'] x: 1573781440 [キー = 'x: 646797592'] x: 646797592 [キー = 'x: 655632802'] x: 655632802 [キー = 'x: 1206819377'] x: 1206819377
再度: 動作しませんでした。
よく考えてみると、 では内部的に (または同等のもの)Distinct
を使用しHashSet<T>
、 では内部的にGroupBy
のようなものを使用するのが理にかなっていますDictionary<TKey, List<T>>
。これで、これらのメソッドが機能しない理由を説明できるでしょうか? 試してみましょう:
var uniqueValues = new HashSet<Value>(values, comparer);
foreach (Value x in uniqueValues)
{
Console.WriteLine(x);
}
出力:
x: 1346013431 x: 1388845717 x: 1576754134 x: 1104067189 x: 1144789201 x: 1862076501 x: 1573781440 x: 646797592 x: 655632802 x: 1206819377
うん... 意味がわかってきた?
これらの例から、あらゆる実装GetHashCode
に適切なを含めることがなぜそれほど重要であるかが明らかになると思います。IEqualityComparer<T>
元の回答
拡大するoripの回答:
ここで改善できる点がいくつかあります。
Func<T, TKey>
まず、の代わりにを使用しますFunc<T, object>
。これにより、実際のkeyExtractor
自体で値型キーがボックス化されるのを防ぎます。- 2 番目に、私は実際に
where TKey : IEquatable<TKey>
制約を追加します。これにより、呼び出しでのボックス化が防止されますEquals
(パラメーターobject.Equals
を受け取ります。ボックス化せずにパラメーターを受け取るには実装object
が必要です)。明らかに、これは厳しすぎる制限を課す可能性があるため、制約のない基本クラスと制約のある派生クラスを作成できます。IEquatable<TKey>
TKey
結果のコードは次のようになります。
public class KeyEqualityComparer<T, TKey> : IEqualityComparer<T>
{
protected readonly Func<T, TKey> keyExtractor;
public KeyEqualityComparer(Func<T, TKey> keyExtractor)
{
this.keyExtractor = keyExtractor;
}
public virtual bool Equals(T x, T y)
{
return this.keyExtractor(x).Equals(this.keyExtractor(y));
}
public int GetHashCode(T obj)
{
return this.keyExtractor(obj).GetHashCode();
}
}
public class StrictKeyEqualityComparer<T, TKey> : KeyEqualityComparer<T, TKey>
where TKey : IEquatable<TKey>
{
public StrictKeyEqualityComparer(Func<T, TKey> keyExtractor)
: base(keyExtractor)
{ }
public override bool Equals(T x, T y)
{
// This will use the overload that accepts a TKey parameter
// instead of an object parameter.
return this.keyExtractor(x).Equals(this.keyExtractor(y));
}
}