J'ai un hashset contenant plusieurs listes d'entiers - i.e. Afin de maintenir l'unicité, je dois actuellement faire deux choses:
1. Boucle manuelle Bien que les listes existantes, à la recherche de doublons en utilisant Y a-t-il un meilleur moyen de le faire? Existe-t-il un iéqualitère existant que je peux fournir au hashset afin que hashset séquenceequals .
2. Tri des listes individuelles afin que séquenceequalaires fonctionne actuellement. hashset.add () puisse automatiquement gérer l'unicité?
5 Réponses :
Si vous ne spécifiez pas d'iéquitycomparer, les types par défaut seront utilisés, je pense donc que ce que vous aurez besoin de faire est de créer votre propre implémentation de l'iéquitycomparer et de passer cela au constructeur de votre hashset. Voici un bon exemple .
Ceci démarre mal, il doit s'agir d'un hashset
Ce n'est pas comme ReadonlyCollection garantit l'immuabilité. Et si cet ensemble n'est pas exposé dans une mutabilité publique d'une API peu importe. Stocker le hachage calculé n'est pas si important non plus, car je pense que hashset
Un readonlycollection
Ce que je voulais dire, c'est que si vous ne créez pas le ReadonlyCollection vous-même, un étranger a toujours la référence à l'ILITE sous-jacente et peut modifier cette liste, qui est ensuite reflétée dans la liste réadonnycollection. Si vous contrôlez la création de l'immutabilité (peu profonde). (Et sur une immuabilité profonde)
Voici un comparateur possible qui compare un On pourrait construire le tri dans le comparateur, mais je ne pense pas que ce soit un choix judicieux. L'ajout d'une forme canonique de la liste semble plus sage. P> Ce code ne fonctionnera que dans .NET 4, car il tire parti de la variance générique. Si vous avez besoin de versions précédentes, vous devez soit remplacer ienumerable ienumerable code> avec la liste code>, ou ajoutez un deuxième paramètre générique pour le type de collecte. P> 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=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();
}
@downvoter pourriez-vous expliquer quel est le problème avec cette solution, afin que je puisse résoudre / l'améliorer?
(pas mon bowvote) assez proche mais manque la sorte avant l'ajout ou l'égal
C'est pourquoi j'ai expliqué au début qu'il doit toujours trier manuellement.
@Codeinchaose Je suis d'accord avec le choix de conception que vous décrivez. Semble un gaspillage pour sortir toutes les listes déjà triées. C'était un commentaire à votre (maintenant mis à jour) principale (). (et à moi cela ne valait pas la peine de descendre pour en premier lieu)
Avoir le .sort () dans principal montre mieux comment l'utiliser. C'était donc une bonne suggestion :)
@Codeinchaos merci! Cela a bien fonctionné. Bien que je sois un peu confus sur la mise en œuvre égale. Je ne sais pas si je crée un sens, mais pourquoi ne pas simplement comparer les codes de hasch dans des égaux? Appelez-vous que la séquenceequale est égale () essentiellement la même chose?
@Codeinchaose Le tri est le pire cas O (N2) Les égaux sont les pires cas O (n) et le gethashcode toujours O (n), est-ce vraiment le meilleur moyen?
@Magus Le tri est (n * journal (n)), et vous ne pouvez pas être inférieur à O (n) lorsque vous ajoutez une liste arbitraire de toute façon. Le code de hachage sera généralement calculé une fois et les égaux seront calculés aussi souvent que le code de hachage en collision à l'intérieur de la table, qui est O (1). Il y a quelques améliorations possibles, mais je doute qu'ils soient nécessaires dans la pratique. Je crois que c'est un bon compromis entre la lisibilité / la taille et la performance du code.
Aller avec celui-ci, comme maintenant une nouvelle structure de données pour stocker des codes de hash (bien que plus efficaces) semble être une overcilleuse pour mon application
@CodeInchaos - Je venais de supposer que lorsque vous ajoutez quelque chose à un hashset, chaque Hashcode de l'élément existant serait vérifié directement lorsque vous ajoutez autre chose. Ce n'est pas le cas (j'ai confirmé avec un test rapide), vous avez donc raison lorsque vous dites que chaque code de hachage ne doit être vérifié qu'une seule fois. Donc, fondamentalement, ma réponse est surchargée. En même temps, il est intéressant, et un peu troublant, car cela signifie qu'un hashset
Le contrat d'un hashset / dictionnaire indique explicitement que ni l'égalité ni le hashcode ne peuvent changer lorsqu'un objet est dans un ensemble. En règle générale, vous ne remplacez que des égaux / hashcode sur des objets immuables. Et même si Hashset n'a pas stocké le hachage, il serait corrompu par un hachage en mutation, car le hachage détermine le seau, donc avec un hachage changé, il regarde dans le mauvais godet.
Salut, comment puis-je faire ça pour travailler avec le double? j'ai besoin de ça!
Y a-t-il une raison pour laquelle vous n'utilisez pas simplement un tableau? Il semble que leur contenu ne change pas (beaucoup) une fois qu'ils ont été ajoutés au Alors, la première fois que vous Utiliser sur une liste Voici une idée de base. Vous devez faire attention à ce que ce ne soit pas fragile (par exemple, assurez-vous d'annuler tout code de hachage mis en cache lorsque les membres changent) mais cela ne semble pas être une situation typique de la manière dont vous utilisez votre utilisation. Ceci. si les listes ne changent pas une fois ajoutée, cela devrait être très rapide. Même dans les situations où les listes pourraient changer fréquemment, le temps de créer un nouveau code de hachage n'est probablement pas très différent (si même plus grand du tout) que de faire une séquence comparer. int [] sera mieux performer. De plus, je suppose que les listes contiennent des doublons, sinon vous seriez simplement d'utiliser des ensembles et de ne pas avoir de problème. hashset . À la fin de la journée, vous allez devoir utiliser un comparateur qui tombe sur séquenceequal . Mais vous n'avez pas à le faire à chaque fois. Au lieu de cela ou de faire un nombre exponentiel de séquence se compare (par exemple - lorsque le hashset augmente, effectuez un séquencequalaire contre chaque membre existant) - Si vous créez un bon hashcode à l'avant, vous devrez peut-être faire très peu de choses se compare. Tandis que la surcharge de générer un bon hashcode est probablement à peu près la même chose que faire un séquenceequal , vous ne le faites qu'un seul moment pour chaque liste. particulière liste wrapper qui le fait facilement.
Aucune des raisons particulières d'utiliser la liste <>, je ne savais pas sur Int [] S Performant mieux. Merci! Et votre hypothèse est correcte, les listes incluent des doublons, c'est pourquoi je n'utilise pas de jeux.
Généralement, une construction plus simple va probablement être plus rapide qu'un plus complexe, à moins que vous fassiez quelque chose qui dépend de certains aspects de cette structure complexe (par exemple, une liste liée sera beaucoup plus rapide pour insérer des éléments qu'une liste non liée) . La longue et écrasante de ma réponse longue enroulement est que vous devriez utiliser une construction qui peut cacher des codes de hasch. Comme il est coûteux de comparer des listes ou de créer quelque chose qui peut en identifier uniques et que vous le faites beaucoup de fois sur les mêmes objets, il suffit de définir quelque chose qui se souviendra de cet identifiant unique.
Lors de la comparaison de hashsets de liste une option que vous avez toujours, c'est que, au lieu de comparer chaque élément, vous triez les listes et les rejoindre à l'aide d'une virgule et de comparaison des chaînes générées.
Donc, dans ce cas, lorsque vous créez des comparateurs personnalisés au lieu d'itération des éléments et de calculer la fonction de hachage personnalisée, vous pouvez appliquer cette logique.
Vérifiez la réponse de Jon Skeet ici: Stackoverflow.com/questions/1023424/...
Pourriez-vous fournir plus d'informations sur quel problème vous essayez de résoudre?
hashset> semble être un outil improbable à utiliser.
@marcind, je l'utilise pour maintenir une liste de toutes les factorisations d'un numéro .. Donc, pour 24, vous pouvez avoir par exemple {4, 2, 3}, {2, 2, 6}, etc ... l'algorithme que j'utilise Pour le moment crée des ensembles en double, j'aimerais savoir comment résoudre ce problème, mais je n'ai malheureusement pas: - /
Vous voudrez peut-être demander cela comme une question distincte. Il devrait y avoir une solution plus élégante que ce que vous essayez actuellement.
@CODEINCHAOS, YUP, je pense vraiment que je devrais! Toute solution sera plus élégante que le gâchis que je vais au moment ;-)
@PRESSE - C'est un sujet un peu hors sujet, mais quel espace de noms d'obtention de Hasset. Je penserais que ce serait dans System.Collections.Generic, mais j'ai
à l'aide de System.Collections.generic et que I CNA Utilisez la liste, il vous crie à moi pour utiliser HASHSET ...@ kralco626, j'utilise System.Collections.Generic.HashSet. J'ai peur de ne pas vraiment avoir votre question .. Le compilateur vous demandant d'utiliser une liste au lieu d'un hashset?
@Peest - Non, il est juste d'essayer de me dire que Hashset n'existe pas dans System.Collections.Generic ...