Quelle est la structure de données la plus efficace pour stocker une liste d'entiers qui doivent être recherchés beaucoup dans .Net?

Question

J'ai besoin d'une structure de données efficace pour stocker une liste d'entiers. Le nombre dans la liste peut varier de 1 à probablement jamais plus de 1000. La liste sera interrogée environ 20 fois par demande. Quel serait le type de collection le plus efficace pour stocker ces?

MISE À JOUR

Pour donner un peu plus de perspicacité, nous prendrons www.wikipediamaze.com (a little game I wrote) à titre d'exemple (pas le scénario réel, mais assez près pour la conversation). Pour la liste des puzzles sur une page donnée, je retourne actuellement une liste de la table des puzzles jointe à la table qui stocke les puzzles que l'utilisateur actuel a joué. Au lieu de cela, je veux mettre en cache la liste des puzzles agnostiques à l'utilisateur. Donc ce que je fais est d'abord le chargement et la mise en cache de la liste des puzzles de la base de données. Ensuite, je charge et cache la liste des puzzles que l'utilisateur a joué. Puis, quand je itérer suis sur les casse-tête pour les afficher, je veux faire:

protected BestDataStructure<long> PlayedPuzzles {get; set;} //Loaded from session 

protected bool HasBeenPlayed(long puzzleId) 
{ 
    return PlayedPuzzles.Contains(puzzleId) 
} 

A chaque fois qu'ils jouent un nouveau casse-tête, je sauverai l'enregistrement à la base de données et l'ajouter à la liste stockée dans la session.

Merci!

Answer 1

Cela dépend de la façon dont vous devez les interroger, mais un simple tableau, ou HashSet<int> vient à l'esprit.

Les deux sont O (1) lorsque vous les indexez. HashSet.Contains est également O (1).

En réponse à votre commentaire sur la question: Utilisez HashSet, car vous devez vérifier si un entier spécifié existe. Vous devriez utiliser Contient() sur HashSet pour faire ceci; cela vous donnera la meilleure performance. Si vous avez besoin de stocker une autre valeur liée à la valeur, utilisez peut-être Dictionary.

Answer 2

HashSet(int).

Answer 3

Si vous recherchez une structure qui exécute efficacement une opération telle que Contains(), alors HashSet<int> est ce que vous cherchez. HashSet<int> est O (1) (temps constant) pour Contains(), ce qui est aussi complexe que vous l'obtiendrez.

Answer 4

si vous avez besoin de vérifier la présence de l'élément, alors probablement bool[] avec 1000 éléments et définissez true pour les éléments entiers existants?