Есть ли разница в эффективности между одномерным массивом и двумерным массивом (матрицей)?

Question

Сейчас я занимаюсь разработкой настольной игры на Си для университета. И учитель предоставил некоторый код, и способ, которым он хранит плату в памяти, - это одномерный массив, доска имеет 16 элементов (доска 4x4), а строка 0 находится в позициях [0, 3], строка 2 находится в позициях [ 4, 7] и т. Д. Он также использует приведенные ниже функции для преобразования 2-мерных координат (i, j) в 1-мерную координацию для правильного доступа к правильному положению доски (функции приведены ниже). Эта плата будет управляться несколькими потоками, может быть, это поможет с многопоточной синхронизацией? И мой вопрос: менее эффективно хранить плату в 2-мерном массиве (матрице) с 4 строками и 4 столбцами?

int linearConv(int i, int j){
  return j*dim+i;
}
char* getBoardPlaceStr(int i, int j){
  return board[linearConv(i, j)].v;
}

PS: Кроме того, имеет ли доступ к массиву, подобному массиву [0], разыменование указателя (т. Е. * Указателя), доступ к элементу структуры (т.е. элементу struct.member или sutuct-> member), для которого не нужны критические области?

Answer 1

Менее эффективно хранить плату в 2-мерном массиве (матрице) с 4 строками и 4 столбцами?

Оба:

T board[4][4];

И

T board[4 * 4];

Имеют одинаковый размер, выравнивание и расположение. Как правило, элементы в любых размерных массивах хранятся непрерывно без пробелов (в противном случае арифметика указателей не будет работать).

Доступ к элементам с использованием [j][i] и [j * 4 + i] выполняет те же вычисления в сборке.

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

Answer 2

Элементы массива находятся рядом друг с другом в памяти для произвольного измерения.

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

В информатике существует нечто, называемое принципом локальности.Либо в пространстве, либо во времени.

Относительно массивов мы получили место в пространстве, которое говорит, что доступ к элементу в arr[1][1] будет , вероятно, , приведет к доступу к элементу arr[1][2], тоже.

Проверьте этот ответ о том, как доступ к массивам (по строкам / по столбцам) может повлиять на эффективность.

Answer 3

Эта доска будет управляться несколькими потоками, возможно, это поможет с многопоточной синхронизацией?

Не вижу причин ожидать этого.

И мой вопрос: это меньше? эффективно хранить плату в 2-мерном массиве (матрице) с 4 строки и 4 столбца?

Нет, в C не менее эффективно хранить плату в добросовестном 2D массиве. Макет в памяти неотличим от макета 1D, который вы описываете, и вычисления индексации для извлечения элементов, таким образом, полностью эквивалентны вычислениям в представленном коде.

То же самое не относится к некоторым другим языкам, таким как Java, где каждое измерение требует разыменования отдельного указателя, а массивы, как объекты, имеют дополнительные связанные данные и метаданные, помимо элементов. Подобная структура данных также может быть сформирована в C, но, хотя она может быть проиндексирована, как если бы это был многомерный массив, ее структура и структура на самом деле совершенно иные.

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

Также доступ к массиву, подобному массиву [0], разыменование указателя (т.е. * указатель), доступ к члену структуры (например, struct.member или sutuct-> member) атомарные операции, которым не нужны критические области?

Нет, ни один из них не является атомарным в том смысле, который вы имеете в виду.