Матрица (программирование)
Массив (в некоторых языках программирования также таблица, ряд, матрица, вектор) — структура данных, хранящая набор значений (элементов массива), идентифицируемых по индексу или набору индексов, принимающих целые (или приводимые к целым) значения из некоторого заданного непрерывного диапазона. Одномерный массив можно рассматривать как реализацию абстрактного типа данных — вектор.
В простейшем случае массив имеет константную длину по всем размерностям и может хранить данные только одного, заданного при описании, типа. Ряд языков поддерживает также динамические массивы, длина которых может изменяться по ходу работы программы, и гетерогенные массивы, которые могут в разных элементах хранить данные различных типов.
Содержание
Общее описание
Массив — упорядоченный набор элементов, каждый из которых хранит одно значение, идентифицируемое с помощью одного или нескольких индексов. В простейшем случае массив имеет постоянную длину и хранит единицы данных одного и того же типа, а в качестве индексов выступают целые числа.
Количество используемых индексов массива может быть различным: массивы с одним индексом называют одномерными, с двумя — двумерными, и т. д. Одномерный массив — нестрого соответствует вектору в математике; двумерный («строка», «столбец»)— матрице. Чаще всего применяются массивы с одним или двумя индексами; реже — с тремя; ещё большее количество индексов — встречается крайне редко.
Пример фиксированного массива на языке Паскаль
Пример двумерного массива на JavaScript
Поддержка индексных массивов (свой синтаксис объявления, функции для работы с элементами и т. д.) есть в большинстве высокоуровневых языков программирования. Максимально допустимая размерность массива, типы и диапазоны значений индексов, ограничения на типы элементов определяются языком программирования и (или) конкретным транслятором.
В языках программирования, допускающих объявления программистом собственных типов, как правило, существует возможность создания типа «массив». В определении такого типа задаются типы и/или диапазоны значений каждого из индексов и тип элементов массива. Объявленный тип в дальнейшем может использоваться для определения переменных, формальных параметров и возвращаемых значений функций. Некоторые языки поддерживают для переменных-массивов операции присваивания (когда одной операцией всем элементам массива присваиваются значения соответствующих элементов другого массива).
Объявление типа «массив» в языке Паскаль
Специфические типы массивов
Динамические массивы
Динамическими называются массивы, размер которых может изменяться во время выполнения программы. Обычные (не динамические) массивы называют ещё фиксированными или статическими.
Динамические массивы могут реализовываться как на уровне языка программирования, так и на уровне системных библиотек. Во втором случае динамический массив представляет собой объект стандартной библиотеки, и все операции с ним реализуются в рамках той же библиотеки. Так или иначе, поддержка динамических массивов предполагает наличие следующих возможностей:
Ниже приведён пример конструкций для работы с динамическими массивами на Delphi.
Гетерогенные массивы
Гетерогенным называется массив, в разные элементы которого могут быть непосредственно записаны значения, относящиеся к различным типам данных. Массив, хранящий указатели на значения различных типов, не является гетерогенным, так как собственно хранящиеся в массиве данные относятся к единственному типу — типу «указатель». Гетерогенные массивы удобны как универсальная структура для хранения наборов данных произвольных типов. Реализация гетерогенности требует усложнения механизма поддержки массивов в трансляторе языка.
Реализация
Типовым способом реализации статического гомогенного (хранящего данные одного типа) массива является следующий:
Таким образом, адрес элемента с заданным набором индексов вычисляется так, что время доступа ко всем элементам массива одинаково. (Здесь одинаковость времени доступа следует понимать как отсутствие теоретической зависимости времени доступа от положения элемента и размера массива. В действительности особенности конкретной вычислительной платформы могут дать определённый разброс времени доступа. Например, CAS-латентность ОЗУ приводит к увеличению времени доступа к данным, расположенным в другой колонке (странице) ОЗУ, по отношению к предыдущим считанным данным. В практике высокоуровневого программирования такими тонкостями, за редчайшими исключениями, пренебрегают.)
Первый элемент массива, в зависимости от языка программирования, может иметь различный индекс. Различают три основных разновидности массивов: с отсчетом от нуля (zero-based), с отсчетом от единицы (one-based) и с отсчетом от специфического значения заданного программистом (n-based). Отсчет индекса элемента массивов с нуля более характерен для низкоуровневых языков программирования, хотя встречается и в языках высокого уровня, например, в том же Си. В ряде языков (Паскаль, Ада, Модула-2) диапазон индексов может определяться как произвольный диапазон значений любого типа данных, приводимого к целому, то есть целых чисел, символов, перечислений, даже логического типа (в последнем случае массив имеет два элемента, индексируемых значениями «Истина» и «Ложь»).
Обычным способом реализации гетерогенных массивов является отдельное хранение самих значений элементов и размещение в блоке памяти массива (организованного как обычный гомогенный массив, описанный выше) указателей на эти элементы. Поскольку указатели на значения любых типов, как правило, имеют один и тот же размер, удаётся сохранить простоту вычисления адреса, хотя возникают дополнительные накладные расходы на размещение значений элементов и обращение к ним.
Для динамических массивов может использоваться тот же механизм размещения, что и для статических, но с выделением некоторого объёма дополнительной памяти для расширения и добавлении механизмов изменения размера и перемещения содержимого массива в памяти.
Также динамические и гетерогенные массивы могут реализовываться путём использования принципиально иных методов хранения значений в памяти, например, одно- или двухсвязных списков. Такие реализации могут быть более гибкими, но требуют, как правило, дополнительных накладных расходов. Кроме того, в них обычно не удаётся выдержать требование константного времени доступа к элементу.
ЧАВО по матрицам и кватернионам
Часто задаваемые вопросы по матрицам и кватернионам.
Введение
Замечание по поводу OpenGL и этого документа
В этом документе, как в большинстве книг по математике, все матрицы представлены в стандартном математическом виде. К сожалению, в уроках и документах по использованию графических библиотек типа IrisGL, OpenGL используют представление, в котором изменены местами столбцы и строки.
В этом документе, к примеру, матрица переноса 4×4 записывается в таком виде:
\(M = \begin
В коде это можно записать вот так:
OpenGL использует одномерный массив для хранения матриц, но, к счастью, они находятся в памяти в таком виде, что получив адрес pfMatrix и скастовав его к float* можно увидеть матрицу в том виде, в каком ее передают в glLoadMatrixf.
Во фрагментах кода в этом документе используются одномерные массивы для хранения матриц. Порядок элементов в них транспонирован как в OpenGL.
| Этот документ | OpenGL |
| \(M = \begin | \(M = \begin |
Что такое матрица?
Матрица это двумерный массив чисел, где каждый ряд или колонка состоит из одного и более чисел.
Матрицы можно складывать, вычитать, умножать и делить.
Размер матрицы определяется количеством рядов и колонок.
Матрица с M рядов и N колонок описывается как матрица MxN.
Описать отдельный элемент матрицы можно в виде двух индексов.
Используя математическую нотацию индексы обозначают переменными i и j. Сначала пишут строку, затем колонку.
К примеру, если есть матрица M с порядком 4×4, то элементы этой матрицы описываются парами индексов строк и колонок:
\(M = \begin
У верхнего правого элемента матрицы i=0 и j=3, что можно описать так:
\(M_
В компьютерной анимации обычно используют матрицы 2×2, 3×3 и 4×4.
Матрицы 2×2 используются для двумерного пространства, например, для поворотов, сдвигов и других типов обработки изображений.
Матрицы 3×3 достаточны для хранения информации о повороте (вращении) и масшатбировании. Такие матрицы могут быть использованы для скелетной анимации.
Матрицы 4×3 достаточно, чтобы хранить поворот, масштабирование и перемещение.
Матрицы 4×4 используются для всего набора трансформаций в трёхмерном пространстве, включая перспективное проецирование.
Что такое порядок матрицы?
Порядок матрицы — это её размерность. Матрица из M строк и N столбцов имеет порядок MxN.
Как я могу сделать матрицу в C/C++?
Проще всего использовать ключевое слово typedef.
Матрицы 3×3 и 4×4 могут быть описаны так:
Так как матрицы имеют размерность 3×3 и 4×4, им необходимо 9 и 16 элементов соответственно.
На первый взгляд, использование одного линейного массива чисел может показаться не интуитивным. Использование двумерного массива кажется логичнее:
Однако, использование двух систем отсчета для каждого элемента матрицы часто ведет к путанице. В математике, сначала записывают строку(i), а затем колонку(j): \(M_
В C/C++, это будет так:
Использование двумерных массивов также подействует на производительность процессора, так как компилятор C всегда использует операцию умножения для определения индекса элемента.
Так что, эффективнее использовать одномерные массивы. Однако останется решить ещё один вопрос. Как двумерный массив проецируется в линейный?
Есть только два решения: строка сначала, колонка потом, либо колонка сначала, а строка потом.
Разница в производительности минимальна. Если все циклы раскрыты, то нет практически отличий в производительности для таких операций как умножение матрицы на матрицу.
При использовании C/C++ порядок элементов в матрице следующий:
| \(M = \begin | \(M = \begin |
В чем плюсы от использования матриц?
Один из первых вопросов, задаваемых по использованию матриц в компьютерной анимации: «Зачем вообще они нужны?». Интуиция подсказывает, что придется хорошо потратиться на циклы, и тем самым матричные перемножения замедлят программу.
Решением этой проблемы, являются регистры процессора и процессорный кэш. Первый может быть счетчиком в цикле, а алгоритм предсказания с заполнением кэша позволит оптимизировать доступ к памяти.
Также можно указать и на плюсы. Используя этот математический подход в описании 3D алгоритмов, можно предсказать и спланировать систему 3D анимации. Этот подход позволяет реализовать анимацию персонажа, сплайны и инверсную кинематику.
Но чаще всего звучит такой вопрос: «А не будет ли быстрее, просто умножить каждую пару координат на коэффициенты поворота для оси, вместо того чтобы производить полное векторно-матричное умножение?»
иначе говоря:
Вращение в X преобразует Y и Z
Вращение в Y преобразует X и Z
Вращение в Z преобразует X и Y
За это приводятся следующие аргументы:
Дана вершина V = (x, y, z), углы поворота (A,B и C) и перенос (D,E,F).
И следующий алгоритм:
Вместе они займут следующее количество процессорного времени:
| Настройка | На одну вершину |
| 6 тригонометрических функций 6 присваиваний. | 12 присваиваний 12 умножений 9 сложений |
Те же самые операции, но при использовании матричного умножения.
С матрицей 4х4 они займут:
| Настройка | Изменение | На одну вершину | Изменение |
| 6 тригонометрических функций | 0 | 0 | |
| 18 присваиваний | -12 | 3 присваиваний | -9 |
| 12 умножений | +12 | 9 умножений | -3 |
| 6 вычитаний | +6 | 6 сложений | -3 |
Сравнивая две таблицы, видно, что матрица поворота стоит как минимум 12 умножений и дополнительно 18 присваиваний.
Однако мы экономим на обработке вершин. Использование матричного умножения, от настройки всего 4 вершин, перевесит дополнительные затраты на настройке.
Как матрицы влияют на систему координат?
Матрицы поворота, переноса, сдвига очень просто действуют на систему координат.
Первые три колонки матрицы описывают направление осей X,Y,Z соответственно.
Если описана матрица 4х4 как:
\(M = \begin
Вектор направления для каждой оси будет следующий:
ось \(X = [ A E I]\)
ось \(Y = [ B F J ]\)
ось \(Z = [ C G K]\)
Математические операции над массивами и матрицами
May 31 · 4 min read
В процессе обработки и организации данных в определенные моменты возникает необходимость в выполнении математических операций над массивами и матрицами.
Заглянем в notebook
Чтобы ознакомиться с рассматриваемыми далее понятиями о математических операциях над массивами и матрицами в NumPy, загляните на страницу с Jupyter Notebook. Обратите внимание: для облегчения понимания важные функции, результаты выполнения и термины выделены жирным шрифтом.
Первым делом разберемся в различиях между массивами и матрицами в NumPy, где эти понятия рассматриваются немного по-разному.
Массив NumPy
Массивы NumPy — это многомерные объекты с размерностью N.
Матрицы NumPy
Матрицы NumPy — это д вумерные объекты. По сути, это те же массивы. Но есть массивы с размерностью 3, 4, 5 и т. д., а матрицы представляют собой массивы с размерностью 2.
Математически понятия остались неизменными — в практических и организационных целях разработчики NumPy лишь разделили методы и атрибуты, характерные для объектов- массивов, от тех, что характерны для объектов- матриц. Отметим также, что в операциях линейной алгебры над массивами и матрицами имеются некоторые различия, которые мы позже разберем.
Многие функции в NumPy в качестве получаемого в результате объекта возвращают массивы, а не матрицы. И не забывайте проверять тип объекта. Итак, начнем.
Загрузка пакетов
Создание матрицы 1
Проверка типа
Имеем объект-матрицу NumPy (матрицу NumPy), созданную с помощью функции matrix :
Создание матрицы 2
Другой метод создания матриц — список списков. Внутри этого списка еще два списка значений.
Создание матрицы 3
С помощью матричной функции создается также матрица со множеством строк и столбцов. При том, что NumPy выделяет создание такой матрицы в отдельную операцию, многомерный объект представляется все так же в виде массива:
Проверка типа
Получение среза матрицы
Кроме того, получают срез матрицы (не забывая, что индексация в Python начинается с 0):
Математические операции
Переходим к выполнению математических операций над массивами и матрицами.
Создание массива
Умножение массивов
Один массив умножается на другой:
Проверка типа
Преобразование массива в матрицу
Обратите внимание: объекты-массивы и объекты-матрицы практически одинаковы. Математически это одно и то же, но у нас для каждого из них есть методы и атрибуты.
Проверка типа
Умножение матриц
Матрицы тоже перемножаются друг с другом:
Почему результаты перемножения массивов и матриц отличаются?
При перемножении массивов происходит непосредственное умножение, т. е. элемент первого массива умножается на соответствующий элемент второго.
Скалярное произведение
При перемножении матриц происходит умножение каждого элемента строки первой матрицы на каждый элемент столбца второй матрицы с суммированием получаемого результата, затем следующий элемент строки первого массива умножается на следующий элемент столбца второго массива и т. д. То есть получаем операцию умножения строки * столбцы:
Этот метод, называющийся скалярным произведением, широко применяется в искусственных нейронных сетях, машинном обучении и искусственном интеллекте, причем практически везде это умножение матриц.
Тем не менее в NumPy выполняется и скалярное произведение массивов. Происходит оно так же, как обычное их умножение:
Скалярное произведение массивов
Мы получили тот же результат, что и при перемножении матриц:
Преобразование массива в матрицу
Массив в матрицу преобразовывается так:
Здесь мы воспользовались возможностью преобразования и перемножения матриц — скалярным произведением.
Преобразование матрицы в массив
Преобразуем матрицы в массивы и выполним операции над новым объектом.
Обратите внимание: результат операции приводит к умножению массивов на их соответствующие элементы.
Редко где в Интернете найдешь столь простое объяснение. Ведь для понимания этих различий требуются кое-какие математические знания.
От действий над матрицами к пониманию их сути…
Очень уважаю людей, которые имеют смелость заявить, что они что-то не понимают. Сам такой. То, что не понимаю, — обязательно должен изучить, осмыслить, понять. Статья «Математика на пальцах», и особенно матричная запись формул, заставили меня поделиться своим небольшим, но, кажется, немаловажным опытом работы с матрицами.
Лет эдак 20 назад довелось мне изучать высшую математику в вузе, и начинали мы с матриц (пожалуй, как и все студенты того времени). Почему-то считается, что матрицы — самая лёгкая тема в курсе высшей математики. Возможно — потому, что все действия с матрицами сводятся к знанию способов расчёта определителя и нескольких формул, построенных — опять же, на определителе. Казалось бы, всё просто. Но… Попробуйте ответить на элементарный вопрос — что такое определитель, что означает число, которое вы получаете при его расчёте? (подсказка: вариант типа «определитель — это число, которое находится по определённым правилам» не является правильным ответом, поскольку говорит о методе получения, а не о самой сути определителя). Сдаётесь? — тогда читаем дальше.
Сразу хочу сказать, что я не математик ни по образованию, ни по должности. Разве что мне интересна суть вещей, и я порой пытаюсь до них «докопаться». Так же было и с определителем: нужно было разобраться со множественной регрессией, а в этом разделе эконометрики практически всё делается через… матрицы, будь они неладны. Вот и пришлось мне самому провести небольшое исследование, поскольку ни один из знакомых математиков не дал внятного ответа на поставленный вопрос, изначально звучавший как «что такое определитель». Все утверждали, что определитель — это такое число, которое особым образом посчитано, и если оно равно нулю, то… В общем, как в любом учебнике по линейной алгебре. Спасибо, проходили.
Если какую-то идею придумал один человек, то другой человек должен быть в состоянии её понять (правда, для этого порой приходится вооружаться дополнительными знаниями). Обращение к «великому и могучему» поисковику показало, что «площадь параллелограмма равна модулю определителя матрицы, образованной векторами — сторонами параллелограмма». Говоря простым языком, если матрица — это способ записи системы уравнений, то каждое уравнение в отдельности описывает вектор. Построив из точки начала координат векторы, заданные в матрице, мы таким образом зададим в пространстве некоторую фигуру. Если наше пространство одномерное, то фигура — это отрезок; если двумерное — то фигура — параллелограмм, и так далее.
Получается, что для одномерного пространства определитель — это длина отрезка, для плоскости — площадь фигуры, для трёхмерной фигуры — её объём… дальше идут n-мерные пространства, вообразить которые нам не дано. Если объём фигуры (то есть определитель для матрицы 3*3) равен нулю, то это означает, что сама фигура не является трёхмерной (она может быть при этом двухмерной, одномерной или вообще представлять собой точку). Ранг матрицы — это истинная (максимальная) размерность пространства, для которого определитель не равен нулю.
Так, с определителем почти всё понятно: он определяет «объёмность» фигуры, образованной описанными системой уравнений векторами (хотя непонятно, почему его значение не зависит от того, имеем мы дело с исходной матрицей, или с транспонированной — возможно, транспонирование — это вид аффинного преобразования?). Теперь нужно разобраться с действиями над матрицами…
Если матрица — это система уравнений (а иначе зачем нам таблица каких-то цифр, не имеющих к реальности никакого отношения?), то мы можем с ней делать разные вещи. Например, можем сложить две строки одной и той же матрицы, или умножить строку на число (то есть каждый коэффициент строки умножаем на одно и то же число). Если у нас есть две матрицы с одинаковыми размерностями, то мы их можем сложить (главное, чтобы при этом мы не сложили бульдога с носорогом — но разве математики, разрабатывая теорию матриц, думали о таком варианте развития событий?). Интуитивно понятно, тем более что в линейной алгебре иллюстрациями подобных операций являются системы уравнений.
Однако в чём смысл умножения матриц? Как я могу умножить одну систему уравнений на другую? Какой смысл будет иметь то, что я получу в этом случае? Почему для умножения матриц неприменимо переместительное правило (то есть произведение матриц В*А не то что не равно произведению А*В, но и не всегда осуществимо)? Почему, если мы перемножим матрицу на вектор-столбец, то получим вектор-столбец, а если перемножим вектор-строку на матрицу, то получим вектор-строку?
Ну, тут уж не то что Википедия, — тут даже современные учебники по линейной алгебре бессильны дать какое-либо внятное объяснение. Поскольку изучение чего-либо по принципу «вы сначала поверьте — а поймёте потом» — не для меня, копаю в глубь веков (точнее — читаю учебники первой половины XX века) и нахожу интересную фразу…
Если совокупность обычных векторов, т.е. направленных геометрических отрезков, является трёхмерным пространством, то часть этого пространства, состоящая из векторов, параллельных некоторой плоскости, является двумерным пространством, а все векторы, параллельные некоторой прямой, образуют одномерное векторное пространство.
В книгах об этом напрямую не говорится, но получается, что векторам, параллельным некоторой плоскости, необязательно лежать на этой плоскости. То есть они могут находиться в трёхмерном пространстве где угодно, но если они параллельны именно этой плоскости, то они образуют двумерное пространство… Из приходящих мне на ум аналогий — фотография: трёхмерный мир представлен на плоскости, при этом вектору, параллельному матрице (или плёнке) фотоаппарата, будет соответствовать такой же вектор на картинке (при условии соблюдении масштаба 1:1). Отображение трёхмерного мира на плоскости «убирает» одно измерение («глубину» картинки). Если я правильно понял сложные математические концепции, перемножение двух матриц как раз и представляет собой подобное отражение одного пространства в другом. Поэтому, если отражение пространства А в пространстве В возможно, то допустимость отражения пространства В в пространстве А — не гарантируется.
Любая статья заканчивается в тот момент, когда автору надоедает её писать. Поскольку я не ставил перед собой цели объять необъятное, а исключительно хотел понять суть описанных операций над матрицами и то, как именно матрицы связаны с решаемыми мной системами уравнений, я не полез в дальнейшие дебри линейной алгебры, а вернулся к эконометрике и множественной регрессии, но сделал это уже более осознанно. Понимая, что и зачем я делаю и почему только так, а не иначе. То, что у меня получилось в этом материале, можно озаглавить как «глава о сути основных операций линейной алгебры, которую почему-то забыли напечатать в учебниках». Но ведь мы же не читаем учебников, правда? Если честно, когда я учился в университете, мне очень не хватало именно понимания затронутых здесь вопросов, поэтому я надеюсь, что, изложив этот непростой материал по возможности простыми словами, я делаю доброе дело и помогаю кому-то вникнуть в саму суть матричной алгебры, переведя операции над матрицами из раздела «камлание с бубном» в раздел «практические инструменты, применяемые осознанно».