Порядок строк и столбцов

Иллюстрация разницы между порядком по строкам и столбцам

В вычислениях порядок по строкам и по столбцам - это методы хранения многомерных массивов в линейных хранилищах, таких как оперативная память .

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

Макет данных имеет решающее значение для правильной передачи массивов между программами, написанными на разных языках программирования. Это также важно для производительности при обходе массива, поскольку современные процессоры обрабатывают последовательные данные более эффективно, чем непоследовательные данные. В первую очередь это связано с кешированием ЦП . Кроме того, непрерывный доступ позволяет использовать инструкции SIMD, которые работают с векторами данных. В некоторых носителях, таких как лента или флэш-память NAND , последовательный доступ на несколько порядков быстрее, чем непоследовательный доступ. ^{[ необходима цитата ]}

Объяснение и пример [ править ]

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

В случае массивов атрибуты - это индексы по каждому измерению. Для получения матриц в математической нотации, первый индекс обозначает строку , а второй указывает на столбец , например, с учетом матрицы , находится в первой строке и втором столбце. Это соглашение перенесено в синтаксис языков программирования ^[1], хотя часто индексы начинаются с 0 вместо 1. ^[2]${\ displaystyle A}$${\ displaystyle a_ {1,2}}$

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

Например, массив

${\ displaystyle A = {\ begin {bmatrix} a_ {11} & a_ {12} & a_ {13} \\ a_ {21} & a_ {22} & a_ {23} \ end {bmatrix}}}$

может храниться двумя способами:

Адрес	Рядный порядок	Столбец-мажорный порядок
0	${\ displaystyle a_ {11}}$	${\ displaystyle a_ {11}}$
1	${\ displaystyle a_ {12}}$	${\ displaystyle a_ {21}}$
2	${\ displaystyle a_ {13}}$	${\ displaystyle a_ {12}}$
3	${\ displaystyle a_ {21}}$	${\ displaystyle a_ {22}}$
4	${\ displaystyle a_ {22}}$	${\ displaystyle a_ {13}}$
5	${\ displaystyle a_ {23}}$	${\ displaystyle a_ {23}}$

Разные языки программирования справляются с этим по-разному. В C многомерные массивы хранятся в порядке строк, а индексы массивов записываются сначала строкой (лексикографический порядок доступа):

C: строковый порядок (лексографический порядок доступа), индексирование с нуля

Адрес	Доступ	Ценить
0	A[0][0]	${\ displaystyle a_ {11}}$
1	A[0][1]	${\ displaystyle a_ {12}}$
2	A[0][2]	${\ displaystyle a_ {13}}$
3	A[1][0]	${\ displaystyle a_ {21}}$
4	A[1][1]	${\ displaystyle a_ {22}}$
5	A[1][2]	${\ displaystyle a_ {23}}$

С другой стороны, в Фортране массивы хранятся в порядке по столбцам, в то время как индексы массивов по-прежнему записываются по строкам (колексикографический порядок доступа):

Фортран: порядок столбцов (колексографический порядок доступа), индексирование на основе одного

Адрес	Доступ	Ценить
1	A(1,1)	${\ displaystyle a_ {11}}$
2	A(2,1)	${\ displaystyle a_ {21}}$
3	A(1,2)	${\ displaystyle a_ {12}}$
4	A(2,2)	${\ displaystyle a_ {22}}$
5	A(1,3)	${\ displaystyle a_ {13}}$
6	A(2,3)	${\ displaystyle a_ {23}}$

Обратите внимание, как использование A[i][j]многоступенчатой ​​индексации, как в C, в отличие от нейтральной нотации, такой A(i,j)как в Fortran, почти неизбежно подразумевает основной порядок строк по синтаксическим причинам, так сказать, потому что его можно переписать как (A[i])[j], а A[i]строка part можно даже присвоить промежуточной переменной, которая затем индексируется в отдельном выражении. (Никаких других последствий не следует предполагать, например, Fortran не является основным столбцом просто из- за своей нотации, и даже указанное выше значение можно намеренно обойти на новом языке.)

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

Языки программирования и библиотеки [ править ]

Языки программирования или их стандартные библиотеки, которые поддерживают многомерные массивы, обычно имеют собственный порядок хранения для этих массивов - по строкам или по столбцам.

Порядок строк используется в C / C ++ / Objective-C (для массивов в стиле C), PL / I , ^[3] Pascal , ^[4] Speakeasy , ^{[ необходима ссылка ]} SAS , ^[5] и Rasdaman . ^[6]

Порядок по столбцам используется в Fortran , MATLAB , ^[7] GNU Octave , S-Plus , ^[8] R , ^[9] Julia , ^[10] и Scilab . ^[11]

Ни строк, ни столбцов [ править ]

