2D-Array: предпочтительный способ доступа к элементам

Question

Итак, вот я сегодня вечером с этим вопросом, который возник у меня в голове:

Какой ваш любимый способ доступа к элементам матрицы m x n

есть нормальный способ использования индекса для столбцов и еще один индекс для матрицы строк [i] [j]

и есть другой способ, где ваша матрица - это вектор длины m * n и вы получаете доступ к элементам, используя [i * n + j] в качестве номера индекса

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

Answer 1

Допустим, у нас есть этот фрагмент кода C (++):

 int x = 3;
 int y = 4;

 arr2d[x][y]   = 0xFF;
 arr1d[x*10+y] = 0xFF;

Где:

 unsigned char arr2d[10][10];
 unsigned char arr1d[10*10];

А теперь давайте посмотрим на его скомпилированную версию (сборка;используя отладчик):

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

Answer 2

Существует только две причины, по которым одномерный массив должен представлять n-измерения, о которых я могу думать:

• Производительность. Обычный способ выделения n-мерных массивов означает, что мы получаем n измерений, которые не обязательно должны быть распределены в одном фрагменте - что не так уж хорошо для пространственной локализации (и может также привести к некоторые дополнительные обращения к памяти - в худшем случае нам нужно 1 дополнительное чтение для каждого доступа). Теперь в C / C ++ вы можете обойти это (выделить память одним куском, а затем указать правильные указатели; будьте очень осторожны, чтобы не забыть об этом при удалении), и другие языки (C #) уже могут делать это из коробка. Также обратите внимание, что в языке с GC stop & copy рассуждения не нужны, так как все объекты будут расположены так или иначе рядом друг с другом. Вы избегаете дополнительных издержек для каждого отдельного измерения, поэтому используете свою память и кешируете немного лучше.

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

Answer 3

Если бы я использовал двумерный массив, я бы проголосовал за матрицу [i] [j]. Я думаю, что это более читабельно. Тем не менее, я мог бы рассмотреть возможность использования класса таблицы Гуавы. http://guava -libraries.googlecode.com / SVN / багажник / Javadoc / COM / Google / общие / собирать / Table.html

Answer 4

Я не думаю, что ваш «любимый» или наиболее эстетически приятный способ - это хороший подход к решению этой проблемы - основной задачей будет моя основная задача.

Хранение матрицы какнепрерывный массив часто является наиболее эффективным способом выполнения матричных вычислений.Если вы посмотрите на оптимизированные библиотеки BLAS (Basic Linear Algebra Subroutine), такие как Intel MKL, AMD ACML, ATLAS и т. Д., То будет использоваться непрерывное хранилище матриц.Когда используется непрерывное хранилище и используются непрерывные шаблоны доступа к данным, может быть получена более высокая производительность из-за улучшенного ссылочного местоположения (т. Е. Производительности кэша) операций.

В некоторых языках (например, c++)вы могли бы использовать перегрузку операторов для достижения стиля индексации data[i][j] при выполнении сопоставлений индексов массива 1D за кулисами.

Надеюсь, это поможет.

Answer 5

Я думаю, что если вам нужен двумерный массив, это потому, что вы хотели бы получить к нему доступ как к двумерному массиву, а не как одномерный массив

В противном случае вы можете сделать простое умножение, чтобы сделать его одномерным массивом