Производительность двухмерного массива по сравнению с одномерным массивом

Question

В C есть разница во времени и пространстве между двумерным массивом m × n и 1-мерным массивом длины m × n (при больших значениях m и n)? Будет ли доступ к элементам быстрее с помощью одномерного массива?

Answer 1

В C двумерные массивы - это просто аккуратная схема индексирования для одномерных массивов. Так же, как с 1D-массивом, 2D-массивы выделяют один блок смежной памяти, а нотация A[row][col] похожа на A[row*NCOLS+col].

Обычно, если вы должны были реализовать свои собственные многомерные массивы с использованием одномерных массивов, вы бы написать функцию индексирования:

int getIndex(int row, int col) { return row*NCOLS+col; } 

Предполагая, что ваш компилятор встраивает эту функцию, производительность здесь будет точно таким же, как если вы использовали встроенную функцию индексирования 2D-массивов.

Для иллюстрации:

#define NROWS 10 
#define NCOLS 20 

Это:

int main(int argc, char *argv[]) { 
    int myArr[NROWS*NCOLS]; 
    for (int i=0; i<NROWS; ++i) { 
     for (int j=0; j<NCOLS; ++j) { 
      myArr[getIndex(i,j)] = i+j; 
     } 
    } 
    return 0; 
} 

Если выполнять так же, как это:

int main(int argc, char *argv[]) { 
    int myArr[NROWS][NCOLS]; 
    for (int i=0; i<NROWS; ++i) { 
     for (int j=0; j<NCOLS; ++j) { 
      myArr[i][j] = i+j; 
     } 
    } 
    return 0; 
} 

Хотя как AraKpointed out, если вы прыгали строк много , и строки очень большие, вы можете поразить множество ошибок страницы ... в этом случае cust Функция индексирования om (с переключением строк и столбцов) могла бы помочь, но так же может просто изменить, какие измерения в двумерном массиве вы рассматриваете как строки и которые вы рассматриваете как столбцы.

Answer 2

Я не думаю, что есть какая-то разница. Внутренне c обрабатывает двумерный массив, например, несколько одномерных массивов.

Однако, как и при всей производительности, ваш пробег может отличаться. Может быть какая-то тонкая арифметическая разница указателя. Запускайте тесты по времени в обоих сценариях. Какой бы ни побежал быстрее.

Answer 3

Я только догадываюсь, но я бы сказал, что 1-й массив быстрее, чем 2d-массив. Однако это было бы не намного быстрее. Вид как $ 1,000,000.01 составляет более $ 1,000,000.

Я бы использовал все, с чем проще кодировать.

Answer 4

На самом деле, если вы используете так называемый двумерный массив в C, компилятор выполнит преобразование в одномерный массив для вас. Если вы используете одномерный массив, и вам нравится относиться к нему как к двумерному, вы должны сами написать отображение.

Единственное, что вам нужно позаботиться, это получить доступ к массиву по-разному, потому что компилятор C сохранит вашу двумерную строку массива за строкой. Если вы получаете доступ к «большому» двумерному массиву по столбцу, тогда могут возникнуть ошибки страниц. Даже если вы программируете на языке, который поддерживает только одномерные массивы, вы можете легко записать отображение в любое количество измерений.

Посмотрите на эту статью в Википедии, если вы хотите сделать mapping row-wise. Ваше сопоставление может быть по столбцу, например, как матрицы FORTRAN.

Answer 5

Robert is correct.Выражения индексирования скомпилированы для арифметических выражений указателя, и поэтому нет никакой разницы.

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

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

Answer 6

Как сказано другим, разница в том, как вы получаете доступ к своим товарам: что имеет значение, если ваши элементы являются макетом в памяти, который является линейным, по крайней мере, на общих архитектурах. Итак, все, что у вас на самом деле - это 1d-массив, 2d и т. Д. - это просто «удобство», а разумный компилятор должен оптимизировать индексирование, но на практике, когда у вас есть несколько переменных, компиляторы часто терпят неудачу на arch как x86 из-за голода регистрации.

Теперь это зависит от вашего приложения, но я думаю, вы должны подумать с 1d макетом по умолчанию, особенно если вам нужно обрабатывать несколько измерений. Первая проблема с многомерными массивами в C состоит в том, что вы не можете их динамически распределять - если вы распределяете по каждой строке, у вас будут ужасные характеристики, потому что у вас нет смежной части памяти. Подробнее об этом см. В разделе FFTW doc.

Обратите внимание, что вы всегда можете описать свою единую память с удобной индексацией массива поверх нее (вы выделяете один большой блок памяти nxm, а затем создаете массив из n указателя на каждую строку).