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

Ответ 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;
}

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

Ответ 2

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

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

Взгляните на эту статью в Википедии, если вы хотите сделать сопоставление по размеру. Ваше сопоставление может быть по столбцу, например, как матрицы FORTRAN.

Ответ 3

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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

Ответ 6

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

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