Tableau pouvant être redimensionné rapidement

Question

Je recherche un type de données de type tableau pouvant facilement ajouter des éléments, sans impact négatif sur les performances.

• Système. Tableau : Redim Preserve copie l'intégralité de la mémoire vive (RAM) de l'ancien au nouveau, aussi lentement que la quantité d'éléments existants
• System.Collections. ArrayList : assez bon?
• System.Collections. IList : assez bon?

Answer 1

Juste pour résumer quelques structures de données:

System.Collections.ArrayList : les structures de données non typées sont obsolètes. Utilisez List (of t) à la place.

System.Collections.Generic.List (of t) : cela représente un tableau redimensionnable. Cette structure de données utilise un tableau interne en coulisse. L'ajout d'éléments à la liste est O (1) tant que le tableau sous-jacent n'a pas été rempli, sinon son O (n + 1) permet de redimensionner le tableau interne et de copier les éléments.

List<int> nums = new List<int>(3); // creates a resizable array
                                   // which can hold 3 elements

nums.Add(1);
// adds item in O(1). nums.Capacity = 3, nums.Count = 1

nums.Add(2);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(3);
// adds item in O(1). nums.Capacity = 3, nums.Count = 3

nums.Add(4);
// adds item in O(n). Lists doubles the size of our internal array, so
// nums.Capacity = 6, nums.count = 4

L’ajout d’éléments n’est efficace que lorsqu’il s’ajoute au dos de la liste. L'insertion au milieu oblige le tableau à décaler tous les éléments, opération O (n). La suppression d'éléments est également O (n), car le tableau doit déplacer les éléments vers l'arrière.

System.Collections.Generic.LinkedList (of t) : si vous n'avez pas besoin d'un accès aléatoire ou indexé aux éléments de votre liste, par exemple, vous envisagez uniquement d'ajouter des éléments et d'effectuer une itération à partir du premier. pour durer, alors une LinkedList est votre amie. Les insertions et les extractions sont O (1), la recherche est O (n).

Answer 2

Vous devriez utiliser la liste générique < > ( System.Collections.Generic.List ) à cette fin. Il fonctionne à la temps d'amortissement constant .

Il partage également les fonctionnalités suivantes avec les tableaux.

• Accès aléatoire rapide (vous pouvez accéder à n’importe quel élément de la liste en O (1))
• Il est rapide de passer en boucle
• Lent pour insérer et supprimer des objets au début ou au milieu (puisqu’il doit faire une copie de la liste entière)

Si vous avez besoin d'insertions et de suppressions rapides au début ou à la fin, utilisez la liste liée ou les files d'attente

Answer 3

Est-ce que le LinkedList < T & Gt; structurer le travail pour vous? Ce n'est pas (dans certains cas) aussi intuitif qu'un tableau simple, mais c'est très rapide.

• Ajouter le dernier à ajouter à la fin
• AddBefore / AddAfter à insérer dans la liste
• AddPremier à ajouter au début

Ce n'est pas si rapide pour un accès aléatoire cependant, car vous devez parcourir la structure pour accéder à vos éléments ... Cependant, il a des méthodes .ToList () et .ToArray () pour récupérer une copie de la structure dans la liste / array form donc pour un accès en lecture, vous pouvez le faire en un tour de main. L'augmentation des performances des inserts peut compenser la diminution des performances liée à la nécessité d'un accès aléatoire ou non. Cela dépendra entièrement de votre situation.

Il existe également cette référence qui vous aidera à choisir la bonne voie à suivre:

Quand utiliser une liste chaînée sur un tableau / une liste de tableaux?

Answer 4

Qu'est-ce qui & est suffisant? & pour vous? Que voulez-vous faire exactement avec cette structure de données?

Aucune structure de tableau (c'est-à-dire un accès O (n)) ne permet une insertion au milieu sans exécution O (n); l’insertion à la fin est O (n) dans le pire des cas, un O (1) amorti pour des tableaux auto-redimensionnant comme ArrayList.

Peut-être que les hashtables (accès O (1) amorti et insertion n'importe où, mais O (n) cas le plus défavorable pour l'insertion) ou les arbres (O (log (n)) pour l'accès et l'insertion n'importe où, garantis) sont mieux adaptés.

Answer 5

Si la rapidité est votre problème, je ne vois pas en quoi la réponse sélectionnée est meilleure qu’un tableau brut, bien qu’elle se redimensionne elle-même, elle utilise le même mécanisme que celui que vous utiliseriez pour redimensionner un tableau (et devrait prendre une touche plus longue) SAUF si vous ajoutez toujours à la fin, auquel cas il devrait faire les choses un peu plus intelligemment, car il alloue un morceau à la fois au lieu d'un seul élément.

Si vous ajoutez souvent au début / au milieu de votre collection et que vous n'indexez pas très souvent dans le milieu / la fin, vous souhaiterez probablement une liste chaînée. Cela aura le temps d’insertion le plus rapide et le temps d’itération sera très long, cela ne sert à rien d’indexer (comme regarder le 3ème élément à partir de la fin ou le 72ème élément).