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

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

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

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

Объяснение и пример

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

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

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

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

A=a_{y,x}={\begin{bmatrix}\color {Blue}a_{11}&\color {Blue}a_{12}&\color {Blue}a_{13}\\\color {Orange}a_{21}&\color {Orange}a_{22}&\color {Orange}a_{23}\end{bmatrix}}

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

Адрес	Порядок строк	Столбец-основной порядок
0	$\color {Blue}a_{11}$	$\color {Blue}a_{11}$
1	$\color {Blue}a_{12}$	$\color {Orange}a_{21}$
2	$\color {Blue}a_{13}$	$\color {Blue}a_{12}$
3	$\color {Orange}a_{21}$	$\color {Orange}a_{22}$
4	$\color {Orange}a_{22}$	$\color {Blue}a_{13}$
5	$\color {Orange}a_{23}$	$\color {Orange}a_{23}$

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

C: порядок строк (лексикографический порядок доступа), индексация с нуля.
Адрес `x + N_x*y`	Доступ `A[y][x]`	Ценить $a_{y,x}$
0	`A[0][0]`	$a_{11}$
1	`A[0][1]`	$a_{12}$
2	`A[0][2]`	$a_{13}$
3	`A[1][0]`	$a_{21}$
4	`A[1][1]`	$a_{22}$
5	`A[1][2]`	$a_{23}$

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

Фортран: порядок по столбцам (колексикографический порядок доступа), индексация по единице.
Адрес `y + N_y*(x-1)`	Доступ `A(y,x)`	Ценить $a_{y,x}$
1	`A(1,1)`	$a_{11}$
2	`A(2,1)`	$a_{21}$
3	`A(1,2)`	$a_{12}$
4	`A(2,2)`	$a_{22}$
5	`A(1,3)`	$a_{13}$
6	`A(2,3)`	$a_{23}$

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

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

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

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

Порядок строк используется в C / C++ / Objective-C (для массивов в стиле C), PL/I , ^[4] Паскаль , ^[5] Говори легко , ^{[ нужна ссылка ]} и САС . ^[6]

Порядок столбцов используется в Фортране , ^[7]^[8] ИДЛ , ^[7] МАТЛАБ , ^[8] GNU Octave , Джулия , ^[9] С , С-ПЛЮС , ^[10] Р , ^[11] Скилаб , ^[12] Йорик и Расдаман . ^[13]

Ни по строкам, ни по столбцам

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

Еще менее плотным является использование списков списков, например, в Python , ^[16] и в языке Wolfram Language компании Wolfram Mathematica . ^[17]

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

Внешние библиотеки

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

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

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

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

Torch (для Lua) изменен с Column-Major. ^[22] грести-майору ^[23] порядок по умолчанию.

Транспонирование

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

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

Расчет адреса в целом

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

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

В порядке следования строк последнее измерение является смежным, так что смещение в памяти этого элемента определяется выражением: $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}$