Типичной альтернативой для хранения плотных массивов является использование векторов Илиффа , которые обычно хранят элементы в одной строке непрерывно (например, в порядке старших строк), но не сами строки. Они используются (упорядочены по возрасту): Java , ^[12] C # / CLI / .Net , Scala , ^[13] и Swift .

Даже менее плотно, чтобы использовать списки списков, например, в Python , ^[14] и в Wolfram языке в Wolfram Mathematica . ^[15]

Альтернативный подход использует таблицы таблиц, например, в Lua . ^[16]

Внешние библиотеки [ править ]

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

По умолчанию в NumPy ^[17] (для Python) используется порядок строк .

По умолчанию в Eigen ^[18] и Armadillo (оба для C ++) используется порядок столбцов .

Особым случаем будет OpenGL (и OpenGL ES ) для обработки графики. Поскольку «недавние математические трактовки линейной алгебры и родственных областей неизменно рассматривают векторы как столбцы», дизайнер Марк Сигал решил заменить это соглашение в предшественнике IRIS GL , которое заключалось в записи векторов в виде строк; для совместимости матрицы преобразования по-прежнему будут храниться в векторном порядке, а не в порядке главных координат, и затем он использовал «уловку, чтобы сказать, что матрицы в OpenGL хранятся в порядке основных столбцов». ^[19] Это было действительно актуально только для презентации, потому что умножение матриц было основано на стеке и все еще могло быть интерпретировано как пост-умножение, но, что еще хуже, реальность просочилась через основанный на C.API, потому что отдельные элементы будут доступны как M[vector][coordinate]или, по сути, M[column][row]что, к сожалению, запутало соглашение, которое дизайнер стремился принять, и это даже было сохранено в языке затенения OpenGL, который был позже добавлен (хотя это также позволяет получить доступ к координатам с помощью имя, например, M[vector].y). В результате многие разработчики теперь просто заявляют, что наличие столбца в качестве первого индекса является определением основного столбца, хотя это явно не относится к настоящему языку с основным столбцом, таким как Fortran.

Torch (для Lua) изменен с основного столбца ^[20] на основной столбец ^{[21] по} умолчанию.

Транспонирование [ править ]

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

Например, функциям подпрограмм базовой линейной алгебры передаются флаги, указывающие, какие массивы транспонируются. ^[22]

Расчет адреса в целом [ править ]

Эта концепция распространяется на массивы с более чем двумя измерениями.

Для d -мерного массива с размерами N _k ( k = 1 ... d ) данный элемент этого массива задается кортежем из d ( отсчитываемых от нуля) индексов .${\ displaystyle N_ {1} \ times N_ {2} \ times \ cdots \ times N_ {d}}$ ${\ displaystyle (n_ {1}, n_ {2}, \ ldots, n_ {d})}$${\ displaystyle n_ {k} \ in [0, N_ {k} -1]}$

В строковом порядке последнее измерение является смежным, так что смещение памяти этого элемента задается следующим образом:

${\displaystyle n_{d}+N_{d}\cdot (n_{d-1}+N_{d-1}\cdot (n_{d-2}+N_{d-2}\cdot (\cdots +N_{2}n_{1})\cdots )))=\sum _{k=1}^{d}\left(\prod _{\ell =k+1}^{d}N_{\ell }\right)n_{k}}$

В порядке столбца первое измерение является смежным, так что смещение памяти этого элемента задается следующим образом:

${\displaystyle n_{1}+N_{1}\cdot (n_{2}+N_{2}\cdot (n_{3}+N_{3}\cdot (\cdots +N_{d-1}n_{d})\cdots )))=\sum _{k=1}^{d}\left(\prod _{\ell =1}^{k-1}N_{\ell }\right)n_{k}}$

где пустой продукт - мультипликативный единичный элемент , т . е ..${\displaystyle \prod _{\ell =1}^{0}N_{\ell }=\prod _{\ell =d+1}^{d}N_{\ell }=1}$

Для данного порядка шаг в размерности k задается значением умножения в скобках перед индексом n _k в суммировании справа вверху.

В общем, есть d! возможных порядков для данного массива, по одному для каждой перестановки измерений (с основными случаями строки и порядком столбца только в двух особых случаях), хотя списки значений шага не обязательно являются перестановками друг друга, например, в формате 2 на В примере 3 выше, шаги: (3,1) для высшей строки и (1,2) для высшей строки столбца.

См. Также [ править ]

• Структура данных массива
• Матричное представление
• Векторизация (математика) , эквивалент превращения матрицы в соответствующий вектор-столбец
• Формат CSR , метод хранения разреженных матриц в памяти
• Порядок Мортона , еще один способ сопоставления многомерных данных с одномерным индексом, полезный в древовидных структурах данных.

Ссылки [ править ]

Источники [ править ]

• Дональд Э. Кнут, Искусство компьютерного программирования, том 1: фундаментальные алгоритмы , третье издание, раздел 2.2.6 (Addison-Wesley: New York, 1997).