objets du groupe par l'égalité

I ont une collection d'objets que je voudrais comparer l'égalité à l'aide d'une méthode qui ressemble à ceci:objets du groupe par l'égalité

bool AreEqual (MyObject O1, O2 MyObject);

Quel serait le moyen le plus convivial pour regrouper tous les objets égaux? La réponse évidente serait de comparer chaque objet avec tous les autres objets de la collection mais cela nuirait plutôt à la performance (N^N, je crois).

Le groupe LINQ par opérateur pourrait-il offrir une solution?

EDIT:

Je serais peut-être nommé MyObject TheirObject que je ne peux pas modifier sa mise en œuvre (et il ne met pas en œuvre IComparable). Cela signifie que je vais probablement utiliser la solution d'ICR.

Source

2009-12-06 Opflash

Vous n'avez pas besoin de comparer tous les objets à tous les autres obj ect, vous devez comparer chaque objet avec chaque groupe (par ex. premier élément du groupe) et créer un nouveau groupe s'il ne correspond à aucun (ou s'il s'agit du premier élément).

La pourrait ressembler à:

public static IEnumerable<IEnumerable<T>> Group<T>(IEnumerable<T> items) 
    where T : IEquatable<T> 
{ 
    IList<IList<T>> groups = new List<IList<T>>(); 

    foreach (T t in items) 
    { 
     bool foundGroup = false; 

     foreach (IList<T> group in groups) 
     { 
      Debug.Assert(group.Count() >= 1); 
      if (group[0].Equals(t)) 
      { 
       group.Add(t); 
       foundGroup = true; 
       break; 
      } 
     } 

     if (!foundGroup) 
     { 
      IList<T> newGroup = new List<T>() { t }; 
      groups.Add(newGroup); 
     } 
    } 

    foreach (IList<T> group in groups) 
    { 
     yield return group; 
    } 
}

Ceci est, bien sûr, déjà fait pour vous dans LINQ, que les gens ont indiqué plus haut comment utiliser. Je voulais juste démontrer que l'algorithme peut être un peu mieux que de comparer chaque élément à chaque élément.

N.B. L'algorithme repose sur l'hypothèse que la relation d'égalité est transitive - c'est-à-dire si a est égal à b, et b est égal à c, alors a est égal à c. Bien que je ne sois pas tout à fait sûr de la façon dont vous regrouperiez des éléments non-transitifs.

Source

2009-12-06 14:55:14 ICR

Nous vous remercions de votre échantillon. Avec votre permission, j'aimerais l'utiliser dans mon projet. Les dernières lignes sont particulièrement intéressantes. Quel avantage la boucle finale offre-t-elle par rapport à un simple "groupe de retour"? ? – Opflash

Comme je le dis, je recommande toujours la solution LINQ. C'est à peu près la même chose, mais c'est déjà écrit pour vous. La raison pour laquelle j'ai donné l'échantillon était que vous pouvez voir comment un tel algorithme pourrait fonctionner. Le but des lignes finales est parce que j'aime renvoyer le type le plus général applicable - dans ce cas IEnumerable. Mais pour les construire, vous devez utiliser IList pour avoir la méthode Add. C# ne peut actuellement pas trouver comment transformer un IEnumerable en un IEnumerable > donc vous devez céder chaque groupe manuellement. L'avantage est qu'il compile :) – ICR

Ce n'est vraiment pas une bonne implémentation, car c'est O (n^2). Veuillez utiliser la méthode d'extension Linq 'GroupBy' existante. – ErikE

Je suggère d'utiliser IComparable interface pour la classe MyObject et puis essayer de regroupement, par exemple comme cela est fait here ou here

Source

2009-12-06 14:05:08 Gacek

Vous pouvez utiliser le IEqualityComparer si vous prévoyez d'utiliser LINQ. Here est un exemple en utilisant IComparer et IEqualityComparer

j'irais avec LINQ pour comparer tous les elements.If que vous essayez d'obtenir une liste d'objets distincts, je le ferais de cette façon (pseudocode)

Mettre en oeuvre IEqualityComparer, dire ObjectEqualityComparer implémente IEqualityComparer
var result = sourceList.Distinct (une instance de objectEqualityComparer)

Source

2009-12-06 14:24:11 ram

objets du groupe par l'égalité

Répondre

Questions connexes