Что лучше в отношении производительности? type [,] или type [] []?

Question

Насколько эффективнее иметь двумерный массив (type[,]) или массив массивов (type[][]) в C#?

В частности, для первоначального распределения и доступа пункта

Answer 1

Конечно, если все остальное терпит неудачу ... испытайте его! После дает (в «Release», в консоли):

Size 1000, Repeat 1000 
    int[,] set: 3460 
    int[,] get: 4036 (chk=1304808064) 
    int[][] set: 2441 
    int[][] get: 1283 (chk=1304808064) 

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

Обратите внимание, что этот тест предполагает, что вы получаете доступ к массиву гораздо чаще, чем его создаете, поэтому я не включил тайминги для создания, где я бы ожидал, что будет немного быстрее, если память сильно фрагментирована.

using System; 
using System.Diagnostics; 
static class Program 
{ 
    static void Main() 
    { 
     Console.WriteLine("First is just for JIT..."); 
     Test(10,10); 
     Console.WriteLine("Real numbers..."); 
     Test(1000,1000); 

     Console.ReadLine(); 
    } 

    static void Test(int size, int repeat) 
    { 
     Console.WriteLine("Size {0}, Repeat {1}", size, repeat); 
     int[,] rect = new int[size, size]; 
     int[][] jagged = new int[size][]; 
     for (int i = 0; i < size; i++) 
     { // don't cound this in the metrics... 
      jagged[i] = new int[size]; 
     } 
     Stopwatch watch = Stopwatch.StartNew(); 
     for (int cycle = 0; cycle < repeat; cycle++) 
     { 
      for (int i = 0; i < size; i++) 
      { 
       for (int j = 0; j < size; j++) 
       { 
        rect[i, j] = i * j; 
       } 
      } 
     } 
     watch.Stop(); 
     Console.WriteLine("\tint[,] set: " + watch.ElapsedMilliseconds); 

     int sum = 0; 
     watch = Stopwatch.StartNew(); 
     for (int cycle = 0; cycle < repeat; cycle++) 
     { 
      for (int i = 0; i < size; i++) 
      { 
       for (int j = 0; j < size; j++) 
       { 
        sum += rect[i, j]; 
       } 
      } 
     } 
     watch.Stop(); 
     Console.WriteLine("\tint[,] get: {0} (chk={1})", watch.ElapsedMilliseconds, sum); 

     watch = Stopwatch.StartNew(); 
     for (int cycle = 0; cycle < repeat; cycle++) 
     { 
      for (int i = 0; i < size; i++) 
      { 
       for (int j = 0; j < size; j++) 
       { 
        jagged[i][j] = i * j; 
       } 
      } 
     } 
     watch.Stop(); 
     Console.WriteLine("\tint[][] set: " + watch.ElapsedMilliseconds); 

     sum = 0; 
     watch = Stopwatch.StartNew(); 
     for (int cycle = 0; cycle < repeat; cycle++) 
     { 
      for (int i = 0; i < size; i++) 
      { 
       for (int j = 0; j < size; j++) 
       { 
        sum += jagged[i][j]; 
       } 
      } 
     } 
     watch.Stop(); 
     Console.WriteLine("\tint[][] get: {0} (chk={1})", watch.ElapsedMilliseconds, sum); 
    } 
} 

Answer 2

Я считаю, что [,] может выделить один непрерывный кусок памяти, в то время как [] [] является N + 1 порции распределения, где N является размером первого измерения. Поэтому я предполагаю, что [,] быстрее при первоначальном распределении.

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

Как уже упоминалось Марк Gravell, использование является ключевым для оценки эффективности ...

Answer 3

типа [,] будет работать быстрее. Не только из-за меньших расчетных расчетов. В основном из-за меньшей проверки ограничений, уменьшения объема памяти и большей локализации в памяти. type [] [] не является одним объектом - это 1 + N объектов, которые должны быть выделены и могут быть друг от друга.

Answer 4

На самом деле это зависит. В статье MSDN Magazine, Harness the Features of C# to Power Your Scientific Computing Projects, говорит, что это:

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