Comment et quand abandonner l'utilisation des tableaux en C #?

Question

On m'a toujours dit que l'ajout d'un élément à un tableau se produit comme suit:

  

Une copie vide du tableau + 1element est   créé et ensuite les données de la   tableau d'origine est copié dans ce puis   les nouvelles données pour le nouvel élément est   puis chargé

Si cela est vrai, l'utilisation d'un tableau dans un scénario nécessitant une activité importante des éléments est contre-indiquée en raison de l'utilisation de la mémoire et du processeur, correct?

Si tel est le cas, ne devriez-vous pas essayer d'éviter autant que possible d'utiliser un tableau lorsque vous ajouterez beaucoup d'éléments? Devez-vous utiliser iStringMap à la place? Si tel est le cas, que se passera-t-il si vous avez besoin de plus de deux dimensions ET devez ajouter de nombreux ajouts d'éléments? Est-ce que vous prenez juste le coup de la performance ou y at-il autre chose qui devrait être utilisé?

Answer 1

Recherchez le générique List<T> en remplacement des tableaux. Ils supportent la plupart des choses que font les baies, y compris l'allocation d'une taille de stockage initiale si vous le souhaitez.

Answer 2

Cela dépend vraiment de ce que vous entendez par & "ajouter. &";

.

Si vous voulez dire:

T[] array;
int i;
T value;
...
if (i >= 0 && i <= array.Length)
    array[i] = value;

Ensuite, non, cela ne crée pas de nouveau tableau et constitue en fait le moyen le plus rapide de modifier n'importe quel type d'IList dans .NET.

Si, toutefois, vous utilisez quelque chose comme ArrayList, List, Collection, etc., appelez le & "Ajouter &"; La méthode peut créer un nouveau tableau - mais ils sont intelligents à ce sujet, ils ne font pas que redimensionner d'un élément, ils grandissent géométriquement. Par conséquent, si vous ajoutez beaucoup de valeurs uniquement Pendant ce temps, il devra allouer un nouveau tableau. Même dans ce cas, vous pouvez utiliser la & Quot; Capacité & Quot; propriété pour la forcer à se développer avant la main, si vous savez combien d'éléments vous ajoutez (list.Capacity += numberOfAddedElements)

Answer 3

En général, je préfère éviter l’utilisation de tableaux. Utilisez simplement List & Lt; T & Gt ;. Il utilise un tableau de taille dynamique en interne et est assez rapide pour la plupart des utilisations. Si vous utilisez des tableaux multidimensionnels, utilisez List & Lt; List & Lt; List & Lt; T & Gt; & Gt; & Gt; si tu dois. Ce n’est pas pire en termes de mémoire et il est beaucoup plus simple d’ajouter des éléments.

Si vous êtes dans les 0,1% d'utilisation nécessitant une vitesse extrême, assurez-vous que ce sont les accès à votre liste qui posent vraiment problème avant de tenter de l'optimiser.

Answer 4

Si vous allez ajouter / supprimer beaucoup d'éléments, utilisez simplement une liste. Si c'est multidimensionnel, vous pouvez toujours utiliser une liste & Lt; List & Lt; int & Gt; & Gt; ou quelque chose.

D'autre part, les listes sont moins efficaces que les tableaux si vous faites principalement traverser la liste, car les tableaux se trouvent tous à la même place dans le cache de votre CPU, où les objets d'une liste sont dispersés partout.

Si vous souhaitez utiliser un tableau pour une lecture efficace, mais que vous allez ajouter & "ajouter &"; éléments fréquemment, vous avez deux options principales:

1) Générez-le sous forme de liste (ou liste de listes), puis utilisez ToArray () pour le transformer en une structure de tableau efficace.

