La façon la plus rapide d'étendre un tableau

Question

Je cherche le moyen le plus rapide d'étendre un tableau. Peu importe si c'est seulement pour la longueur + 1 ou la longueur + x, cela doit être le moyen le plus rapide.

Voici un exemple :

var arr = new int [200];
for(int i = 0; i < 200; i++)
   arr[i] = i;

Et maintenant je veux étendre arr de 5 éléments commençant à la position d'index 20.

var arr2 = new int [] { 999, 999, 999, 999, 999 }

Comment puis-je placer arr2 à l'intérieur de arr en utilisant le moyen le plus rapide en termes de performance ?

Le résultat doit ressembler à ceci 0,1,2,3,4....20, 999, 999, 999, 999, 999, 21, 22, 23, 24....199

Answer 1

Créez un nouveau tableau de la taille souhaitée, puis utilisez la méthode statique Array.Copy pour copier les tableaux originaux dans le nouveau.

Vous ne pouvez pas "étendre" un tableau, vous ne pouvez créer un plus grand et y copier l'original.

De plus, envisagez d'utiliser List ou LinkedList<> au lieu d'un tableau, sauf si vous avez besoin d'un contrôle extrêmement fin sur ce qui est en mémoire.

Answer 2

Il est beaucoup plus facile d'utiliser une liste. Mais si vous devez utiliser des tableaux, vous devez créer un nouveau tableau de taille 205 et copier les valeurs des deux tableaux sources, car la taille du tableau est constante.

Answer 3

Votre meilleur choix est d'utiliser quelque chose comme List plutôt qu'un tableau. Mais si vous devez utiliser un tableau:

int[] arr1 = new int[200];
// initialiser le tableau
int[] arr2 = new int[]{999, 999, 999, 999, 999};

int targetPos = 20;

// redimensionne le tableau, en copiant les éléments
Array.Resize(ref arr1, arr1.Length + arr2.Length);

// déplace la fin du tableau vers le bas
Buffer.BlockCopy(arr1, 4*targetPos, arr1, 4*(targetPos+arr2.Length), 4*(arr1.Length - targetPos));

// copier arr2 à la bonne position
Buffer.BlockCopy(arr2, 0, 4*arr1.targetPos, 4*arr2.Length);

Il pourrait être plus rapide de créer un nouveau tableau et de copier les éléments, comme ceci.

int[] newArray = new int[arr1.Length + arr2.Length];

// copier la première partie du tableau original
Buffer.BlockCopy(arr1, 0, newArray, 0, 4*targetPos);

// copier le deuxième tableau
Buffer.BlockCopy(arr2, 0, newArray, 4*targetPos, 4*arr2.Length);

// copier le reste du tableau original
Buffer.BlockCopy(arr1, 4*targetPos, newArray, 4*(targetPos + arr2.Length), 4*(arr1.Length - targetPos));

// et remplacer le tableau original
arr1 = newArray;

La version la plus rapide dépendra de la valeur de targetPos. La deuxième version sera plus rapide lorsque targetPos est petite. Lorsque targetPos est petit, la première version doit copier beaucoup de données deux fois. La deuxième version ne copie jamais plus qu'elle n'en a besoin.

BlockCopy est un peu compliqué à utiliser car il nécessite des décalages en octets, c'est la raison de toutes les multiplications par quatre dans le code. Il serait peut-être préférable d'utiliser Array.Copy dans la deuxième version ci-dessus. Cela évitera d'avoir à multiplier tout par 4 (et d'oublier parfois).

Answer 4

Si vous connaissez la longueur de tableau, dimensionnez-le à cette longueur,

var ints  = new int[someFixedLength];

Si vous avez une idée vague de la longueur, utilisez une liste générique.

var ints = new List(someVagueLength);

Les deux types implémentent IList mais le type List gère la redimension de l'array interne de manière générique, c'est généralement la façon la plus rapide.

---

Remarque: le .Count initial de la List sera 0, mais l'array interne sera dimensionné à la taille que vous passez au constructeur.

---

Si vous avez besoin de copier des données entre des tableaux, la façon la plus rapide est d'utiliser Buffer.BlockCopy, donc dans votre exemple

Buffer.BlockCopy(arr2, 0, arr, sizeof(int) * 20, sizeof(int) * 5);

copie tous les 5 int de arr2 dans les indices 20, 21 ... 24 de arr.

Il n'y a pas de moyen plus rapide de le faire avec C# (actuellement).

Answer 5

Une réponse montrant des benchmarks de timing est donnée ici: Meilleure façon de combiner deux ou plusieurs tableaux d'octets en C#. Si vous considérez le "tableau que vous insérez dans" comme les tableaux 1 et 3, et le "tableau à insérer" comme le tableau 2, alors l'exemple "concaténer trois tableaux" s'applique directement.

Remarquez le point à la fin de la réponse acceptée: la méthode qui est plus rapide pour créer donne un tableau plus lent à accéder (c'est pourquoi j'ai demandé si vous vous souciez de la vitesse de création ou de la vitesse d'accès).