Введение

Представление массивов в компьютерной памяти

В вычислительной технике порядок хранения по строкам и порядок хранения по столбцам — это методы хранения многомерных массивов в линейном хранилище, таком как оперативная память. Различие между этими порядками заключается в том, какие элементы массива располагаются последовательно в памяти. При порядке хранения по строкам последовательные элементы строки находятся рядом друг с другом, а при порядке хранения по столбцам то же самое верно для последовательных элементов столбца. Хотя эти термины отсылают к строкам и столбцам двумерного массива, то есть матрицы, эти порядки можно обобщить на массивы любой размерности, учитывая, что порядок хранения по строкам и порядок хранения по столбцам эквивалентны лексикографическому и колексикографическому порядку соответственно. Важно также отметить, что матрицы, которые обычно представляются как наборы строчных или столбцовых векторов, при использовании этого подхода эффективно хранятся как последовательные векторы или последовательные компоненты векторов. Такие способы хранения данных называются AoS (Array of Structures) и SoA (Structure of Arrays) соответственно. Организация данных критически важна для корректной передачи массивов между программами, написанными на разных языках программирования. Она также важна для производительности при обходе массива, поскольку современные процессоры более эффективно обрабатывают последовательные данные, чем непоследовательные. Это в основном связано с кэшированием процессора, которое использует принцип пространственной локальности. Кроме того, последовательный доступ позволяет использовать SIMD-инструкции, которые работают с векторами данных. В некоторых средах хранения данных, таких как магнитная лента, последовательный доступ значительно быстрее, чем непоследовательный.

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

Языки программирования или их стандартные библиотеки, поддерживающие многомерные массивы, как правило, имеют встроенный порядок хранения – по строкам или по столбцам. Порядок по строкам используется в C/C++/Objective C (для массивов в стиле C), PL/I, Pascal, Speakeasy и SAS. Порядок по столбцам используется в Fortran, MATLAB, GNU Octave, Julia, S, S PLUS, R, Scilab, Yorick и Rasdaman.

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

Типичной альтернативой для хранения разреженных массивов является использование векторов Iliffe, которые обычно хранят указатели на элементы в одной строке последовательно (как в порядке главных строк), но не сами строки. Они используются в (в порядке возрастания возраста): Java, C#/CLI/.NET, Scala и Swift. Ещё более разреженным способом является использование списков списков, например, в Python и в Wolfram Language системы Wolfram Mathematica. Альтернативный подход использует таблицы таблиц, например, в Lua.

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

Поддержка многомерных массивов также может предоставляться внешними библиотеками, которые могут даже поддерживать произвольные порядки, где каждое измерение имеет значение шага, а порядок по строкам или по столбцам – лишь две возможные интерпретации. Порядок по строкам является значением по умолчанию в NumPy (для Python). Порядок по столбцам является значением по умолчанию в Eigen и Armadillo (для C++). Особым случаем является OpenGL (и OpenGL ES) для обработки графики. Поскольку "современные математические работы по линейной алгебре и смежным областям неизменно рассматривают векторы как столбцы", дизайнер Марк Сегал решил заменить эту конвенцию на принятую в предшественнике IRIS GL, где векторы записывались как строки; для совместимости матрицы преобразований по-прежнему хранились в порядке векторов (= строк) вместо порядка координат (= столбцов), а затем он использовал уловку, "[чтобы] заявить, что матрицы в OpenGL хранятся в порядке по столбцам". Это было важно главным образом для представления, поскольку умножение матриц осуществлялось на основе стека и могло интерпретироваться как пост-умножение, но, что хуже, реальность проявилась через C-API, поскольку к отдельным элементам обращались как M[вектор][координата] или, по сути, M[столбец][строка], что, к сожалению, запутало конвенцию, которую дизайнер стремился внедрить, и это даже сохранилось в языке шейдеров OpenGL, который был добавлен позже (хотя это также позволяет обращаться к координатам по имени, например, M[вектор].y). В результате многие разработчики теперь просто утверждают, что наличие столбца в качестве первого индекса является определением порядка по столбцам, хотя это явно не соответствует действительности для языка с настоящим порядком по столбцам, такого как Fortran. Torch (для Lua) изменил порядок по умолчанию с порядка по столбцам на порядок по строкам.

Трансплантация

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