Préfixer à un tableau C#

Question

Étant donné un byte[] valeurs peuplé en C#, je veux ajouter la valeur (byte)0x00 au début du tableau. Je suppose que cela nécessitera de créer un nouveau tableau et d'y ajouter le contenu de l'ancien tableau. La vitesse est un aspect important de mon application. Quel est le meilleur moyen de le faire?

-- ÉDITER --

Le byte[] est utilisé pour stocker les paramètres de l'algorithme de signature numérique (DSA). L'opération ne devra être effectuée qu'une seule fois par tableau, mais la vitesse est importante car je peux potentiellement effectuer cette opération sur de nombreux byte[] différents.

Answer 1

Si vous ne comptez effectuer cette opération qu'une seule fois, il n'y a pas beaucoup de choix. Le code fourni par la réponse de Monroe devrait très bien faire l'affaire.

byte[] newValues = new byte[values.Length + 1];
newValues[0] = 0x00;                                // définir la valeur précédente
Array.Copy(values, 0, newValues, 1, values.Length); // copier les anciennes valeurs

Cependant, si vous envisagez d'effectuer cette opération plusieurs fois, vous avez plus de choix. Il y a un problème fondamental avec l'ajout de données au début d'un tableau qui n'est pas une opération efficace, vous pourriez donc choisir d'utiliser une structure de données alternative.

Une LinkedList peut ajouter efficacement des données au début, mais elle est généralement moins efficace pour la plupart des tâches car elle implique beaucoup plus d'allocation/libération de mémoire et perd également la localité de la mémoire, ce qui pourrait ne pas être un gain net.

Une file à double extrémité (connue sous le nom de deque) serait une fantastique structure de données pour vous. Vous pouvez ajouter efficacement au début ou à la fin, et accéder efficacement aux données n'importe où dans la structure (mais vous ne pouvez pas insérer efficacement ailleurs qu'au début ou à la fin). Le principal problème ici est que le .NET ne fournit pas d'implémentation de deque. Vous devriez trouver une bibliothèque tierce avec une implémentation.

Vous pouvez également économiser beaucoup lors de la copie en gardant une trace des "données que je dois ajouter au début" (en utilisant une List/Queue/etc.) et en attendant d'ajouter réellement les données aussi longtemps que possible, afin de minimiser la création de nouveaux tableaux autant que possible, tout en limitant le nombre de copies des éléments existants.

Vous pouvez également envisager de modifier la structure afin d'ajouter à la fin, plutôt qu'au début (même si vous savez que vous devrez le renverser plus tard). Si vous ajoutez beaucoup de données en peu de temps, il peut être utile de stocker les données dans une List (qui peut ajouter efficacement à la fin) et d'ajouter à la fin. Selon vos besoins, il pourrait même être intéressant de créer une classe qui est un wrapper pour une List et qui cache le fait qu'elle est inversée. Vous pourriez faire un indexeur qui mappe i à Count-i, etc. pour que cela apparaisse, de l'extérieur, comme si vos données étaient stockées normalement, même si la List interne tient en réalité les données à l'envers.

Answer 2

Ok les gars, regardons le problème de performance concernant cette question. Ceci n'est pas une réponse, juste un microbenchmark pour voir quelle option est la plus efficace.

Alors, définissons le scénario :

• Un tableau d'octets de 1 000 000 d'éléments, remplis de manière aléatoire
• Nous devons préfixer l'élément 0x00

Nous avons 3 options :

1. Créer manuellement et remplir le nouveau tableau
2. Créer manuellement le nouveau tableau et utiliser Array.Copy (@Monroe)
3. Créer une liste, charger le tableau, insérer l'élément et convertir la liste en tableau

Voici le code :

    byte[] tableauOctets = new byte[1000000];

    for (int i = 0; i < tableauOctets.Length; i++)
    {
        tableauOctets[i] = Convert.ToByte(DateTime.Now.Second);
    }

    Stopwatch chronometre = new Stopwatch();

    //#1 Création et remplissage manuel d'un nouveau tableau

    chronometre.Start();

    byte[] tableauOctetsEtendu1 = new byte[tableauOctets.Length + 1];

    tableauOctetsEtendu1[0] = 0x00;

    for (int i = 0; i < tableauOctets.Length; i++)
    {
        tableauOctetsEtendu1[i + 1] = tableauOctets[i];
    }

    chronometre.Stop();
    Console.WriteLine(string.Format("#1: {0} ms", chronometre.ElapsedMilliseconds));
    chronometre.Reset();

    //#2 Utilisation d'un nouveau tableau et Array.Copy

    chronometre.Start();

    byte[] tableauOctetsEtendu2 = new byte[tableauOctets.Length + 1];
    tableauOctetsEtendu2[0] = 0x00;                                
    Array.Copy(tableauOctets, 0, tableauOctetsEtendu2, 1, tableauOctets.Length);

    chronometre.Stop();
    Console.WriteLine(string.Format("#2: {0} ms", chronometre.ElapsedMilliseconds));
    chronometre.Reset();

    //#3 Utilisation d'une Liste

    chronometre.Start();

    List listeOctets = new List();
    listeOctets.AddRange(tableauOctets);
    listeOctets.Insert(0, 0x00);

    byte[] tableauOctetsEtendu3 = listeOctets.ToArray();

    chronometre.Stop();
    Console.WriteLine(string.Format("#3: {0} ms", chronometre.ElapsedMilliseconds));
    chronometre.Reset();

    Console.ReadLine();

