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

un tableau multidimensionnel crée une belle mise en page de mémoire linéaire alors qu'un tableau irrégulier implique plusieurs niveaux supplémentaires d'indirection.

à la Recherche de la valeur jagged[3][6] dans un tableau en escalier var jagged = new int[10][5] fonctionne comme ceci: Regardez l'élément à l'indice 3 (qui est un tableau) et recherchez 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 mémoire coûteux).

un tableau multidimensionnel est présenté 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 propriété Length de ce tableau multidimensionnel renvoie le nombre total d'éléments soit 10 * 30 = 300.

la propriété Rank d'un tableau irrégulier est toujours 1, mais un tableau multidimensionnel peut avoir n'importe quel rang. La méthode GetLength 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) retourne 30.

indexation le 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 parce qu'une seule localisation mémoire est impliquée, qui est l'adresse de base du tableau.

un réseau multidimensionnel alloue donc un bloc de mémoire, alors qu'un tableau irrégulier ne doit pas être carré, par exemple jagged[1].Length ne doit pas être égal à jagged[2].Length , ce qui serait vrai pour tout tableau multidimensionnel.

Performance

Performance sage, les tableaux multidimensionnels devrait être plus rapide. Beaucoup plus rapide, mais en raison d'une mise en œuvre vraiment mauvaise CLR ils ne 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 rangée sont des timings de tableaux déchiquetés, la seconde montre multidimensionnel les tableaux et le troisième, c'est comme ça que ça devrait être. Le programme est montré ci-dessous, FYI cela a été testé en cours d'exécution mono. (Les horaires de windows sont très différents, principalement en raison des variations dans L'implémentation CLR).

Sur windows, le timing de l'enchevêtrement des tableaux sont largement supérieurs, environ le même que ma propre interprétation de ce tableau multidimensionnel regarder, voir Unique()'. Malheureusement, le compilateur windows JIT-est vraiment stupide, et cela rend malheureusement ces les discussions sur le rendement sont difficiles, il y a trop d'incohérences.

ce sont les horaires que j'ai eu sur windows, même affaire ici, la première rangée sont des tableaux déchiquetés, deuxième multidimensionnel et troisième ma propre mise en œuvre de multidimensionnel, notez combien de temps cela est plus lent sur 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();
    }
}

simplement mis les tableaux multidimensionnels sont similaires à un tableau dans le SGBD.

Tableau de Tableau (tableau en escalier) vous permet d'avoir chaque élément de tenir un autre tableau du même type de longueur variable.

ainsi, 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

E. G. Psuedocode:

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

Penser la-dessus 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 chaque ligne ayant un nombre variable de colonnes:

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

Préface: Ce commentaire est destiné à l'adresse la réponse fournie par okutane , mais à cause de la stupide système de réputation, je ne peux pas poster là où il appartient.

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

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 frais généraux des appels de méthode. La vérification des limites est très complexe grâce à la possibilité d'index non-zéros, qui est une fonctionnalité qui n'est pas offerte avec des tableaux dentelés. Si nous supprimons le sub, cmp,et jmps pour le non-zero cases, 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, puisque c'est la raison pour laquelle nous choisissons les octets à dimensionner comme des puissances de deux bits) que n'importe quoi d'autre pour l'accès aléatoire à un élément.

une autre complication est qu'il existe de nombreux cas où un compilateur moderne optimisera l'élimination des limites imbriquées-vérifiant l'accès aux éléments tout en itérant sur un tableau de dimension unique. Le résultat est du 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 l'opération. Ainsi, même si la vérification des limites de l'accès à un seul élément amortit à un temps d'exécution constant en ce qui concerne les dimensions et les tailles des réseaux, un simple test-case pour mesurer la différence peut prendre plusieurs fois plus de temps à exécuter.

je voudrais mettre à jour sur ce, parce que dans . les tableaux multi-dimensionnels du noyau Net sont plus rapides que les tableaux découpés . J'ai effectué les tests de John Leidegren et voici les résultats sur .net Core 2.0 preview 2. J'ai augmenté la valeur de dimension pour rendre toutes 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; nécessaire 34 instructions à exécuter

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

single[i * dim * dim + j * dim + k] = i * j * k; besoin d'23 instructions à exécuter

Je n'ai pas été en mesure d'identifier pourquoi les tableaux unidimensionnels étaient encore plus rapides que les tableaux multidimensionnels, mais je pense que cela a à voir avec une certaine optimisation faite sur le CPU

Multi-dimension des tableaux sont (n-1)-dimension des matrices.

Donc int[,] square = new int[2,2] est le carré de la matrice 2x2, int[,,] cube = new int [3,3,3] est un cube - matrice carrée de 3x3. La proportionnalité n'est pas nécessaire.

les tableaux Irréguliers sont juste tableau de tableaux (un tableau où chaque cellule contient un tableau.

donc MDA sont proportionnels, JD peut ne pas être! Chaque cellule contient un tableau de longueur arbitraire!

cela pourrait avoir été mentionné dans les réponses ci-dessus, mais pas explicitement: avec un tableau en jagged vous pouvez utiliser array[row] pour renvoyer une rangée entière de données, mais ce n'est pas autorisé pour les tableaux multi-D.

En plus des autres réponses, notez qu'un tableau multidimensionnel est réparti comme un grand chunky objet sur le tas. Cela a certaines implications:

1. certains tableaux multidimensionnels seront alloués sur le tas D'objets de Grande Taille (LOH) où leurs homologues Jagged tableau équivalents n'auraient pas autrement.
2. le GC aura besoin de trouver un seul bloc de mémoire libre contigu pour allouer un tableau multidimensionnel, alors qu'un le tableau déchiqueté pourrait être capable de combler les lacunes causées par la fragmentation de tas... ce n'est généralement pas un problème dans .NET à cause 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 voulez).
3. vous voudrez regarder dans <gcAllowVeryLargeObjects> pour les tableaux multidimensionnels chemin avant que la question ne se posera jamais si vous utilisez seulement des tableaux dentelés.

je parle .il les dossiers produits par ildasm pour construire une base de données des assemnblies, les classes, les méthodes, et les procédures stockées pour l'utilisation faisant une conversion. Je suis tombé sur ce qui suit, qui a cassé mon parsing.

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

the book Expert.net 2.0 IL Assembler, by Serge Lidin, Apress, published 2006, Chapter 8, Primitive Types and Signatures, pp. 149-150 explains.

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

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

** signifie Peut être répété, [ ] signifie facultatif.

Exemples: Let <type> = int32 .

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

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

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

Tom