Quelles sont les différences entre un tableau multidimensionnel et un tableau de tableaux en C #?

Quelles sont les différences entre les tableaux multidimensionnels double[,]et les tableaux de tableaux double[][]en C #?

S'il y a une différence, quelle est la meilleure utilisation pour chacun?

Les tableaux de tableaux (tableaux dentelés) sont plus rapides que les tableaux multidimensionnels et peuvent être utilisés plus efficacement. Les tableaux multidimensionnels ont une syntaxe plus agréable.

Si vous écrivez du code simple à l'aide de tableaux irréguliers et multidimensionnels, puis inspectez l'assembly compilé avec un désassembleur IL, vous verrez que le stockage et la récupération à partir de tableaux dentelés (ou unidimensionnels) sont de simples instructions IL tandis que les mêmes opérations pour les tableaux multidimensionnels sont la méthode invocations toujours plus lentes.

Considérez les méthodes suivantes:

static void SetElementAt(int[][] array, int i, int j, int value)
{
    array[i][j] = value;
}

static void SetElementAt(int[,] array, int i, int j, int value)
{
    array[i, j] = value;
}

Leur IL sera le suivant:

.method private hidebysig static void  SetElementAt(int32[][] 'array',
                                                    int32 i,
                                                    int32 j,
                                                    int32 'value') cil managed
{
  // Code size       7 (0x7)
  .maxstack  8
  IL_0000:  ldarg.0
  IL_0001:  ldarg.1
  IL_0002:  ldelem.ref
  IL_0003:  ldarg.2
  IL_0004:  ldarg.3
  IL_0005:  stelem.i4
  IL_0006:  ret
} // end of method Program::SetElementAt

.method private hidebysig static void  SetElementAt(int32[0...,0...] 'array',
                                                    int32 i,
                                                    int32 j,
                                                    int32 'value') cil managed
{
  // Code size       10 (0xa)
  .maxstack  8
  IL_0000:  ldarg.0
  IL_0001:  ldarg.1
  IL_0002:  ldarg.2
  IL_0003:  ldarg.3
  IL_0004:  call       instance void int32[0...,0...]::Set(int32,
                                                           int32,
                                                           int32)
  IL_0009:  ret
} // end of method Program::SetElementAt

Lorsque vous utilisez des tableaux irréguliers, vous pouvez facilement effectuer des opérations telles que l'échange de ligne et le redimensionnement de ligne. Dans certains cas, l'utilisation de tableaux multidimensionnels sera peut-être plus sûre, mais même Microsoft FxCop indique que les tableaux irréguliers doivent être utilisés au lieu de multidimensionnels lorsque vous les utilisez pour analyser vos projets.

Un tableau multidimensionnel crée une belle disposition de mémoire linéaire tandis qu'un tableau irrégulier implique plusieurs niveaux supplémentaires d'indirection.

