Представление 2D-массива в виде массива 1D

Возможные дубликаты:
Реализация матрицы, которая более эффективна - с использованием массива массивов (2D) или массива 1D?
Производительность 2-мерного массива против 1-мерного массива

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

two_D = [[0, 1, 2],
         [3, 4, 5]]

Он будет представлен как:

one_D = [0, 1, 2, 3, 4, 5]

Если ему нужно было знать, что находится в позиции (1,1) 2D-массива, он сделает некоторую простую алгебру и получит 4.

Есть ли повышение производительности, полученное с помощью массива 1D, а не 2D-массива. Данные в массивах можно вызывать миллионы раз во время вычислений.

Я надеюсь, что объяснение структуры данных будет ясным... если не сообщите мне, и я попытаюсь объяснить это лучше.

Спасибо:)

ИЗМЕНИТЬ Язык C

Ответы

Ответ 2

Для 2-го массива ширины W и высоты H вы можете представить его как 1-й массив длины W * H, где каждый индекс

 (x,y)

где x - столбец, а y - строка, 2-мерного массива сопоставляется с индексом

i=y*W + x

в 1-D массиве. Аналогично вы можете использовать обратное отображение:

y = i / W
x = i % W

. Если вы сделаете W мощностью 2 (W = 2 м), вы можете использовать хак

y = i >> m;
x = (i & (W-1))

где эта оптимизация ограничивается только случаем, когда W является степенью 2. Компилятор, скорее всего, пропустит эту микро-оптимизацию, поэтому вам придется реализовать ее самостоятельно.

Модуль является медленным оператором в C/С++, поэтому его устранение выгодно.

Кроме того, при использовании больших 2-мерных массивов помните, что компьютер хранит их в памяти как 1-й массив и в основном вычисляет индексы, используя перечисленные выше сопоставления.

Гораздо важнее то, как вы определяете эти сопоставления, как получить доступ к массиву. Существует два способа сделать это, основные столбцы и основные строки. Способ, которым вы проходите, более важен, чем любой другой фактор, потому что он определяет, используете ли вы кеширование в своих интересах. Пожалуйста, прочитайте http://en.wikipedia.org/wiki/Row-major_order.

Ответ 3

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

Для каждой системы разные, какой тип используется, поэтому без информации о том, что вы используете, на самом деле нет способа быть уверенным. Я бы посоветовал просто проверить производительность, если это действительно важно для вас. И если производительность не так важна, то не беспокойтесь об этом.

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

Ответ 4

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

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

Ответ 5

oneD_index = 3 * y + x;

Где x - позиция внутри строки, а y - позиция в столбце. Вместо 3 вы используете ширину столбца. Таким образом, вы можете преобразовать 2D-координаты в 1D-координату.