Порядок по строкам и столбцам

редактировать

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

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

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

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

Содержание

1 Объяснение и пример
2 Программирование языки и библиотеки
- 2.1 Ни строки, ни столбец
- 2.2 Внешние библиотеки
3 Транспонирование
4 Вычисление адреса в целом
5 См. также
6 Ссылки
7 Источники

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

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

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

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

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

A = [a 11 a 12 a 13 a 21 a 22 a 23] {\ displaystyle A = {\ begin {bmatrix} a_ {11} a_ {12} a_ {13} \\ a_ {21} a_ {22} a_ {23} \ end {bmatrix}}}

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

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

Адрес	Старший порядок строк	Основной порядок столбцов
0	$a 11 {\ displaystyle a_ {11}}$ $a_ {11}$	$a 11 {\ displaystyle a_ {11}}$ $a_ {11}$
1	$a 12 {\ displaystyle a_ {12}}$ $a_ {12}$	$a 21 {\ displaystyle a_ {21}}$ $a_ {21}$
2	$a 13 {\ displaystyle a_ {13}}$ $a _ {{13}}$	$a 12 {\ displaystyle a_ {12}}$ $a_ {12}$
3	$a 21 {\ displaystyle a_ {21}}$ $a_ {21}$	$a 22 {\ displaystyle a_ {22}}$ $a _ {{22}}$
4	$a 22 {\ displaystyle a_ {22}}$ $a _ {{22}}$	$a 13 {\ displaystyle a_ {13}}$ $a _ {{13}}$
5	$a 23 {\ displaystyle a_ {23 }}$ ${\ displaystyle a_ {23}}$	$a 23 {\ displaystyle a_ {23}}$ ${\ displaystyle a_ {23}}$

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

C: основной порядок строк (лексографический порядок доступа), ноль индексирование на основе
Адрес	Доступ	Значение
0	`A [0] [0]`	$a 11 {\ displaystyle a_ {11}}$ $a_ {11}$
1	`A [0 ] [1]`	$a 12 {\ displaystyle a_ {12}}$ $a_ {12}$
2	`A [0] [2]`	$a 13 {\ displaystyle a_ {13}}$ $a _ {{13}}$
3	`A [1] [0]`	$a 21 {\ displaystyle a_ {21}}$ $a_ {21}$
4	`A [1] [1]`	$a 22 {\ displaystyle a_ {22}}$ $a _ {{22}}$
5	`A [1] [2]`	$a 23 {\ displaystyle a_ {23}}$ ${\ displaystyle a_ {23}}$

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

Fortran: основной порядок столбцов (колексографический порядок доступа), индексирование на основе единицы
Адрес	Доступ	Значение
1	`A (1,1)`	$a 11 {\ displaystyle a_ {11}}$ $a_ {11}$
2	`A (2,1)`	$a 21 {\ displaystyle a_ {21}}$ $a_ {21}$
3	`A (1,2)`	$a 12 {\ displaystyle a_ {12}}$ $a_ {12}$
4	`А (2,2)`	$а 22 {\ displa ystyle a_ {22}}$ $a _ {{22}}$
5	`A (1,3)`	$a 13 {\ displaystyle a_ {13}}$ $a _ {{13}}$
6	`A (2,3)`	$a 23 {\ displaystyle a_ {23}}$ ${\ displaystyle a_ {23}}$

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

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

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

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

Старший порядок строк используется в C /C ++ / Objective-C (для массивов в стиле C), PL / I, Паскаль, Speakeasy, SAS и Rasdaman.

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

Ни строковый, ни главный столбец

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

Еще менее плотный заключается в использовании списков списков, например, в Python и в языке Wolfram Language из Wolfram Mathematica.

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

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

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

Порядок строк по умолчанию в NumPy (для Python).

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

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

Torch (для Lua) изменен с основного столбца на основной порядок строк по умолчанию.

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

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

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

Вычисление адреса в целом

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

Для d-мерного $N 1 × N 2 × ⋯ × N d {\ displaystyle N_ {1} \ times N_ {2} \ times \ cdots \ times N_ {d}}$ $N_1 \ times N_2 \ times \ cdots \ times N_d$ массив с размерами N k (k = 1... d), данный элемент этого массива определяется tuple $(n 1, n 2,…, nd) {\ displaystyle (n_ {1}, n_ {2}, \ ldots, n_ {d})}$ $(n_1, n_2, \ ldots, n_d)$ индексов d (с отсчетом от нуля) $nk ∈ [0, N k - 1] {\ displaystyle n_ {k} \ in [0, N_ {k} -1]}$ $n_k \ in [0, N_k - 1]$ .

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