Et les résultats sont :

#1: 9 ms
#2: 1 ms
#3: 6 ms

Je l'ai exécuté plusieurs fois et j'ai obtenu des nombres différents, mais la proportion est toujours la même : #2 est toujours le choix le plus efficace.

Ma conclusion : les tableaux sont plus efficaces que les Listes (bien qu'ils offrent moins de fonctionnalités), et d'une manière ou d'une autre, Array.Copy est vraiment optimisé (j'aimerais comprendre cela, cependant).

Tout retour sera apprécié.

Cordialement.

PS : ce n'est pas un post de confrontation, nous sommes sur un site de questions-réponses pour apprendre et enseigner. Et apprendre.

Answer 3

La manière la plus simple et la plus propre pour .NET 4.7.1 et version supérieure est d'utiliser la méthode sans effet secondaire Prepend().

Ajoute une valeur au début de la séquence.

Exemple

// Créer un tableau de nombres
var numbers = new[] { 1, 2, 3 };

// Essayer de préfixer toute valeur du même type
var results = numbers.Prepend(0);

// le résultat est 0, 1, 2, 3
Console.WriteLine(string.Join(", ", results));

Answer 4

Comme vous l'avez supposé, la manière la plus rapide de le faire est de créer un nouveau tableau de longueur + 1 et de copier toutes les anciennes valeurs.

Si vous allez faire cela plusieurs fois, alors je suggère d'utiliser une List au lieu de byte[], car le coût de réallocation et de copie lors de l'agrandissement du stockage sous-jacent est amorti de manière plus efficace; dans le cas habituel, le vecteur sous-jacent dans la List est agrandi d'un facteur de deux chaque fois qu'une addition ou insertion est faite dans la List qui dépasserait sa capacité actuelle.

...

byte[] newValues = new byte[values.Length + 1];
newValues[0] = 0x00;                                // définir la valeur préfixée
Array.Copy(values, 0, newValues, 1, values.Length); // copier les anciennes valeurs

Answer 5

Lorsque j'ai besoin d'ajouter fréquemment des données tout en voulant un accès aléatoire en O(1) aux éléments individuels, j'utiliserai un tableau qui est sur-assigné par une certaine quantité de rembourrage pour ajouter rapidement de nouvelles valeurs. Cela signifie que vous devez stocker la longueur réelle du contenu dans une autre variable, car array.length indiquera la longueur + le rembourrage. Une nouvelle valeur est ajoutée en utilisant un emplacement du rembourrage, aucune allocation ni copie n'est nécessaire tant que vous n'avez plus de rembourrage. En fait, l'allocation est amortie sur plusieurs opérations d'ajout. Il y a des compromis de vitesse et d'espace, car si vous avez beaucoup de ces structures de données, vous pourriez avoir une quantité raisonnable de rembourrage utilisée à un moment donné dans le programme.

La même technique peut être utilisée en préfixant. Tout comme pour l'ajout, vous pouvez introduire une interface ou une abstraction entre les utilisateurs et l'implémentation: vous pouvez avoir plusieurs emplacements de rembourrage afin qu'une nouvelle allocation de mémoire ne soit nécessaire que de temps en temps. Comme certains l'ont suggéré ci-dessus, vous pouvez également implémenter une interface de préfixage avec une structure de données d'ajout qui inverse les index.

J'emballerais la structure de données sous la forme d'une implémentation d'une interface de collection générique, de sorte que l'interface apparaisse assez normale pour l'utilisateur (comme une liste de tableaux ou quelque chose comme ça).

(De plus, si la suppression est prise en charge, il est probablement utile de vider les éléments dès qu'ils sont supprimés pour aider à réduire la charge du GC.)

Le point principal est de considérer l'implémentation et l'interface séparément, car les découpler vous donne la flexibilité de choisir des implémentations variées ou de masquer les détails de l'implémentation en utilisant une interface minimale.

Il existe de nombreuses autres structures de données que vous pourriez utiliser en fonction de leur applicabilité à votre domaine. Cordes ou tampon d'écart; voir Quelle est la meilleure structure de données adaptée pour mettre en œuvre un éditeur comme le bloc-notes?; Les tries font aussi des choses utiles.