В чем разница между многомерным массивом и массивом массивов в C #?

В чем разница между многомерными массивами double[,] и array-of-arrays 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; } 

Их ИЛ будет выглядеть следующим образом:

 .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, но multidimensional array может иметь любой ранг. Метод GetLength любого массива может использоваться для получения длины каждого измерения. Для многомерного массива в этом примере mult.GetLength(1) возвращает 30.

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

Поэтому multidimensional array выделяет блок непрерывной памяти, в то время как зубчатый массив не должен быть квадратным, например 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. (Тайм-ауты окон сильно различаются, в основном из-за вариаций реализации CLR).

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

Это тайминги, которые я получил в 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(); } } с 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(); } } 

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

Итак, если вы уверены, что структура данных выглядит как таблица (фиксированные строки / столбцы), вы можете использовать multidimensional 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 

Предисловие. Этот комментарий предназначен для ответа на вопрос, предоставленный 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) . Этот расчет примерно такой же быстрый (одно умножение может быть заменено сдвигом, так как именно по этой причине мы выбираем байты размером до двух бит), как что-либо еще для случайного доступа к элементу.

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

Я хотел бы обновить это, потому что в .NET Core многомерные массивы быстрее, чем зубчатые массивы . Я провел тесты у Джона Лейдегрена, и это результаты в .NET Framework 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 

Я искал parsingки, и вот что я нашел

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] – квадратная matrix 2×2, int[,,] cube = new int [3,3,3] – квадратная matrix 3×3. Пропорциональность не требуется.

Жесткие массивы – это всего лишь массив массивов – массив, в котором каждая ячейка содержит массив.

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

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

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

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

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

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

Книга Expert .NET 2.0 IL Assembler, автор: Serge Lidin, Apress, опубликованная в 2006 году, глава 8, «Примитивные типы и подписи», стр. 149-150.

[] называется Vector ,

[ [**] ] называется массивом

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

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

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

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

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

Том

Interesting Posts

Spring Контроллеры на основе аннотаций не работают, если они находятся внутри файла jar

Как мне получить / отредактировать изображения аватара пользователя Chrome?

Как выполнить декодирование URL в Java?

Как я могу удерживать кнопку нажатой после нажатия на нее?

Triple vs. Dual Channel с 6 палочками памяти

Как разрешить «у нас возникают проблемы с определением вашего ПК Windows Consumer Preview»?

Передача массива по ссылке

Каков наилучший способ создания разреженного массива в C ++?

Предоставляет ли RE REPL?

Как проверить количество TXT-файлов в папке (команда dir)?

Возможно ли совместить вложенные скобки с регулярным выражением без использования рекурсивных или балансировочных групп?

PostgreSQL: разница между текстом и varchar (характер меняется)

Вызывает статические методы через объект «плохая форма»? Зачем?

Переключение материнской платы без новой установки?

Должен ли я всегда отключать обработчики событий в методе Dispose?

Давайте будем гением компьютера.