Производительность 2-мерного массива по сравнению с 1-мерным массивом
- Система. IO для операций файла
- Система. Наборы & Система. Наборы. Универсальный - изучают, как управлять / Списки использования, Словарь, и т.д.
6 ответов
В C двумерные массивы - это просто изящная схема индексации для одномерных массивов. Как и в случае с одномерным массивом, двухмерные массивы выделяют один блок непрерывной памяти, а запись 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 указал , если вы много прыгаете по строкам, а строки очень большие, вы можете столкнуться с множеством ошибок страниц ...
На самом деле, если вы используете так называемый двумерный массив в C, компилятор выполнит преобразование в одномерный массив за вас. Если вы используете одномерный массив и хотите рассматривать его как двумерный, тогда вам придется написать отображение самостоятельно.
Единственное, о чем вам нужно позаботиться, это получить доступ к строке массива - мудро, потому что компилятор C будет хранить ваш двухмерный массив строка за строкой. Если вы обращаетесь к «большому» двумерному массиву по столбцам, то вероятны ошибки страниц. Даже если вы программируете на языке, который поддерживает только одномерные массивы, вы можете легко записать отображение в любое количество измерений.
Взгляните на эту статью в Википедии, если вы хотите выполнить сопоставление по строкам . Ваше отображение может быть по столбцам,
Я не думаю, что есть разница. Внутренне c обрабатывает двумерный массив как несколько последовательных одномерных массивов.
Однако, как и во всех случаях с производительностью, ваш пробег может отличаться. Может быть какая-то тонкая арифметическая разница в указателях. Запустите тесты по времени в обоих сценариях. Побеждает тот, кто бежит быстрее.
Роберт прав. Выражения индексации скомпилированы в арифметические выражения указателей, поэтому разницы нет.
Что может иметь влияние, так это порядок доступа, и поэтому вы можете захотеть реализовать что-то самостоятельно, чтобы вы могли контролировать порядок доступа. Например, формы сначала столбец и первая строка.
На современных процессорах доступ к большим массивам на разных этапах может иметь неожиданные различия в производительности. Последовательный доступ всегда самый быстрый, а другие шаги могут быть до 30 раз медленнее из-за взаимодействия с кешем. Многомерные массивы, в которых внутренние размеры являются степенью двойки, часто имеют низкую производительность из-за того, как они взаимодействуют с ассоциативностью кеша. Чтобы разобраться в этих проблемах, нет реальной замены проведению измерений.
Я только догадываюсь, но я бы сказал, что 1d-массив быстрее, чем 2d-массив. Однако это не было бы заметно быстрее. Что-то вроде 1 000 000,01 доллара - это больше, чем 1 000 000 долларов.
Я бы использовал то, что проще кодировать.
Как сказал другой, разница действительно в том, как вы получаете доступ к своим предметам: что имеет значение, если как ваши предметы макет в памяти, линейный, по крайней мере, на распространенных архитектурах. Таким образом, все, что у вас есть на самом деле, это 1d-массив, 2d и т. Д. - это «просто» удобство, и разумный компилятор должен оптимизировать индексацию - но на практике, когда у вас больше, чем несколько переменных, компиляторы часто терпят неудачу на Arch как x86 из-за нехватки регистров.
Теперь это зависит от вашего приложения, но я думаю, вам стоит подумать о 1d-макете по умолчанию, особенно если вам нужно обрабатывать несколько измерений. Первая проблема с многомерными массивами в C заключается в том, что вы не можете динамически выделять их - если вы распределяете по строкам, у вас будут ужасные выступления, потому что у вас нет непрерывного фрагмента памяти. Подробнее об этом см. документ FFTW .
Обратите внимание, что вы всегда можете описать свой отдельный кусок памяти с помощью удобной индексации массива поверх него (вы выделяете один большой блок памяти nxm, а затем создаете массив из n указателей на каждую строку).