La recherche de la valeur jagged[3][6]dans un tableau irrégulier var jagged = new int[10][5]fonctionne comme ceci: recherchez l'élément à l'index 3 (qui est un tableau) et recherchez l'élément à l'index 6 dans ce tableau (qui est une valeur). Pour chaque dimension dans ce cas, il existe une recherche supplémentaire (il s'agit d'un modèle d'accès à la mémoire coûteux).

Un tableau multidimensionnel est disposé linéairement en mémoire, la valeur réelle est trouvée en multipliant ensemble les index. Cependant, étant donné le tableau var mult = new int[10,30], la Lengthpropriété de ce tableau multidimensionnel renvoie le nombre total d'éléments, c'est-à-dire 10 * 30 = 300.

La Rankpropriété d'un tableau dentelé est toujours 1, mais un tableau multidimensionnel peut avoir n'importe quel rang. La GetLengthméthode de n'importe quel tableau peut être utilisée pour obtenir la longueur de chaque dimension. Pour le tableau multidimensionnel dans cet exemple, mult.GetLength(1)renvoie 30.

L'indexation du tableau multidimensionnel est plus rapide. Par exemple, étant donné le tableau multidimensionnel dans cet exemple mult[1,7]= 30 * 1 + 7 = 37, obtenez l'élément à cet index 37. Il s'agit d'un meilleur modèle d'accès à la mémoire car un seul emplacement de mémoire est impliqué, qui est l'adresse de base du tableau.

Un tableau multidimensionnel alloue donc un bloc de mémoire continue, tandis qu'un tableau dentelé n'a pas à être carré, par exemple jagged[1].Lengthn'a pas à être égal jagged[2].Length, ce qui serait vrai pour tout tableau multidimensionnel.

Performance

Les tableaux multidimensionnels en termes de performances devraient être plus rapides. Beaucoup plus rapide, mais en raison d'une implémentation CLR vraiment mauvaise, ils ne le sont pas.

 23.084  16.634  15.215  15.489  14.407  13.691  14.695  14.398  14.551  14.252 
 25.782  27.484  25.711  20.844  19.607  20.349  25.861  26.214  19.677  20.171 
  5.050   5.085   6.412   5.225   5.100   5.751   6.650   5.222   6.770   5.305 

La première ligne est le minutage des tableaux irréguliers, la seconde montre les tableaux multidimensionnels et la troisième, c'est comme ça que ça devrait être. Le programme est illustré ci-dessous, pour info, il a été testé en mono. (Les horaires des fenêtres sont très différents, principalement en raison des variations de mise en œuvre du CLR).

Sur les fenêtres, les synchronisations des tableaux irréguliers sont largement supérieures, à peu près la même que ma propre interprétation de ce à quoi devrait ressembler le tableau multidimensionnel, voir 'Single ()'. Malheureusement, le compilateur JIT de Windows est vraiment stupide, et cela rend malheureusement ces discussions sur les performances difficiles, il y a trop d'incohérences.

Ce sont les timings que j'ai obtenus sur les fenêtres, même chose ici, la première ligne est des tableaux irréguliers, le deuxième multidimensionnel et le troisième ma propre implémentation du multidimensionnel, notez à quel point cela est plus lent sur les fenêtres par rapport au mono.

  8.438   2.004   8.439   4.362   4.936   4.533   4.751   4.776   4.635   5.864
  7.414  13.196  11.940  11.832  11.675  11.811  11.812  12.964  11.885  11.751
 11.355  10.788  10.527  10.541  10.745  10.723  10.651  10.930  10.639  10.595

Code source:

using System;
using System.Diagnostics;
static class ArrayPref
{
    const string Format = "{0,7:0.000} ";
    static void Main()
    {
        Jagged();
        Multi();
        Single();
    }

    static void Jagged()
    {
        const int dim = 100;
        for(var passes = 0; passes < 10; passes++)
        {
            var timer = new Stopwatch();
            timer.Start();
            var jagged = new int[dim][][];
            for(var i = 0; i < dim; i++)
            {
                jagged[i] = new int[dim][];
                for(var j = 0; j < dim; j++)
                {
                    jagged[i][j] = new int[dim];
                    for(var k = 0; k < dim; k++)
                    {
                        jagged[i][j][k] = i * j * k;
                    }
                }
            }
            timer.Stop();
            Console.Write(Format,
                (double)timer.ElapsedTicks/TimeSpan.TicksPerMillisecond);
        }
        Console.WriteLine();
    }

    static void Multi()
    {
        const int dim = 100;
        for(var passes = 0; passes < 10; passes++)
        {
            var timer = new Stopwatch();
            timer.Start();
            var multi = new int[dim,dim,dim];
            for(var i = 0; i < dim; i++)
            {
                for(var j = 0; j < dim; j++)
                {
                    for(var k = 0; k < dim; k++)
                    {
                        multi[i,j,k] = i * j * k;
                    }
                }
            }
            timer.Stop();
            Console.Write(Format,
                (double)timer.ElapsedTicks/TimeSpan.TicksPerMillisecond);
        }
        Console.WriteLine();
    }

    static void Single()
    {
        const int dim = 100;
        for(var passes = 0; passes < 10; passes++)
        {
            var timer = new Stopwatch();
            timer.Start();
            var single = new int[dim*dim*dim];
            for(var i = 0; i < dim; i++)
            {
                for(var j = 0; j < dim; j++)
                {
                    for(var k = 0; k < dim; k++)
                    {
                        single[i*dim*dim+j*dim+k] = i * j * k;
                    }
                }
            }
            timer.Stop();
            Console.Write(Format,
                (double)timer.ElapsedTicks/TimeSpan.TicksPerMillisecond);
        }
        Console.WriteLine();
    }
}

Autrement dit, les tableaux multidimensionnels sont similaires à une table dans un SGBD.
Array of Array (tableau dentelé) permet à chaque élément de contenir un autre tableau du même type de longueur variable.

Donc, si vous êtes sûr que la structure des données ressemble à une table (lignes / colonnes fixes), vous pouvez utiliser un tableau multidimensionnel. Les tableaux dentelés sont des éléments fixes et chaque élément peut contenir un tableau de longueur variable

Par exemple, le pseudo-code:

int[,] data = new int[2,2];
data[0,0] = 1;
data[0,1] = 2;
data[1,0] = 3;
data[1,1] = 4;

Considérez ce qui précède comme un tableau 2x2:

1 | 2
3 | 4

int[][] jagged = new int[3][]; 
jagged[0] = new int[4] {  1,  2,  3,  4 }; 
jagged[1] = new int[2] { 11, 12 }; 
jagged[2] = new int[3] { 21, 22, 23 }; 

Considérez ce qui précède comme chaque ligne ayant un nombre variable de colonnes:

 1 |  2 |  3 | 4
11 | 12
21 | 22 | 23

Préface: Ce commentaire est destiné à répondre à la réponse fournie par okutane , mais en raison du système de réputation stupide de SO, je ne peux pas l'afficher à sa place.

Votre affirmation selon laquelle l'une est plus lente que l'autre en raison des appels de méthode n'est pas correcte. L'un est plus lent que l'autre en raison d'algorithmes de vérification des limites plus compliqués. Vous pouvez facilement vérifier cela en regardant non pas l'IL, mais l'assembly compilé. Par exemple, sur mon installation 4.5, accéder à un élément (via un pointeur dans edx) stocké dans un tableau à deux dimensions pointé par ecx avec des index stockés dans eax et edx ressemble à ceci:

sub eax,[ecx+10]
cmp eax,[ecx+08]
jae oops //jump to throw out of bounds exception
sub edx,[ecx+14]
cmp edx,[ecx+0C]
jae oops //jump to throw out of bounds exception
imul eax,[ecx+0C]
add eax,edx
lea edx,[ecx+eax*4+18]

Ici, vous pouvez voir qu'il n'y a pas de surcharge des appels de méthode. La vérification des limites est juste très compliquée grâce à la possibilité d'index non-zéro, qui n'est pas une fonctionnalité proposée avec des tableaux irréguliers. Si nous supprimons les sous, cmp et jmps pour les cas non nuls, le code se résout à peu près à (x*y_max+y)*sizeof(ptr)+sizeof(array_header). Ce calcul est à peu près aussi rapide (une multiplication pourrait être remplacée par un décalage, car c'est la raison pour laquelle nous choisissons des octets à dimensionner en puissances de deux bits) comme toute autre chose pour l'accès aléatoire à un élément.

Une autre complication est qu'il existe de nombreux cas où un compilateur moderne optimisera la vérification des limites imbriquées pour l'accès aux éléments tout en itérant sur un tableau à une dimension. Le résultat est un code qui fait simplement avancer un pointeur d'index sur la mémoire contiguë du tableau. L'itération naïve sur des tableaux multidimensionnels implique généralement une couche supplémentaire de logique imbriquée, de sorte qu'un compilateur est moins susceptible d'optimiser le fonctionnement. Ainsi, même si la surcharge de vérification des limites de l'accès à un seul élément est amortie à un temps d'exécution constant en ce qui concerne les dimensions et les tailles des tableaux, un cas de test simple pour mesurer la différence peut prendre plusieurs fois plus de temps à s'exécuter.

Je voudrais mettre à jour cela, car dans .NET Core, les tableaux multidimensionnels sont plus rapides que les tableaux irréguliers . J'ai exécuté les tests de John Leidegren et voici les résultats sur la prévisualisation 2. de NET Core 2.0. J'ai augmenté la valeur de la dimension pour rendre les influences possibles des applications d'arrière-plan moins visibles.

Debug (code optimalization disabled)
Running jagged 
187.232 200.585 219.927 227.765 225.334 222.745 224.036 222.396 219.912 222.737 

Running multi-dimensional  
130.732 151.398 131.763 129.740 129.572 159.948 145.464 131.930 133.117 129.342 

Running single-dimensional  
 91.153 145.657 111.974  96.436 100.015  97.640  94.581 139.658 108.326  92.931 


Release (code optimalization enabled)
Running jagged 
108.503 95.409 128.187 121.877 119.295 118.201 102.321 116.393 125.499 116.459 

Running multi-dimensional 
 62.292  60.627  60.611  60.883  61.167  60.923  62.083  60.932  61.444  62.974 

Running single-dimensional 
 34.974  33.901  34.088  34.659  34.064  34.735  34.919  34.694  35.006  34.796 

J'ai regardé dans les démontages et c'est ce que j'ai trouvé

jagged[i][j][k] = i * j * k; 34 instructions nécessaires pour exécuter

multi[i, j, k] = i * j * k; 11 instructions nécessaires pour exécuter

single[i * dim * dim + j * dim + k] = i * j * k; besoin de 23 instructions pour exécuter

Je n'ai pas pu identifier pourquoi les tableaux unidimensionnels étaient encore plus rapides que multidimensionnels, mais je suppose que cela a à voir avec une optimisation effectuée sur le processeur

Les tableaux multidimensionnels sont des matrices à (n-1) dimensions.

Il en int[,] square = new int[2,2]est de même de la matrice carrée 2x2, int[,,] cube = new int [3,3,3]est une matrice cubique carrée 3x3. La proportionnalité n'est pas requise.

Les tableaux dentelés ne sont que des tableaux de tableaux - un tableau où chaque cellule contient un tableau.

Les MDA sont donc proportionnels, JD ne l'est peut-être pas! Chaque cellule peut contenir un tableau de longueur arbitraire!

Cela peut avoir été mentionné dans les réponses ci-dessus, mais pas explicitement: avec un tableau dentelé, vous pouvez utiliser array[row]pour référencer toute une ligne de données, mais cela n'est pas autorisé pour les tableaux multi-d.

En plus des autres réponses, notez qu'un tableau multidimensionnel est alloué comme un gros objet volumineux sur le tas. Cela a quelques implications:

1. Certains tableaux multidimensionnels seront alloués sur le tas d'objets volumineux (LOH) où leurs homologues de tableaux dentelés équivalents n'auraient pas autrement.
2. Le GC devra trouver un seul bloc de mémoire libre contigu pour allouer un tableau multidimensionnel, tandis qu'un tableau dentelé pourrait être en mesure de combler les lacunes causées par la fragmentation de tas ... ce n'est généralement pas un problème dans .NET en raison du compactage , mais le LOH n'est pas compacté par défaut (vous devez le demander, et vous devez le demander chaque fois que vous le souhaitez).
3. Vous voudrez rechercher <gcAllowVeryLargeObjects>des tableaux multidimensionnels bien avant que le problème ne se pose si vous n'utilisez que des tableaux irréguliers.

J'analyse des fichiers .il générés par ildasm pour créer une base de données d'assassinats, de classes, de méthodes et de procédures stockées à utiliser pour effectuer une conversion. Je suis tombé sur ce qui suit, ce qui a brisé mon analyse.

.method private hidebysig instance uint32[0...,0...] 
        GenerateWorkingKey(uint8[] key,
                           bool forEncryption) cil managed

Le livre Expert .NET 2.0 IL Assembler, de Serge Lidin, Apress, publié en 2006, chapitre 8, Types et signatures primitifs, pp. 149-150 explique.

<type>[]est appelé un vecteur de <type>,

<type>[<bounds> [<bounds>**] ] est appelé un tableau de <type>

**les moyens peuvent être répétés, les [ ]moyens sont facultatifs.

Exemples: Let <type> = int32.

1) int32[...,...]est un tableau bidimensionnel de bornes inférieures et de tailles non définies

2) int32[2...5]est un tableau unidimensionnel de borne inférieure 2 et de taille 4.

3) int32[0...,0...]est un tableau bidimensionnel de bornes inférieures 0 et de taille non définie.

À M