2) Allouez le tableau pour qu'il soit plus grand que nécessaire, puis placez les objets dans les cellules pré-allouées. Si vous finissez par avoir besoin de plus d'éléments que ce que vous avez pré-alloué, vous pouvez simplement réaffecter le tableau lorsqu'il se remplit, en doublant la taille à chaque fois. Cela donne à O (log n) des performances de redimensionnement au lieu de O (n) comme ce serait le cas avec un tableau reallocate une fois par ajout. Notez que c'est en gros le fonctionnement de StringBuilder, qui vous permet d'ajouter plus rapidement en continu à une chaîne.

Answer 5

  

Quand abandonner l'utilisation des tableaux

1. Tout d’abord, lorsque la sémantique des tableaux ne correspond pas à votre intention - Vous avez besoin d’une collection en croissance dynamique? Un ensemble qui n'autorise pas les doublons? Une collection qui doit rester immuable? Évitez les tableaux dans tous les cas. C'est 99% des cas. Juste énoncer le point de base évident.

2. Deuxièmement, lorsque vous ne codez pas pour respecter les critères de performances absolus - cela représente environ 95% des cas. Les tableaux fonctionnent mieux marginalement , en particulier lors de l'itération . Cela n'a presque jamais d'importance.

3. Lorsque vous n'êtes pas forcé par un argument avec params mot clé , je souhaitais simplement IEnumerable<T> accepter n'importe quel ICollection<T>.Contains ou même mieux langage lui-même pour désigner une séquence (et non un type de structure).

4. Lorsque vous n'écrivez pas du code hérité, ni ne travaillez avec des interfaces

En bref, il est très rare que vous ayez réellement besoin d’un tableau. J'ajouterai pourquoi on peut l'éviter?

1. La principale raison d'éviter les tableaux imo est conceptuelle. Les tableaux sont plus proches de la mise en œuvre et plus éloignés de l'abstraction. Les tableaux indiquent plus comment cela se fait que ce qui est fait , ce qui va à l’encontre de l’esprit des langages de haut niveau. Ce n'est pas surprenant, étant donné que les tableaux sont plus proches du métal, ils sortent directement d'un type spécial (même si en interne, array est une classe). Pour ne pas être pédagogique, les tableaux se traduisent vraiment par un sens sémantique très rarement nécessaire. La sémantique la plus utile et la plus fréquente est celle des collections avec des entrées quelconques, des ensembles avec des éléments distincts, des mappes de valeurs de clé, etc., avec toute combinaison de variantes pouvant être ajoutées, lues, immuables et respectant l'ordre. Pensez-y, vous voudrez peut-être une collection pouvant être ajoutée ou une collection en lecture seule avec des éléments prédéfinis sans autre modification, mais à quelle fréquence votre logique ressemble-t-elle à & "Je souhaite une collection pouvant être ajoutée de façon dynamique mais uniquement un nombre fixe d'entre eux et devrait aussi être modifiable " Très rare je dirais.

