Каковы различия между многомерным массивом и массивом массивов в C#?

многомерный массив создает хороший линейный макет памяти, в то время как зубчатый массив подразумевает несколько дополнительных уровней косвенности.

поиск значения jagged[3][6] в многомерном массиве var jagged = new int[10][5] работает следующим образом: найдите элемент в индексе 3 (который является массивом) и найдите элемент в индексе 6 в этом массиве (который является значением). Для каждого измерения в этом случае есть дополнительный поиск (это дорогостоящий шаблон доступа к памяти).

многомерная массив выкладывается линейно в память, фактическое значение определяется путем умножения индексов. Однако, учитывая массив var mult = new int[10,30] на Length свойства этого многомерного массива возвращает общее количество элементов, т. е. 10 * 30 = 300.

The Rank свойство зубчатого массива всегда равно 1, но многомерный массив может иметь любой ранг. Элемент GetLength метод любого массива может быть использован для получения длины каждого измерения. Для многомерного массива в этом примере mult.GetLength(1) возвращает 30.

индексирование многомерного массива происходит быстрее. например, учитывая многомерный массив в этом примере mult[1,7] = 30 * 1 + 7 = 37, получить элемент по этому индексу 37. Это лучший шаблон доступа к памяти, потому что задействована только одна ячейка памяти, которая является базовым адресом массива.

многомерный массив поэтому выделяет непрерывный блок памяти, в то время как зубчатый массив не должен быть квадратным, например jagged[1].Length нет равняться jagged[2].Length, что было бы верно для любого многомерного массива.

производительность

производительность мудрый, многомерные массивы должны быть быстрее. Намного быстрее, но из-за очень плохой реализации CLR они не.

 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 

первая строка-это тайминги зубчатых массивов, вторая показывает многомерные массивы, а третья, ну вот как это должно быть. Программа показана ниже, FYI это было протестировано под управлением mono. (Тайминги windows сильно отличаются, в основном из-за вариаций реализации CLR).

в windows тайминги зубчатых массивов значительно превосходят, примерно так же, как и моя собственная интерпретация того, как должен выглядеть многомерный массив, см. " Single ()". К сожалению, JIT-компилятор windows действительно глуп, и это, к сожалению, затрудняет эти обсуждения производительности, слишком много несоответствий.

это тайминги, которые я получил на windows, то же самое дело здесь первая строка-это зубчатые массивы, вторая многомерная и третья моя собственная реализация многомерной, обратите внимание, насколько это медленнее в windows по сравнению с 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

исходный код:

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();
    }
}

проще говоря многомерные массивы похожи на таблицу в СУБД.
Массив массива (jagged array) позволяет каждому элементу содержать другой массив того же типа переменной длины.

Итак, если вы уверены, что структура данных выглядит как таблица (фиксированных строк/столбцов), вы можете использовать многомерный массив. Зубчатый массив-это фиксированные элементы , и каждый элемент может содержать массив переменной длины

например Psuedocode:

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

думать выше в виде таблицы 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 }; 

подумайте о том, что каждая строка имеет переменное количество столбцов:

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

предисловие: этот комментарий предназначен для решения ответ, предоставленный окутане, но из-за такой глупой системы репутации, я не могу разместить его там, где он принадлежит.

ваше утверждение, что один медленнее, чем другие, потому что метод не правильный. Один из них медленнее другого из-за более сложных алгоритмов проверки границ. Вы можете легко проверить это, посмотрев не на IL, а на скомпилированную сборку. Например, на моя установка 4.5, доступ к элементу (через указатель в edx), хранящемуся в двумерном массиве, на который указывает ecx с индексами, хранящимися в eax и edx, выглядит так:

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]

здесь вы можете видеть, что нет никаких накладных расходов от вызовов методов. Проверка границ просто очень запутана благодаря возможности ненулевых индексов, что является функциональностью, не предлагаемой с зубчатыми массивами. Если мы удалим sub, cmp и jmps для ненулевых случаев, код в значительной степени разрешает (x*y_max+y)*sizeof(ptr)+sizeof(array_header). Это вычисление примерно так же быстро (одно умножение может быть заменено сдвигом, так как именно по этой причине мы выбираем байты размером в два бита), как и все остальное для произвольного доступа к элементу.

