В чем различия между многомерным массивом и массивом массивов в C #?
https://stackoverflow.com/questions/597720
-
11-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
В чем различия между многомерными массивами double[,] и массив из массивов double[][] в C #?
Если есть разница, то как лучше всего использовать каждый из них?
Решение
Массив массивов (зубчатые массивы) работают быстрее, чем многомерные массивы, и их можно использовать более эффективно.Многомерные массивы имеют более приятный синтаксис.
Если вы напишете простой код с использованием зубчатых и многомерных массивов, а затем проверите скомпилированную сборку с помощью дизассемблера 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
Первая строка - это тайминги неровных массивов, вторая показывает многомерные массивы, а третья - ну, так и должно быть.Программа показана ниже, К вашему сведению, она была протестирована под управлением 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();
}
}
Проще говоря, многомерные массивы аналогичны таблице в СУБД.
Массив из массива (зубчатый массив) позволяет каждому элементу содержать другой массив того же типа переменной длины.
Итак, если вы уверены, что структура данных имеет вид таблицы (фиксированные строки/столбцы), вы можете использовать многомерный массив.Зубчатый массив представляет собой фиксированные элементы, и каждый элемент может содержать массив переменной длины.
Например.Псевдокод:
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
Предисловие: Этот комментарий предназначен для решения ответ дал Окутане, но из-за глупой системы репутации 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).Этот расчет происходит примерно так же быстро (одно умножение можно заменить сдвигом, поскольку именно поэтому мы выбираем размер байтов как степени двух битов), как и все остальные вычисления для произвольного доступа к элементу.
Другая сложность заключается в том, что во многих случаях современный компилятор оптимизирует вложенную проверку границ для доступа к элементам при переборе одномерного массива.В результате получается код, который по сути просто перемещает указатель индекса по непрерывной памяти массива.Наивная итерация по многомерным массивам обычно включает дополнительный уровень вложенной логики, поэтому компилятор с меньшей вероятностью оптимизирует операцию.Таким образом, даже несмотря на то, что накладные расходы на проверку границ доступа к одному элементу амортизируются до постоянного времени выполнения с учетом размеров и размеров массива, выполнение простого тестового примера для измерения разницы может занять во много раз больше времени.
Я хотел бы обновить эту информацию, потому что в Многомерные массивы .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 инструкции для выполнения
Мне не удалось определить, почему одномерные массивы по-прежнему работают быстрее, чем многомерные, но я предполагаю, что это связано с некоторой оптимизацией процессора.
Многомерные массивы представляют собой (n-1)-мерные матрицы.
Так int[,] square = new int[2,2] квадратная матрица 2х2, int[,,] cube = new int [3,3,3] представляет собой куб - квадратную матрицу 3х3.Пропорциональность не требуется.
Зубчатые массивы — это просто массив массивов — массив, в котором каждая ячейка содержит массив.
Таким образом, MDA пропорциональны, а JD — нет!Каждая ячейка может содержать массив произвольной длины!
Это могло быть упомянуто в приведенных выше ответах, но не явно:с неровным массивом, который вы можете использовать array[row] для ссылки на целую строку данных, но это не разрешено для многомерных массивов.
Я анализирую файлы .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 и неопределенным размером.
Том
В дополнение к другим ответам обратите внимание, что многомерный массив выделяется в куче как один большой массивный объект.Это имеет некоторые последствия:
- Некоторые многомерные массивы будут размещены в куче больших объектов (LOH), где в противном случае не было бы их эквивалентных аналогов зубчатых массивов.
- Сборщику мусора потребуется найти один непрерывный свободный блок памяти для выделения многомерного массива, тогда как неровный массив может заполнить пробелы, вызванные фрагментацией кучи...Обычно это не проблема в .NET из-за сжатия, но LOH не сжимается по умолчанию (вы должны запрашивать это, и вы должны спрашивать каждый раз, когда захотите).
- Вы захотите изучить
<gcAllowVeryLargeObjects>для многомерных массивов способ прежде чем проблема когда-либо возникнет, если вы когда-либо будете использовать только неровные массивы.