2. Array a été conçu à l’époque des pré-génériques. Il imite la généricité avec de nombreux piratages de temps d’exécution et il montrera ses bizarreries ici et là. Certaines des captures que j'ai trouvées:

   1. Covariance cassée.

      string[] strings = ...
      object[] objects = strings;
      objects[0] = 1; //compiles, but gives a runtime exception.
      

   2. Les tableaux peuvent vous donner une référence à un struct! . C'est comme nulle part ailleurs. Un échantillon:

      struct Value { public int mutable; }
      
      var array = new[] { new Value() };  
      array[0].mutable = 1; //<-- compiles !
      //a List<Value>[0].mutable = 1; doesnt compile since editing a copy makes no sense
      print array[0].mutable // 1, expected or unexpected? confusing surely
      

   3. Des méthodes implémentées à l'exécution telles que Equals peuvent être différent pour les structures et les classes . Ce n'est pas grave, mais si vous oubliez de remplacer correctement non générique Length pour les types de référence qui attendent de la collection générique que generic [] , vous obtiendrez une erreur. résultats.

      public class Class : IEquatable<Class>
      {
          public bool Equals(Class other)
          {
              Console.WriteLine("generic");
              return true;
          }
          public override bool Equals(object obj)
          {
              Console.WriteLine("non generic");
              return true;
          } 
      }
      
      public struct Struct : IEquatable<Struct>
      {
          public bool Equals(Struct other)
          {
              Console.WriteLine("generic");
              return true;
          }
          public override bool Equals(object obj)
          {
              Console.WriteLine("non generic");
              return true;
          } 
      }
      
      class[].Contains(test); //prints "non generic"
      struct[].Contains(test); //prints "generic"
      

   4. La propriété T[] et l'indexeur ArrayLength sur ArrayIndex semblent être des propriétés standard auxquelles vous pouvez accéder par réflexion (ce qui devrait impliquer un peu de magie), mais lorsque vous utilisez des arbres d'expression, vous devez cracher exactement le même code que le compilateur. Il existe List<T> et ReadOnlyCollection<T> des méthodes pour le faire séparément. Une de ces question est ici . Un autre exemple:

      Expression<Func<string>> e = () => new[] { "a" }[0];
      //e.Body.NodeType == ExpressionType.ArrayIndex
      
      Expression<Func<string>> e = () => new List<string>() { "a" }[0];
      //e.Body.NodeType == ExpressionType.Call;
      

  

Comment abandonner l'utilisation des tableaux

Le substitut le plus couramment utilisé est <=> qui a un nettoyantAPI. Mais il s’agit d’une structure en croissance dynamique qui vous permet d’ajouter à un <=> à la fin ou d’insérer n’importe où et à n’importe quelle capacité. Il n'y a pas de substitut au comportement exact d'un tableau, mais les gens utilisent généralement des tableaux comme collection en lecture seule où vous ne pouvez rien ajouter à la fin. Un substitut est <=>. Je porte cette méthode d'extension:

public ReadOnlyCollection<T> ToReadOnlyCollection<T>(IEnumerable<T> source)
{
    return source.ToList().AsReadOnly();
}

Answer 6

Lorsque le tableau est redimensionné, un nouveau tableau doit être alloué et le contenu copié. Si vous modifiez uniquement le contenu du tableau, il ne s'agit que d'une affectation de mémoire.

Ainsi, vous ne devriez pas utiliser de tableaux lorsque vous ne connaissez pas la taille du tableau ou que sa taille est susceptible de changer. Cependant, si vous avez un tableau de longueur fixe, ils constituent un moyen simple de récupérer des éléments par index.

Answer 7

ArrayList et List agrandissent le tableau de plus d'un si nécessaire (je pense que c'est en doublant la taille, mais je n'ai pas vérifié le source). Ils constituent généralement le meilleur choix lorsque vous construisez un tableau de taille dynamique.

Lorsque vos repères indiquent que le redimensionnement d'un tableau ralentit sérieusement votre application (rappelez-vous que l'optimisation prématurée est la racine de tout mal), vous pouvez évaluer l'écriture d'une classe de tableau personnalisée avec un comportement de redimensionnement modifié.

Answer 8

En règle générale, si vous devez disposer des performances de recherche indexées BEST, il est préférable de créer d'abord une liste, puis de le transformer en tableau, ce qui vous payera une petite pénalité au début, mais en évitant toute modification ultérieure. Si le problème est que vous allez ajouter continuellement de nouvelles données et supprimer des données anciennes, vous pouvez utiliser une liste de tableaux (ArrayList) ou une liste à des fins pratiques, mais gardez à l'esprit qu'il ne s'agit que de tableaux de cas spéciaux. Quand ils & Quot; grandissent & Quot; ils allouent un tout nouveau tableau et y copient tout ce qui est extrêmement lent.

