Лекция
Привет, Вы узнаете о том , что такое хранение многомерных массивов в линейной памяти, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое хранение многомерных массивов в линейной памяти , настоятельно рекомендую прочитать все из категории Языки и методы программирования. Теория трансляции.
В вычислениях порядок строк и порядок столбцов — это методы хранения многомерных массивов в линейной памяти, такой как оперативная память .
Разница между порядками заключается в том, какие элементы массива являются смежными в памяти. В порядке строк последовательные элементы строки располагаются рядом друг с другом, тогда как то же самое верно для последовательных элементов столбца в порядке столбцов. Хотя эти термины относятся к строкам и столбцам двумерного массива, т. е. к матрице , порядок можно обобщить для массивов любой размерности, отметив, что термины «основной ряд» и «основной столбец» эквивалентны лексикографическому и колексикографическому порядкам . соответственно.
Расположение данных имеет решающее значение для правильной передачи массивов между программами, написанными на разных языках программирования. Это также важно для производительности при обходе массива, поскольку современные ЦП обрабатывают последовательные данные более эффективно, чем непоследовательные. В первую очередь это связано с кэшированием ЦП , которое использует пространственную локальность ссылки . Кроме того, непрерывный доступ позволяет использовать инструкции SIMD , которые работают с векторами данных. В некоторых носителях, таких как хранилище данных на магнитной ленте , последовательный доступ на несколько порядков быстрее, чем непоследовательный доступ.
Термины row-major и column-major происходят из терминологии, связанной с упорядочением объектов. Общий способ упорядочения объектов со многими атрибутами состоит в том, чтобы сначала сгруппировать и упорядочить их по одному атрибуту, а затем внутри каждой такой группы сгруппировать и упорядочить их по другому атрибуту и т. д. Если в упорядочении участвует более одного атрибута, то первый будет называться мажорным , а последний минорным . Если в упорядочивании участвуют два признака, то достаточно указать только главный признак.
В случае массивов атрибутами являются индексы по каждому измерению. Для матриц в математической записи первый индекс указывает на строку , а второй указывает на столбец , например, задана матрица А , Вход а1,2 находится в его первой строке и втором столбце. Это соглашение переносится на синтаксис языков программирования , хотя часто с индексами, начинающимися с 0 вместо 1.
Несмотря на то, что строка обозначается первым индексом , а столбец - вторым индексом , это не подразумевает никакого порядка группировки между измерениями. Таким образом, выбор того, как группировать и упорядочивать индексы, либо по строкам, либо по столбцам, является вопросом соглашения. Та же терминология может быть применена к массивам даже более высокой размерности. Группировка по строкам начинается с крайнего левого индекса, а по столбцам — с крайнего правого индекса, что приводит к лексикографическому и колексикографическому (или колексному) порядку соответственно.
Например, массив
может храниться двумя способами:
| Адрес | Строковый порядок | Столбец-мажорный порядок |
|---|---|---|
| 0 | а11 | а11 |
| 1 | а12 | а21 |
| 2 | а13 | а12 |
| 3 | а21 | а22 |
| 4 | а22 | а13 |
| 5 | а23 | а23 |
Языки программирования справляются с этим по-разному. В C многомерные массивы хранятся в порядке строк, а индексы массива записываются в порядке строк (лексикографический порядок доступа):
| Адрес | Доступ | Ценить |
|---|---|---|
| 0 | A |
а11 |
| 1 | A |
а12 |
| 2 | A |
а13 |
| 3 | A |
а21 |
| 4 | A |
а22 |
| 5 | A |
а23 |
С другой стороны, в Fortran массивы хранятся в порядке столбцов, в то время как индексы массива по-прежнему записываются в порядке строк (колексикографический порядок доступа):
| Адрес | Доступ | Ценить |
|---|---|---|
| 1 | A(1,1) |
а11 |
| 2 | A(2,1) |
а21 |
| 3 | A(1,2) |
а12 |
| 4 | A(2,2) |
а22 |
| 5 | A(1,3) |
а13 |
| 6 | A(2,3) |
а23 |
Обратите внимание, что использование A[i][j]с многоступенчатой индексацией, как в C, в отличие от нейтральной нотации, как A(i,j)в Fortran, почти неизбежно подразумевает построчный порядок, так сказать, по синтаксическим причинам, потому что его можно переписать как (A[i])[j], а A[i]строку часть можно даже присвоить промежуточной переменной, которая затем индексируется в отдельном выражении. Об этом говорит сайт https://intellect.icu . (Никаких других следствий не следует предполагать, например, Фортран не является основным по столбцам просто из-за его нотации, и даже вышеупомянутое следствие можно намеренно обойти в новом языке.)
Чтобы использовать основной порядок столбцов в среде строк или наоборот, по какой-либо причине, одним из обходных путей является назначение нетрадиционных ролей индексам (используя первый индекс для столбца и второй индекс для строки), а другой — обойти синтаксис языка, явно вычислив позиции в одномерном массиве. Конечно, отклонение от соглашения, вероятно, влечет за собой затраты, которые возрастают со степенью необходимого взаимодействия с традиционными языковыми функциями и другим кодом, а не только в форме повышенной уязвимости к ошибкам (забывание также инвертировать порядок умножения матриц, возвращение к соглашению во время написания кода). техническое обслуживание и т. д.), но также и в форме необходимости активной перестановки элементов, все из которых должны быть сопоставлены с какой-либо первоначальной целью, такой как повышение производительности.
Языки программирования или их стандартные библиотеки, которые поддерживают многомерные массивы, обычно имеют родной порядок хранения для этих массивов по строкам или по столбцам.
Строковый порядок используется в C / C++ / Objective-C (для массивов в стиле C), PL/I , Pascal , Speakeasy и SAS .
Порядок столбцов используется в Fortran , MATLAB , GNU Octave , Julia , S , S-PLUS , R , Scilab , Yorick и Rasdaman
Типичной альтернативой для хранения плотных массивов является использование векторов Илиффа , которые обычно хранят указатели на элементы в одной и той же строке непрерывно (например, в порядке строк), но не сами строки. Они используются в (в порядке возраста): Java , C# / CLI / .Net , Scala , и Swift .
Еще менее плотным является использование списков списков, например, в Python , и в языке Wolfram Language of Wolfram Mathematica .
Альтернативный подход использует таблицы таблиц, например, в Lua .
Поддержка многомерных массивов также может быть обеспечена внешними библиотеками, которые могут даже поддерживать произвольное упорядочение, где каждое измерение имеет значение шага, а основные строки или основные столбцы — это всего лишь две возможные результирующие интерпретации.
Строковый порядок используется по умолчанию в NumPy (для Python).
Порядок столбцов по умолчанию используется в Eigen и Armadillo (оба для C++).
Особым случаем будет OpenGL (и OpenGL ES ) для обработки графики. Поскольку «недавние математические обработки линейной алгебры и связанных с ней областей неизменно рассматривают векторы как столбцы», дизайнер Марк Сигал решил заменить это соглашением в предшественнике IRIS GL , которое должно было записывать векторы как строки; для совместимости матрицы преобразования по-прежнему будут храниться в векторно-мажорном (= строковом), а не в координатном (= столбцовом) порядке, и затем он использовал трюк «[чтобы] сказать, что матрицы в OpenGL хранятся в колонна-мажорный порядок». На самом деле это имело значение только для представления, потому что умножение матриц было основано на стеке и все еще могло быть интерпретировано как постумножение, но, что еще хуже, реальность просочилась через API на основе C, потому что доступ к отдельным элементам будет осуществляться как M[vector][coordinate]или, что фактически, M[column][row], что к сожалению, запутал соглашение, которое дизайнер стремился принять, и это было даже сохранено в языке шейдеров OpenGL , который был позже добавлен (хотя это также позволяет вместо этого обращаться к координатам по имени, например, M[vector].y). В результате многие разработчики теперь просто заявляют, что наличие столбца в качестве первого индекса является определением основного столбца, хотя это явно не так с настоящим языком с основным столбцом, таким как Fortran.
Факел (для Lua) изменен с основного порядка столбцов на основной порядок строк по умолчанию.
Поскольку обмен индексами массива является сущностью транспонирования массива , массив, хранящийся как основной по строкам, но читаемый как основной по столбцам (или наоборот), будет казаться транспонированным (пока матрица квадратная). Поскольку фактическое выполнение этой перестановки в памяти обычно является дорогостоящей операцией, некоторые системы предоставляют опции для указания отдельных матриц как хранимых в транспонированном виде. Затем программист должен решить, следует ли переупорядочивать элементы в памяти, основываясь на фактическом использовании (включая количество повторных использований массива в вычислении).
Например, функциям подпрограмм базовой линейной алгебры передаются флаги, указывающие, какие массивы транспонируются.
Концепция обобщается на массивы с более чем двумя измерениями.
Для d -мерного 
массив размерностью N k ( k =1... d ), данный элемент этого массива задается кортежем 
d (начиная с нуля) индексов 
.
В мажорном порядке последнее измерение является непрерывным, так что смещение в памяти этого элемента определяется следующим образом:
В порядке столбцов первое измерение является непрерывным, так что смещение в памяти этого элемента определяется следующим образом:
где пустое произведение является мультипликативным элементом идентичности , т. е. 
.
Для данного порядка шаг в измерении k задается значением умножения в круглых скобках перед индексом n k в суммировании правой части выше.
В общем, есть d! возможные порядки для данного массива, по одному для каждой перестановки измерений (с порядком строк и порядком столбцов всего 2 особых случая), хотя списки значений шага не обязательно являются перестановками друг друга, например, в 2-by- 3 выше, шаги равны (3,1) для основных строк и (1,2) для основных столбцов.
Исследование, описанное в статье про хранение многомерных массивов в линейной памяти, подчеркивает ее значимость в современном мире. Надеюсь, что теперь ты понял что такое хранение многомерных массивов в линейной памяти и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Языки и методы программирования. Теория трансляции
Комментарии
Оставить комментарий
Языки и методы программирования. Теория трансляции
Термины: Языки и методы программирования. Теория трансляции