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

Question

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

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

Answer 1

Les tableaux de tableaux (tableaux en dents de scie) 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 un code simple utilisant des tableaux en dents de scie et multidimensionnels et que vous inspectez ensuite l'assemblage compilé à l'aide d'un désassembleur IL, vous verrez que le stockage et la récupération dans des tableaux en dents de scie (ou unidimensionnels) sont des instructions IL simples, tandis que les mêmes opérations pour les tableaux multidimensionnels sont des invocations de méthodes, qui sont 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 VA sera la suivante :

.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 en dents de scie, vous pouvez facilement effectuer des opérations telles que l'échange de lignes et le redimensionnement de lignes. Peut-être que dans certains cas, l'utilisation de tableaux multidimensionnels sera plus sûre, mais même Microsoft FxCop indique que les tableaux jagged doivent être utilisés à la place des tableaux multidimensionnels lorsque vous l'utilisez pour analyser vos projets.

Answer 2

Un tableau multidimensionnel crée une belle disposition linéaire de la mémoire, tandis qu'un tableau en dents de scie implique plusieurs niveaux supplémentaires d'indirection.

Recherche de la valeur jagged[3][6] dans un ensemble déchiqueté var jagged = new int[10][5] fonctionne comme ça : Rechercher l'élément à l'indice 3 (qui est un tableau) et rechercher l'élément à l'indice 6 dans ce tableau (qui est une valeur). Pour chaque dimension dans ce cas, il y a une recherche supplémentaire (c'est 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 les index. Cependant, étant donné que le tableau var mult = new int[10,30] El Length de ce tableau multidimensionnel renvoie le nombre total d'éléments, c'est-à-dire 10 * 30 = 300.

El Rank d'un tableau en dents de scie est toujours 1, mais un tableau multidimensionnel peut avoir n'importe quel rang. Le site GetLength de tout tableau peut être utilisée pour obtenir la longueur de chaque dimension. Pour le tableau multidimensionnel de cet exemple mult.GetLength(1) retourne 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, on obtient l'élément à cet indice 37. Il s'agit d'un meilleur modèle d'accès à la mémoire car une seule position mémoire est impliquée, à savoir l'adresse de base du tableau.

Un tableau multidimensionnel alloue donc un bloc de mémoire continu, alors qu'un tableau en dents de scie n'a pas besoin d'être carré, par ex. jagged[1].Length ne doit pas nécessairement être égal à jagged[2].Length ce qui serait vrai pour tout tableau multidimensionnel.

Performance

En termes de performances, les tableaux multidimensionnels devraient être plus rapides. Beaucoup plus rapides, mais à cause d'une très mauvaise implémentation du CLR, 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 constituée de tableaux en dents de scie, la deuxième montre des tableaux multidimensionnels et la troisième, c'est comme ça que ça devrait être. Le programme est présenté ci-dessous, pour information, il a été testé sous mono (les temps sous Windows sont très différents, principalement en raison des variations de l'implémentation du CLR).

Sous Windows, les délais des tableaux en dents de scie sont nettement supérieurs, à peu près comme ma propre interprétation de ce que devrait être la consultation d'un 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.

Voici les temps que j'ai obtenus sous Windows, même chose ici, la première ligne sont des tableaux jagged, la deuxième multidimensionnelle et la troisième ma propre implémentation de multidimensionnelle, notez combien c'est plus lent sous Windows par rapport à 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();
    }
}

Answer 3

En termes simples, les tableaux multidimensionnels sont similaires à une table dans un SGBD.
Array of Array (tableau en dents de scie) permet à chaque élément de contenir un autre tableau du même type et de longueur variable.

Ainsi, si vous êtes sûr que la structure des données ressemble à un tableau (rangées/colonnes fixes), vous pouvez utiliser un tableau multidimensionnel. Les tableaux en dents de scie comportent des éléments fixes et chaque élément peut contenir un tableau de longueur variable.

Par exemple, le Psuedocode :

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

Pensez à 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 }; 

Pensez à ce qui précède comme si chaque ligne avait un nombre variable de colonnes :

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

Answer 4

Préface : Ce commentaire a pour but d'aborder la réponse fournie par okutane mais à cause du système de réputation stupide de SO, je ne peux pas le poster là où il devrait être.

Votre affirmation selon laquelle l'un est plus lent que l'autre en raison des appels de méthode n'est pas correcte. L'un est plus lent que l'autre à cause d'algorithmes de contrôle des limites plus compliqués. Vous pouvez facilement le vérifier en regardant, non pas l'IL, mais l'assemblage compilé. Par exemple, sur mon installation 4.5, l'accès à un élément (via le pointeur dans edx) stocké dans un tableau bidimensionnel 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 due aux appels de méthode. La vérification des limites est juste très alambiquée grâce à la possibilité d'index non nuls, ce qui est une fonctionnalité qui n'est pas offerte avec les tableaux en dents de scie. Si nous supprimons les sub, cmp et jmp pour les cas non nuls, le code se résume à 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, puisque c'est la raison pour laquelle nous avons choisi de dimensionner les octets comme des puissances de deux bits) que n'importe quelle autre méthode d'accès aléatoire à un élément.

Une autre complication est qu'il existe de nombreux cas où un compilateur moderne optimisera le contrôle 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 ne fait qu'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 l'opération. Ainsi, même si le surcoût lié au contrôle des limites de l'accès à un seul élément s'amortit en un temps d'exécution constant par rapport aux dimensions et aux tailles des tableaux, un simple cas de test pour mesurer la différence peut prendre plusieurs fois plus de temps à exécuter.

Answer 5

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

Así que int[,] square = new int[2,2] est une matrice carrée 2x2, int[,,] cube = new int [3,3,3] est un cube - matrice carrée 3x3. La proportionnalité n'est pas requise.

Les tableaux en dents de scie ne sont que des tableaux de tableaux - un tableau où chaque cellule contient un tableau.

Donc les MDA sont proportionnels, les JD peuvent ne pas l'être ! Chaque cellule peut contenir un tableau de longueur arbitraire !