Vitesse des listes C#

Question

Les listes C# sont-elles rapides? Quels sont les côtés positifs et négatifs de l'utilisation de listes pour gérer des objets?

L'utilisation intensive des listes ralentira le logiciel? Quelles sont les alternatives aux listes en C#?

Combien d'objets contient "trop ​​d'objets" pour les listes?

Answer 1

List<T> utilise une matrice de support pour contenir les articles:

• accès indexeur (c.-à récupération/mise à jour) est O (1)
• Retirer de la queue est O (1)
• Supprimer de ailleurs exige les éléments existants doivent être décalés vers le haut, donc O (n) efficacement
• Ajouter à la fin est O (1) à moins qu'il ne nécessite un redimensionnement, auquel cas c'est O (n). (Ce double la taille du tampon, de sorte que le coût amorti est O (1).)
• Ajouter à ailleurs nécessite des éléments existants à décaler vers le bas, donc O (n) efficace
• Recherche d'un élément est O (n) sauf si elle est triée, auquel cas une recherche binaire donne O (log n)

Il est généralement bon d'utiliser les listes assez largement. Si vous connaissez la taille finale lorsque vous commencez à remplir une liste, c'est une bonne idée d'utiliser le constructeur qui vous permet de spécifier la capacité, pour éviter le redimensionnement. Au-delà: si vous êtes concerné, éclatez le profiler ...

Answer 2

Comparé à quoi?

• Si vous voulez dire List<T>, alors c'est essentiellement un wrapper autour d'un tableau; si rapide à lire/écrire par index, relativement rapide rapide à ajouter (car il permet un espace supplémentaire à la fin, doubler la taille si nécessaire) et supprimer de la fin, mais plus cher de faire d'autres opérations (insérer/supprimer autre que la fin)
• Un tableau est à nouveau rapide par index, mais la taille fixe (pas append/supprimer)
• Dictionary<,> etc offrent un meilleur accès par clé

Une liste n'est pas intrinsèquement lent; surtout si vous savez que vous avez toujours besoin de regarder toutes les données, ou pouvez y accéder par index. Mais pour les grandes listes, il peut être préférable (et plus pratique) d'effectuer une recherche via une clé. Il existe différentes implémentations de dictionnaire dans .NET, chacune avec des coûts différents en termes de taille/performance.