Comment créer un HashSet <List > avec des éléments distincts?

Voici un comparateur possible qui compare un IEnumerable par ses éléments. Vous devez toujours sortinger manuellement avant d’append.

On pourrait intégrer le sorting dans le comparateur, mais je ne pense pas que ce soit un choix judicieux. Ajouter une forme canonique à la liste semble plus sage.

Ce code ne fonctionnera que dans .net 4 car il tire parti de la variance générique. Si vous avez besoin de versions antérieures, vous devez soit remplacer IEnumerable par List , soit append un deuxième paramètre générique pour le type de collection.

 class SequenceComparer:IEqualityComparer> { public bool Equals(IEnumerable seq1,IEnumerable seq2) { return seq1.SequenceEqual(seq2); } public int GetHashCode(IEnumerable seq) { int hash=1234567; foreach(T elem in seq) hash=hash*37+elem.GetHashCode(); return hash; } } void Main() { var hashSet = new HashSet>(new SequenceComparer()); List test=new int[]{1,3,2}.ToList(); test.Sort(); hashSet.Add(test); List test2=new int[]{3,2,1}.ToList(); test2.Sort(); hashSet.Contains(test2).Dump(); } 

Cela commence mal, il doit s’agir d’un HashSet> car vous ne pouvez pas autoriser les listes à modifier et à invalider le prédicat défini. Cela vous permet ensuite de calculer un code de hachage dans O (n) lorsque vous ajoutez la collection à l’ensemble. Et un test O (n) pour vérifier s’il fait déjà partie de l’ensemble avec un cas très rare O (n ^ 2) si tous les hachages se révèlent égaux. Stocker le hachage calculé avec la collection.

Y a-t-il une raison pour laquelle vous n’utilisez pas simplement un tableau? int[] donnera de meilleurs résultats. De plus, je suppose que les listes contiennent des doublons, sinon vous utiliseriez simplement des ensembles sans problème.

Il semble que leur contenu ne change pas (beaucoup) une fois qu’ils ont été ajoutés au HashSet . À la fin de la journée, vous devrez utiliser un comparateur qui se replie sur SequenceEqual . Mais vous n’êtes pas obligé de le faire à chaque fois. Si vous créez un bon code de hachage à l’avance, vous devrez peut-être effectuer très peu de comparaisons de ce type. Bien que générer un bon hashcode représente probablement une surcharge du même ordre que de faire un SequenceEqual vous ne le faites qu’une seule fois pour chaque liste.

Ainsi, la première fois que vous manipulez une List particulière List , vous devez générer un hachage basé sur la séquence de nombres ordonnée et le mettre en cache. Ensuite, lors de la prochaine comparaison de la liste, la valeur en cache pourra être utilisée. Je ne sais pas comment vous pourriez faire cela avec un comparateur sur ma tête (peut-être un dictionnaire statique?) – mais vous pouvez implémenter un wrapper List qui le fait facilement.

Voici une idée de base. Vous devez faire attention à ce qu’il ne soit pas fragile (par exemple, assurez-vous d’annuler tout code de hachage mis en cache lorsque les membres changent), mais il ne semble pas que ce soit une situation typique pour votre utilisation. ce.

 public class FasterComparingList: IList, 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 InnerList { ... lazy load a List } public int GetHashCode() { if (_LongHash==null) { _LongHash=GetLongHash(); } return (int)_LongHash; } private int? _LongHash=null; public bool Equals(FasterComparingList 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 } } 

Si les listes ne changent pas une fois ajoutées, cela devrait être très rapide. Même dans des situations où les listes peuvent changer fréquemment, le temps nécessaire pour créer un nouveau code de hachage n’est probablement pas très différent (voire plus long) que celui d’une comparaison séquentielle.

Si vous ne spécifiez pas IEQualityComparer, les types par défaut seront utilisés. Je pense donc que vous devez créer votre propre implémentation de IEQualityComparer et la transmettre au constructeur de votre HashSet. Voici un bon exemple .