еще одна сложность заключается в том, что есть много случаев, когда современный компилятор будет оптимизировать вложенные границы-проверка доступа к элементам при итерации по одномерному массиву. Результатом является код, который в основном просто продвигает указатель индекса над смежной памятью массива. Наивная итерация над многомерными массивами обычно включает дополнительный уровень вложенной логики, поэтому компилятор с меньшей вероятностью оптимизирует операцию. Таким образом, несмотря на то, что накладные расходы на проверку границ доступа к одному элементу амортизируются до постоянного времени выполнения относительно размеров и размеров массива, простой тестовый случай для измерения разницы может занять во много раз больше времени для выполнения.

Я хотел бы обновить это, потому что в.NET Core многомерные массивы быстрее, чем зубчатые массивы. Я провел тесты от Джон Leidegren и это результаты на .NET Core 2.0 preview 2. Я увеличил значение измерения, чтобы сделать любые возможные влияния от фоновых приложений менее заметными.

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 

Я заглянул в разборки и вот что я нашел

jagged[i][j][k] = i * j * k; необходимые 34 инструкции к выполнить

multi[i, j, k] = i * j * k; требуется 11 инструкций для выполнения

single[i * dim * dim + j * dim + k] = i * j * k; требуются 23 инструкции для выполнения

Я не смог определить, почему одномерные массивы были все еще быстрее, чем многомерные, но я предполагаю, что это связано с некоторой оптимизацией, сделанной на CPU

многомерные массивы являются (n-1)-размерными матрицами.

Так int[,] square = new int[2,2] квадратная матрица 2x2,int[,,] cube = new int [3,3,3] - квадратно-кубическая матрица 3x3. Пропорциональность не требуется.

зубчатые массивы-это просто массив массивов-массив, в котором каждая ячейка содержит массив.

таким образом, MDA пропорциональны, JD может быть нет! Каждая ячейка может содержать массив произвольной длины!

это могло быть упомянуто в приведенных выше ответах, но не явно: с jagged array вы можете использовать array[row] для ссылки на целую строку данных, но это не допускается для мульти-D массивов.

В дополнение к другим ответы, отметим, что многомерный массив выделяется как один большой коренастый объект в куче. Это имеет некоторые последствия:

1. некоторые многомерные массивы будут выделены в большой куче объектов (LOH), где их эквивалентные зазубренные аналоги массива в противном случае не имели бы.
2. GC нужно будет найти один непрерывный свободный блок памяти для выделения многомерного массива, в то время как неровный массив может быть в состоянии заполните пробелы, вызванные фрагментацией кучи... обычно это не проблема в .NET из-за уплотнения, но LOH не уплотняется по умолчанию (вы должны попросить об этом, и вы должны спрашивать каждый раз, когда вы этого хотите).
3. вы хотите, чтобы посмотреть в <gcAllowVeryLargeObjects> для многомерных массивов путь прежде чем проблема когда-либо возникнет, если вы будете использовать только зубчатые массивы.

я разбираю файлы. il, созданные ildasm для создания базы данных сборок, классов, методов и хранимых процедур для использования при преобразовании. Я наткнулся на следующее, что нарушило мой разбор.

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

книга эксперт .NET 2.0 IL ассемблер, Серж Лидин, Apress, опубликовано 2006, Глава 8, примитивные типы и подписи, С. 149-150 объясняет.

<type>[] называется вектор <type>,

<type>[<bounds> [<bounds>**] ] называется массив <type>

** значит можно повторить, [ ] значит необязательно.

Примеры: Пусть <type> = int32.

1) int32[...,...] представляет собой двумерный массив неопределенных нижних границ и размеров

2) int32[2...5] представляет собой одномерный массив нижней границы 2 и размера 4.

3) int32[0...,0...] представляет собой двумерный массив нижних границ 0 и неопределенного размера.

Тома