Quel est le moyen le plus performant de vérifier l'existence avec une collection d'entiers?

Question

J'ai une grande liste d'entiers qui sont envoyés à mon webservice. Nos règles métier stipulent que ces valeurs doivent être uniques. Quel est le moyen le plus performant pour savoir s'il y a des doublons? Je n'ai pas besoin de connaître les valeurs, j'ai juste besoin de savoir si 2 des valeurs sont égales. Dans un premier temps, je pensais utiliser une liste générique d'entiers et la méthode list.Exists(), mais celle-ci est de O (n); Puis j'ai pensé à utiliser un dictionnaire et la méthode ContainsKey. Mais, j'ai seulement besoin des clés, je n'ai pas besoin des valeurs. Et je pense que c'est aussi une recherche linéaire.

Existe-t-il un meilleur type de données à utiliser pour trouver l'unicité dans une liste? Ou suis-je coincé avec une recherche linéaire?

Answer 1

Utilisez un HashSet<T>:

La classe HashSet fournit des opérations de réglage haute performance . Un ensemble est une collection qui ne contient aucun élément en double, et dont les éléments ne sont en aucun ordre particulier

HashSet<T> expose même a constructor that accepts an IEnumerable<T>. En passant votre List<T> au constructeur HashSet<T>'s, vous obtiendrez une référence à un nouveau HashSet<T> qui contiendra une séquence distincte d'éléments de votre List<T> d'origine.

Answer 2

Sonne comme un emploi pour une Hashset ...

Answer 3

Si vous utilisez Framework 3.5, vous pouvez utiliser la collection HashSet.

Sinon, la meilleure option est la Dictionary. La valeur de chaque article sera gaspillée, mais cela vous donnera les meilleures performances.

Si vous vérifiez les doublons lorsque vous ajoutez les éléments au HashSet/Dictionary au lieu de les compter par la suite, vous obtiendrez de meilleures performances que O (n) en cas de doublons, car vous ne devez pas continuer à vous occuper trouver le premier doublon.

Answer 4

Si l'ensemble des nombres est clairsemé, alors que d'autres suggèrent d'utiliser un HashSet. Mais si l'ensemble des nombres est la plupart du temps en séquence avec des intervalles occasionnels, il serait préférable que vous stockiez le jeu de nombres sous la forme d'un tableau trié ou d'une arborescence binaire de paires début et fin. Ensuite, vous pouvez rechercher la paire avec la plus grande valeur de départ qui était plus petite que votre clé de recherche et la comparer avec la valeur finale de cette paire pour voir si elle existe dans l'ensemble.

Answer 5

Qu'en est-faire:

list.Distinct().Count() != list.Count() 

Je me demande sur la performance de cela. Je pense que ce serait aussi bon que O (n) mais avec moins de code et toujours facilement lisible.