ObservableCollectionからKeyValueを最も効果的に削除しますか？

Question

コレクションからグループを削除する次のコードがあります。技術的には重複はありませんが、とにかくすべて削除されます。 LINQを使ってどんなトリックを.Remove.Where..にするのですか？

public void DeleteGroup(KeyValuePair<int, string> group) 
      { 
       while (this.Groups.Any(g => g.Key.Equals(group.Key))) 
       { 
        var groupToRemove = this.Groups.First(g => g.Key.Equals(group.Key)); 
        this.Groups.Remove(groupToRemove); 
       } 

      } 

Answer 1

あなたは同じキーとこのObseravableCollectionで可能な最も効率的な方法で同じ値でKeyValuePairに渡していると仮定。 KeyValuePair構造であるため、そして、オーバーロード演算子は==それがキーと構造の値のデータメンバーの両方を比較している適用されたときに

public void DeleteGroup2(KeyValuePair<int, string> group) 
{ 
    Groups.Remove(group); 
} 

これは動作します。

また、グループobserabableCollectionに含まれているキーと値と同じキーと値を渡すと、正常に機能します。値が一致しない場合は機能しません。

ObserableCollectionの背後にはかなりのリストがありますので、==演算子を実行するすべてのアイテムを繰り返し処理する必要があります。転記しているコードについても同じことが言えます。 LINQを使用しているという理由だけでは、それはそれ以上効率的ではありません。 LINQ to SQLのような索引付けを使用しているLINQ where節のようなものではありません。

public void DeleteGroup3(KeyValuePair<int, string> groupToDelete) 
{ 
    var itemsToDelete = 
     (
      from g in Groups 
      where g.Key == groupToDelete.Key 
      select g 
     ); 

    foreach (var kv in itemsToDelete) 
    { 
     Groups.Remove(kv); 
    } 
} 

あなたが重複するキーにしても、それらのすべての項目を削除することを保証したい場合、これはおそらく、LINQを使用して最も効率的な方法だろう。

public void DeleteGroup4(KeyValuePair<int, string> group) 
{ 
    List<int> keyIndexes = new List<int>(); 
    int maxIndex = Groups.Count; 
    for (int i = 0; i < maxIndex; i++) 
    { 
     if (Groups[i].Key == group.Key) 
     { 
      keyIndexes.Add(i); 
     } 
    } 

    int indexOffset = 0; 
    foreach (int index in keyIndexes) 
    { 
     Groups.RemoveAt(index - indexOffset); 
     indexOffset++; 
    } 
} 

あなたは同じキーを持つ複数のアイテムを持っているか、あなたは、元のとまったく同じキーと値のペアを知らない場合、これはそれらのすべての最高のパフォーマンスを持っている必要があります。

私はあなたのDeleteGroupメソッドが2N^2 ... Nの外側であることを信じています。ループ中にはN、最初はN、削除用にNです。外側のループに内側と2Nの合計を取る^ 2

DeleteGroup2はNのBIG Oであり、すべてのパフォーマンスが最高です。欠点は、キーだけでなくキーと値の両方を知る必要があることです。また、見つかった最初のアイテムのみが削除されます。同じKeyと同じValueを持つ重複アイテムは削除されません。

DeleteGroup3はN + N^2のIS BIG Oです。選択のためのN。さらに悪いケースは、あなたの鍵がそこにN回N = 2であることです。

DeleteGroup4は2NのBIG Oです。 Nを押してインデックスを検索し、最悪の場合、同じキーを持つアイテムをすべて持っていればRemoveAtIndexはBig Oとなります。これはKeyを知っていて、同じキーで複数のアイテムを持つ可能性。

重複しているアイテムがないことがわかっている場合は、私はDeleteGroup2を使用します。重複する可能性がある場合は、DeleteGroup4が最高のパフォーマンスを持つ必要があります。

重複がなく、キーと値の両方がわからない場合は、DeleteGroup2の最高の実行オプションを使用できますが、キーと値のプロパティを持つKeyValueIntStringというクラスを作成できます。次に、IsEqualsメソッドをオーバーライドして、KeyおよびValueデータメンバの両方を比較するKeyValue構造体とは異なり、Keyプロパティのみを比較します。次に、ObserableCollection.Removeメソッドを使用して、格納されている値を知ることについて心配する必要はありません。 I.Keyを設定したKeyValueIntStringのインスタンスを渡すこともできますが、Valueプロパティの設定については心配する必要はありません。

コメント後、私は最高の読みやすさの方法を追加することにしましたが、パフォーマンスは悪くなりました。 N^4の大きなOを持っています。選択の場合はN、ToListの場合はN、ForEachの場合はN、削除の場合はNがあります。

public void DeleteGroup5(KeyValuePair<int, string> groupToDelete) 
{ 
    (
     from g in Groups 
     where g.Key == groupToDelete.Key 
     select g 
    ).ToList().ForEach(g => Groups.Remove(g)); 
}