В порядке столбцов первое измерение является смежным, так что смещение в памяти этого элемента определяется выражением: $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}$ где пустой продукт является мультипликативным единичным элементом , т.е. ${\textstyle \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 — метод хранения разреженных матриц в памяти.
Векторизация (математика) , эквивалент превращения матрицы в соответствующий вектор со столбцом.

Ссылки

^ «Кэш-память» . Питер Ларс Дордал . Проверено 10 апреля 2021 г.
^ «Массивы и форматированный ввод-вывод» . Учебное пособие по ФОРТРАну . Проверено 19 ноября 2016 г.
^ «Почему нумерация должна начинаться с нуля» . Архив Э. В. Дейкстры . Проверено 2 февраля 2017 г.
^ «Справочник по языку, версия 4, выпуск 3» (PDF) . ИБМ . Проверено 13 ноября 2017 г. Начальные значения, указанные для массива, присваиваются последовательным элементам массива в порядке возрастания строк (конечный индекс меняется быстрее всего).
^ «ISO/IEC 7185:1990(E)» (PDF) . Тип массива, который определяет последовательность двух или более типов индекса, должен представлять собой сокращенную запись для типа массива, указанного для того, чтобы иметь в качестве типа индекса первый тип индекса в последовательности и иметь тип компонента, который тип массива, определяющий последовательность типов индексов без первого типа индекса в последовательности и определяющий тот же тип компонента, что и исходная спецификация.
^ «Справочник по языку SAS® 9.4: концепции, шестое издание» (PDF) . SAS Institute Inc., 6 сентября 2017 г., с. 573 . Проверено 18 ноября 2017 г. Справа налево самое правое измерение представляет столбцы; следующее измерение представляет строки. [...] SAS помещает переменные в многомерный массив, заполняя все строки по порядку, начиная с верхнего левого угла массива (известный как порядок по строкам).
^ Jump up to: ^а ^б «Столбцы, строки и большинство массивов» . www.nv5geospatialsoftware.com . Проверено 31 июля 2024 г.
^ Jump up to: ^а ^б Документация MATLAB, хранилище данных MATLAB (получено с сайта Mathworks.co.uk, январь 2014 г.).
^ «Многомерные массивы» . Джулия . Проверено 9 ноября 2020 г.
^ Шпигельхальтер и др. (2003 , стр. 17): Шпигельхальтер, Дэвид ; Томас, Эндрю; С уважением, Ники ; Ланн, Дэйв (январь 2003 г.), «Форматирование данных: формат S-Plus», Руководство пользователя WinBUGS (PDF) (версия 1.4 изд.), Кембридж, Великобритания: Отдел биостатистики MRC, Институт общественного здравоохранения, заархивировано из оригинала ( PDF) от 18 мая 2003 г.
^ Введение в R , Раздел 5.1: Массивы (получено в марте 2010 г.).
^ «БПФ с многомерными данными» . Скилаб Вики . Проверено 25 ноября 2017 г. Поскольку Scilab хранит массивы в формате основного столбца, элементы столбца являются смежными (т.е. расстояние между ними равно 1) в линейном формате.
^ «Представление внутреннего массива в расдамане» . rasdaman.org . Проверено 29 мая 2022 г.
^ «Спецификация языка Java» . Оракул . Проверено 13 февраля 2016 г.
^ «массив объектов» . Стандартная библиотека Scala . Проверено 1 мая 2016 г.
^ «Стандартная библиотека Python: 8. Типы данных» . Проверено 18 ноября 2017 г.
^ «Векторы и матрицы» . Вольфрам . Проверено 12 ноября 2017 г.
^ «11.2 – Матрицы и многомерные массивы» . Проверено 6 февраля 2016 г.
^ «N-мерный массив (ndarray)» . SciPy.org . Проверено 3 апреля 2016 г.
^ «Эйген: Заказы на хранение» . eigen.tuxfamily.org . Проверено 23 ноября 2017 г. Если порядок хранения не указан, то Eigen по умолчанию сохраняет запись в столбце.
^ «Векторы-столбцы и векторы-строки» . Проверено 12 ноября 2017 г.
^ «Тензор» . Проверено 6 февраля 2016 г.
^ «Тензор» . Справочное руководство по комплекту горелок . Проверено 8 мая 2016 г.
^ «BLAS (Базовые подпрограммы линейной алгебры)» . Проверено 16 мая 2015 г.

Источники

Дональд Э. Кнут, Искусство компьютерного программирования, том 1: Фундаментальные алгоритмы , третье издание, раздел 2.2.6 (Аддисон-Уэсли: Нью-Йорк, 1997).

[Peter_Lars_Dordal-1] «Кэш-память» . Питер Ларс Дордал . Проверено 10 апреля 2021 г.

[2] «Массивы и форматированный ввод-вывод» . Учебное пособие по ФОРТРАну . Проверено 19 ноября 2016 г.

[3] «Почему нумерация должна начинаться с нуля» . Архив Э. В. Дейкстры . Проверено 2 февраля 2017 г.

[4] «Справочник по языку, версия 4, выпуск 3» (PDF) . ИБМ . Проверено 13 ноября 2017 г. Начальные значения, указанные для массива, присваиваются последовательным элементам массива в порядке возрастания строк (конечный индекс меняется быстрее всего).

[5] «ISO/IEC 7185:1990(E)» (PDF) . Тип массива, который определяет последовательность двух или более типов индекса, должен представлять собой сокращенную запись для типа массива, указанного для того, чтобы иметь в качестве типа индекса первый тип индекса в последовательности и иметь тип компонента, который тип массива, определяющий последовательность типов индексов без первого типа индекса в последовательности и определяющий тот же тип компонента, что и исходная спецификация.

[6] «Справочник по языку SAS® 9.4: концепции, шестое издание» (PDF) . SAS Institute Inc., 6 сентября 2017 г., с. 573 . Проверено 18 ноября 2017 г. Справа налево самое правое измерение представляет столбцы; следующее измерение представляет строки. [...] SAS помещает переменные в многомерный массив, заполняя все строки по порядку, начиная с верхнего левого угла массива (известный как порядок по строкам).

[IDL-7] Jump up to: ^а ^б «Столбцы, строки и большинство массивов» . www.nv5geospatialsoftware.com . Проверено 31 июля 2024 г.

[MATLAB-8] Jump up to: ^а ^б Документация MATLAB, хранилище данных MATLAB (получено с сайта Mathworks.co.uk, январь 2014 г.).

[9] «Многомерные массивы» . Джулия . Проверено 9 ноября 2020 г.

[WinBUGS-10] Шпигельхальтер и др. (2003 , стр. 17): Шпигельхальтер, Дэвид ; Томас, Эндрю; С уважением, Ники ; Ланн, Дэйв (январь 2003 г.), «Форматирование данных: формат S-Plus», Руководство пользователя WinBUGS (PDF) (версия 1.4 изд.), Кембридж, Великобритания: Отдел биостатистики MRC, Институт общественного здравоохранения, заархивировано из оригинала ( PDF) от 18 мая 2003 г.

[11] Введение в R , Раздел 5.1: Массивы (получено в марте 2010 г.).

[12] «БПФ с многомерными данными» . Скилаб Вики . Проверено 25 ноября 2017 г. Поскольку Scilab хранит массивы в формате основного столбца, элементы столбца являются смежными (т.е. расстояние между ними равно 1) в линейном формате.

[13] «Представление внутреннего массива в расдамане» . rasdaman.org . Проверено 29 мая 2022 г.

[14] «Спецификация языка Java» . Оракул . Проверено 13 февраля 2016 г.

[15] «массив объектов» . Стандартная библиотека Scala . Проверено 1 мая 2016 г.

[16] «Стандартная библиотека Python: 8. Типы данных» . Проверено 18 ноября 2017 г.

[17] «Векторы и матрицы» . Вольфрам . Проверено 12 ноября 2017 г.

[18] «11.2 – Матрицы и многомерные массивы» . Проверено 6 февраля 2016 г.

[19] «N-мерный массив (ndarray)» . SciPy.org . Проверено 3 апреля 2016 г.

[20] «Эйген: Заказы на хранение» . eigen.tuxfamily.org . Проверено 23 ноября 2017 г. Если порядок хранения не указан, то Eigen по умолчанию сохраняет запись в столбце.

[21] «Векторы-столбцы и векторы-строки» . Проверено 12 ноября 2017 г.

[22] «Тензор» . Проверено 6 февраля 2016 г.

[23] «Тензор» . Справочное руководство по комплекту горелок . Проверено 8 мая 2016 г.

[24] «BLAS (Базовые подпрограммы линейной алгебры)» . Проверено 16 мая 2015 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]