Каковы различия между многомерным массивом и массивом массивов в C#?
Каковы различия между многомерными массивами double[,] и массив массивов double[][] в C#?
Если есть разница, что лучше для каждого?
12 ответов
Массивы массивов (зубчатые массивы) работают быстрее многомерных массивов и могут использоваться более эффективно. Многомерные массивы имеют более приятный синтаксис.
Если вы напишите некоторый простой код с использованием зубчатых и многомерных массивов, а затем осмотрите скомпилированную сборку с помощью дизассемблера IL, вы увидите, что хранение и извлечение из зубчатых (или одномерных) массивов являются простыми инструкциями IL, тогда как те же операции для многомерных массивов являются методом вызовы, которые всегда медленнее.
Рассмотрим следующие методы:
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;
}
Их IL будет следующим:
.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
При использовании зубчатых массивов вы можете легко выполнять такие операции, как перестановка строк и изменение размера строк. Может быть, в некоторых случаях использование многомерных массивов будет более безопасным, но даже Microsoft FxCop говорит, что при использовании его для анализа своих проектов следует использовать зубчатые массивы вместо многомерных.
Многомерный массив создает красивую линейную структуру памяти, в то время как зубчатый массив подразумевает несколько дополнительных уровней косвенности.
Поиск значения jagged[3][6] в зазубренном массиве var jagged = new int[10][5] работает следующим образом: найдите элемент с индексом 3 (который является массивом) и найдите элемент с индексом 6 в этом массиве (который является значением). Для каждого измерения в этом случае есть дополнительный поиск (это дорогой шаблон доступа к памяти).
Многомерный массив линейно размещается в памяти, фактическое значение определяется путем умножения индексов. Однако, учитывая массив var mult = new int[10,30], Length свойство этого многомерного массива возвращает общее количество элементов, т.е. 10 * 30 = 300.
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
В первом ряду приведены временные интервалы массивов, во втором - многомерные массивы, а в третьем - так и должно быть. Программа показана ниже, к вашему сведению, это было проверено в режиме моно. (Синхронизация окон сильно отличается, в основном из-за изменений в реализации CLR).
В окнах временные характеристики зубчатых массивов значительно выше, примерно так же, как моя собственная интерпретация того, на что должен быть похож внешний вид многомерного массива, см. Single(). К сожалению, JIT-компилятор Windows действительно глуп, и это, к сожалению, затрудняет обсуждение производительности, слишком много несоответствий.
Это время, которое я получил на окнах, то же самое здесь, первая строка - зубчатые массивы, вторая - многомерная и третья - моя собственная реализация многомерной, обратите внимание, насколько медленнее это для окон по сравнению с моно.
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();
}
}
Проще говоря, многомерные массивы похожи на таблицы в СУБД.
Array of Array (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;
Думайте об этом как о таблице 2х2:
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
Я хотел бы обновить это, потому что в .NET Core многомерные массивы работают быстрее, чем зубчатые массивы. Я выполнил тесты Джона Лейдгрена, и это результаты предварительного просмотра.NET Core 2.0 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 инструкции для выполнения
Я не смог определить, почему одномерные массивы были все же быстрее многомерных, но я предполагаю, что это связано с некоторой оптимизацией, сделанной на процессоре
Предисловие: Этот комментарий предназначен для ответа на вопрос, предоставленный okutane, но из-за глупой системы репутации SO, я не могу опубликовать его там, где он принадлежит.
Ваше утверждение, что один медленнее другого из-за вызовов метода, неверно. Один медленнее другого из-за более сложных алгоритмов проверки границ. В этом легко убедиться, посмотрев не на 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), Это вычисление примерно такое же быстрое (одно умножение может быть заменено сдвигом, так как это единственная причина, по которой мы выбираем размер байтов в виде степеней двух бит), как и все остальное для произвольного доступа к элементу.
Другая сложность заключается в том, что существует множество случаев, когда современный компилятор оптимизирует удаленную проверку границ для доступа к элементам при выполнении итерации по одномерному массиву. В результате получается код, который в основном просто перемещает указатель индекса по непрерывной памяти массива. Наивная итерация по многомерным массивам обычно включает дополнительный уровень вложенной логики, поэтому компилятор с меньшей вероятностью оптимизирует работу. Таким образом, даже несмотря на то, что накладные расходы на проверку границ при доступе к одному элементу амортизируются до постоянного времени выполнения в отношении размеров и размеров массива, простой тестовый пример для измерения разницы может выполняться во много раз дольше для выполнения.
Многомерные массивы являются (n-1)-мерными матрицами.
Так int[,] square = new int[2,2] квадратная матрица 2х2, int[,,] cube = new int [3,3,3] кубическая квадратная матрица 3x3 Пропорциональность не требуется.
Зубчатые массивы - это просто массив массивов - массив, в котором каждая ячейка содержит массив.
Так что MDA пропорциональны, JD может и не быть! Каждая ячейка может содержать массив произвольной длины!
Это могло быть упомянуто в ответах выше, но не явно: с помощью зубчатого массива вы можете использовать array[row] ссылаться на целый ряд данных, но это не разрешено для многомерных массивов.
В дополнение к другим ответам обратите внимание, что многомерный массив выделяется как один большой коренастый объект в куче. Это имеет некоторые последствия:
- Некоторые многомерные массивы будут размещаться в куче больших объектов (LOH), где в противном случае их эквивалентные зубчатые массивы не имели бы.
- GC должен будет найти один непрерывный свободный блок памяти для выделения многомерного массива, тогда как зубчатый массив может заполнить пробелы, вызванные фрагментацией кучи... это обычно не проблема в.NET из-за сжатия, но LOH не уплотняется по умолчанию (вы должны просить об этом, и вы должны спрашивать каждый раз, когда захотите).
- Вы хотите посмотреть в
<gcAllowVeryLargeObjects>для многомерных массивов задолго до того, как проблема возникнет, если вы будете использовать только зубчатые массивы.
Я подумал, что из будущего я присоединюсь к этому с некоторыми результатами производительности .NET 5, поскольку это будет платформа, которую все используют с этого момента.
Это те же тесты, которые использовал Джон Лейдегрен (в 2009 году).
Мои результаты (.NET 5.0.1):
Debug:
(Jagged)
5.616 4.719 4.778 5.524 4.559 4.508 5.913 6.107 5.839 5.270
(Multi)
6.336 7.477 6.124 5.817 6.516 7.098 5.272 6.091 25.034 6.023
(Single)
4.688 3.494 4.425 6.176 4.472 4.347 4.976 4.754 3.591 4.403
Release(code optimizations on):
(Jagged)
2.614 2.108 3.541 3.065 2.172 2.936 1.681 1.724 2.622 1.708
(Multi)
3.371 4.690 4.502 4.153 3.651 3.637 3.580 3.854 3.841 3.802
(Single)
1.934 2.102 2.246 2.061 1.941 1.900 2.172 2.103 1.911 1.911
Работает на 6-ядерной машине AMD Ryzen 1600 с тактовой частотой 3,7 ГГц.
Похоже, что соотношение производительности примерно такое же. Я бы сказал, если вы действительно сильно не оптимизируете, просто используйте многомерные массивы, поскольку синтаксис немного проще в использовании.
Неровные массивы - это массивы массивов или массивов, в которых каждая строка содержит собственный массив.
Эти массивы могут иметь длину, отличную от длины в других строках.
Объявление и размещение массива массивов
Единственная разница в объявлении зубчатых массивов по сравнению с обычным многомерным массивом состоит в том, что у нас нет только одной пары скобок. С зубчатыми массивами у нас есть пара скобок для каждого измерения. Распределяем их так:
Выделение памяти
Неровные массивы - это совокупность ссылок. Зубчатый массив напрямую не содержит массивов, а скорее имеет элементы, указывающие на них. Размер неизвестен, поэтому CLR просто хранит ссылки на внутренние массивы. После того, как мы выделяем память для одного элемента массива зубчатого массива, ссылка начинает указывать на вновь созданный блок в динамической памяти.
Переменная exampleJaggedArray хранится в стеке выполнения программы и указывает на блок в динамической памяти, который содержит последовательность из трех ссылок на другие три блока в памяти; каждый из них содержит массив целых чисел - элементы зубчатого массива:
Я разбираю файлы.il, сгенерированные ildasm, для создания базы данных сборок, классов, методов и хранимых процедур для использования при преобразовании. Я наткнулся на следующее, что сломало мой разбор.
.method private hidebysig instance uint32[0...,0...]
GenerateWorkingKey(uint8[] key,
bool forEncryption) cil managed
Объясняет книгу Эксперт.NET 2.0 IL Assembler Сержа Лидина, 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 и неопределенным размером.
Том
Используя тест, основанный на тесте , я Джона Лейдегренапроверил результат, используя .NET 4.7.2, версию, подходящую для моих целей, и подумал, что могу поделиться. Первоначально я начал с этого комментария в репозитории GitHub ядра dotnet.
Похоже, что производительность сильно меняется при изменении размера массива, по крайней мере, в моей настройке: 1 процессор xeon с 4physical 8logical.
w = инициализировать массив и поместить в него int i * j. wr = do w, затем в другом цикле установите int x равным [i,j]
По мере увеличения размера массива многомерное становится лучше.