ArrayList est simplement un tableau qui se développe si nécessaire. Ajouter est amorti O (1), veillez simplement à ce que le redimensionnement ne se produise pas au mauvais moment. Insert is O (n), tous les éléments à droite doivent être déplacés. Remove is O (n), tous les éléments à droite doivent être déplacés.

Il est également important de garder à l'esprit que Liste n'est pas une liste chaînée. C'est juste une ArrayList dactylographiée. La documentation de la liste indique qu'elle fonctionne mieux dans la plupart des cas, mais qu'elle ne pas dire pourquoi.

La meilleure chose à faire est de choisir une structure de données adaptée à votre problème. Cela dépend BEAUCOUP de choses et vous pouvez donc parcourir la System.Collections.Generic , espace de noms.

Dans ce cas particulier, je dirais que si vous pouvez obtenir une bonne valeur de clé Dictionnaire serait votre meilleur pari. Il a insérer et supprimer qui approche O (1). Cependant, même avec un dictionnaire, vous devez faire attention à ne pas le laisser redimensionner son tableau interne (opération O (n)). Il est préférable de leur laisser beaucoup de place en spécifiant une capacité initiale plus importante dans le constructeur.

-Rick

Answer 9

Un tableau standard doit être défini avec une longueur, qui réserve toute la mémoire dont il a besoin dans un bloc contigu. Ajouter un élément au tableau le placerait à l'intérieur du bloc de mémoire déjà réservée.

Answer 10

Les tableaux sont parfaits pour quelques écritures et lectures, en particulier celles de nature itérative - pour toute autre chose, utilisez l'une des nombreuses autres structures de données.

Answer 11

Vous avez raison, un tableau est idéal pour les recherches. Cependant, les modifications de la taille du tableau sont coûteuses.

Vous devez utiliser un conteneur qui prend en charge les ajustements de taille incrémentiels dans le scénario dans lequel vous modifiez la taille du tableau. Vous pouvez utiliser une liste de tableaux qui vous permet de définir la taille initiale. Vous pouvez également vérifier en permanence la taille par rapport à la capacité, puis incrémenter la capacité d'un gros bloc pour limiter le nombre de redimensionnements.

Ou vous pouvez simplement utiliser une liste chaînée. Cependant, les recherches sont lentes ...

Answer 12

Ce message de forum pourrait vous être utile ou non en ce qui concerne l'efficacité de divers types de tableaux: Tableaux C # - multidimensionnels et lexicographiques

Answer 13

Si je pense que je vais ajouter beaucoup d'éléments à la collection au cours de sa durée de vie, j'utiliserai une liste. Si je sais avec certitude quelle sera la taille de la collection quand elle sera déclarée, j'utiliserai un tableau.

Une autre fois que j'utilise généralement un tableau sur une liste, c'est lorsque je dois retourner une collection en tant que propriété d'un objet. Je ne veux pas que les appelants ajoutent des éléments de cette collection via les méthodes Add de la liste, mais plutôt qu'ils ajoutent des éléments. à la collection via l'interface de mon objet. Dans ce cas, je prendrai la liste interne, appellerai ToArray et renverrai un tableau.

Answer 14

Si vous allez ajouter beaucoup, et , vous ne ferez pas d'accès aléatoire (comme myArray[i]). Vous pouvez envisager d'utiliser une liste chaînée (LinkedList<T>), car il ne sera jamais nécessaire de & "Grandir &"; comme l'implémentation List<T>. Gardez toutefois à l'esprit que vous ne pouvez réellement accéder qu'aux éléments d'une IEnumerable<T> implémentation à l'aide de l'interface <=>.

Answer 15

La meilleure chose à faire est d’allouer autant de mémoire que nécessaire au départ, si possible. Cela évitera à .NET de faire des appels supplémentaires pour obtenir de la mémoire sur le tas. Si vous ne le faites pas, il est judicieux d’allouer des blocs de cinq ou un nombre quelconque pour votre application.

C’est une règle que vous pouvez appliquer à n'importe quoi vraiment.