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

454

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?

ecleel
la source
7
Le premier double[,]est un tableau rectangulaire, alors qu'il double[][]est connu sous le nom de «tableau dentelé». La première aura le même nombre de "colonnes" pour chaque ligne, tandis que la seconde aura (potentiellement) un nombre différent de "colonnes" pour chaque ligne.
GreatAndPowerfulOz

Réponses:

334

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.

okutane
la source
7
@John, mesurez-les vous-même et ne faites pas d'hypothèses.
Hosam Aly
2
@John: Ma première réaction aussi mais j'avais tort - voir la question Hosams pour plus de détails.
Henk Holterman
38
Les tableaux multidimensionnels devraient logiquement être plus efficaces mais leur implémentation par le compilateur JIT ne l'est pas. Le code ci-dessus n'est pas utile car il n'affiche pas l'accès au tableau dans une boucle.
ILoveFortran
3
@Henk Holterman - Voir ma réponse ci-dessous, Il se peut que sur les fenêtres les tableaux dentelés soient rapides, mais il faut se rendre compte que cela est entièrement spécifique au CLR et pas le cas, par exemple, en mono ...
John Leidegren
12
Je sais que c'est une vieille question, je me demande simplement si le CLR a été optimisé pour les tableaux multidimensionnels depuis que cette question a été posée.
Anthony Nichols
197

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();
    }
}
John Leidegren
la source
2
Essayez de les chronométrer vous-même et voyez comment les deux fonctionnent. Les tableaux dentelés sont beaucoup plus optimisés dans .NET. Cela peut être lié à la vérification des limites, mais quelle qu'en soit la raison, les délais et les repères montrent clairement que les tableaux irréguliers sont plus rapides d'accès que les tableaux multidimensionnels.
Hosam Aly
10
Mais vos synchronisations semblent trop petites (quelques millisecondes). À ce niveau, vous aurez beaucoup d'interférences des services système et / ou des pilotes. Augmentez la taille de vos tests, en prenant au moins une seconde ou deux.
Hosam Aly
8
@JohnLeidegren: Le fait que les tableaux multidimensionnels fonctionnent mieux lors de l'indexation d'une dimension par rapport à une autre est compris depuis un demi-siècle, car les éléments qui ne diffèrent que dans une dimension particulière seront stockés consécutivement en mémoire et avec de nombreux types de mémoire (passé et présents), l'accès à des éléments consécutifs est plus rapide que l'accès à des éléments distants. Je pense qu'en .net, on devrait obtenir une indexation des résultats optimale par le dernier indice, ce que vous faisiez, mais tester le temps avec les indices échangés peut être informatif dans tous les cas.
supercat
16
@supercat: les tableaux multidimensionnels en C # sont stockés dans l'ordre des lignes principales , l'échange de l'ordre des indices serait plus lent car vous accéderiez à la mémoire de manière non consécutive. BTW les temps rapportés ne sont plus précis, j'obtiens presque deux fois plus vite pour les tableaux multidimensionnels que les tableaux dentelés (testés sur le dernier .NET CLR), ce qui devrait être ainsi.
Amro
9
Je sais que c'est un peu pédant, mais je dois mentionner que ce n'est pas Windows vs Mono, mais CLR vs Mono. Vous semblez parfois les confondre. Les deux ne sont pas équivalents; Mono fonctionne également sur Windows.
Magus
70

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
shahkalpesh
la source
4
c'est ce qui compte vraiment pour décider quoi utiliser .. pas ce truc de vitesse .. eh bien la vitesse peut devenir un facteur lorsque vous avez un tableau carré.
Xaser
46

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.

Eglin
la source
1
Merci d'avoir corrigé la réponse de l'okutane (pas Dmitry). Il est ennuyeux que les gens donnent de mauvaises réponses sur Stackoverflow et obtiennent 250 votes positifs tandis que d'autres donnent des réponses correctes et obtiennent beaucoup moins. Mais à la fin, le code IL n'est pas pertinent. Vous devez vraiment mesurer la vitesse pour dire quoi que ce soit sur les performances. As-tu fais ça? Je pense que la différence sera ridicule.
Elmue
38

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

adsamcik
la source
14

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!

abatishchev
la source
7

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.

lznt
la source
4

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.
Joe Amenta
la source
2

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

Thomas C Hutchinson
la source