nd + N d ⋅ (nd - 1 + N d - 1 ⋅ (nd - 2 + N d - 2 ⋅ (⋯ + N 2 n 1) ⋯))) = ∑ k = 1 d (∏ ℓ знак равно К + 1 d N ℓ) nk {\ 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}}

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 ⋅ (n 2 + N 2 ⋅ (n 3 + N 3 ⋅ (⋯ + N d - 1 nd) ⋯))) = ∑ К знак равно 1 d (∏ ℓ = 1 К - 1 N ℓ) nk {\ 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}}

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

где пустой продукт - это мультипликативный элемент идентичности, т. Е. $∏ ℓ знак равно 1 0 N ℓ знак равно ∏ ℓ знак равно d + 1 d N ℓ = 1 {\ displaystyle \ prod _ {\ ell = 1} ^ {0} N _ {\ ell} = \ prod _ {\ ell = d +1} ^ {d} N _ {\ ell} = 1}$ ${\ 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, метод хранения разреженных матриц в памяти
порядок Мортона, еще один способ отображения многомерных данных в одномерный индекс, полезный в древовидных структурах данных

Ссылки

^«Массивы и форматированный I / О ". Учебное пособие по FORTRAN. Проверено 19 ноября 2016 г.
^«Почему нумерация должна начинаться с нуля». Архив Э. В. Дейкстры. Проверено 2 февраля 2017 г.
^«Справочник по языку, версия 4, выпуск 3» (PDF). IBM. Дата обращения 13 ноября 2017. Начальные значения, указанные для массива, присваиваются последовательным элементам массива в порядке возрастания строк (последний индекс изменяется наиболее быстро).
^«ISO / IEC 7185: 1990 (E)» (PDF). Тип-массив, который определяет последовательность из двух или более типов-индексов, должен быть сокращенным обозначением для указанного типа-массива, чтобы иметь в качестве своего типа индекса первый тип индекса в последовательности и иметь компонент: тип, который является типом массива, определяющим последовательность типов индекса без первого типа индекса в последовательности и указывающим тот же тип компонента, что и исходная спецификация.
^«Справочник по языку SAS® 9.4: концепции, шестое издание» (PDF). SAS Institute Inc. 6 сентября 2017 г. с. 573. Проверено 18 ноября 2017 г. Справа налево крайнее правое измерение представляет столбцы; следующее измерение представляет собой строки. [...] SAS помещает переменные в многомерный массив, заполняя все строки по порядку, начиная с верхнего левого угла массива (известный как порядок основных строк).
^«Внутреннее представление массива в расдамане». rasdaman.org. Получено 8 июня 2017 г.
^Документация MATLAB, Хранилище данных MATLAB (получено с Mathworks.co.uk, январь 2014 г.).
^Spiegelhalter et al. (2003, стр. 17): Шпигельхальтер, Дэвид ; Томас, Эндрю; Бест, Ники ; Ланн, Дэйв (январь 2003 г.), «Форматирование данных: формат S-Plus», Руководство пользователя WinBUGS (PDF) (версия 1.4, изд.), Кембридж, Великобритания: MRC Biostatistics Unit, Институт общественного здравоохранения, заархивировано из исходного (PDF) от 18 мая 2003 г. CS1 maint: ref = harv (ссылка )
^Введение в R, Раздел 5.1: Массивы (получено в марте 2010 г.).
^«Многомерные массивы». Julia. Получено 6 февраля 2016 г.
^«БПФ с многомерными данными». Scilab Wiki. Проверено 25 ноября 2017 г. Поскольку Scilab хранит массивы в формате основного столбца, элементы столбца являются смежными (т. Е. Разделение на 1) в линейном формате.
^«Спецификация языка Java». Oracle. Проверено 13 февраля 2016 г.
^«object Array». Стандартная библиотека Scala. Проверено 1 мая 2016 г.
^«Стандартная библиотека Python: 8. Типы данных». Проверено 18 ноября 2017 г.
^«Векторы и матрицы». Wolfram. Проверено 12 ноября 2017 г.
^«11.2 - Матрицы и многомерные массивы». Проверено 6 февраля 2016 г.
^«N-мерный массив (ndarray)». SciPy.org. Проверено 3 апреля 2016 г.
^«Eigen: Storage orders». eigen.tuxfamily.org. Проверено 23 ноября 2017. Если порядок хранения не указан, то Eigen по умолчанию сохраняет запись в главном столбце.
^«Векторы столбца против векторов строк» . Проверено 12 ноября 2017 г.
^«Tensor». Проверено 6 февраля 2016 г.
^«Tensor». Справочное руководство по пакету горелки. Проверено 8 мая 2016 г.
^«BLAS (Основные подпрограммы линейной алгебры)». Проверено 16 мая 2015 г.

Источники

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