«1. Обзор
В этом уроке мы рассмотрим, как мы можем перемножить две матрицы в Java.
Так как концепция матриц изначально не существует в языке, мы реализуем ее сами, а также поработаем с несколькими библиотеками, чтобы посмотреть, как они обрабатывают умножение матриц.
В конце мы проведем небольшой сравнительный анализ различных решений, которые мы исследовали, чтобы определить самое быстрое.
2. Пример
Давайте начнем с создания примера, на который мы сможем ссылаться в этом руководстве.
Сначала представим матрицу 3×2:
Теперь представим вторую матрицу, на этот раз две строки по четыре столбца:
Затем умножение первой матрицы на вторую матрицу, что приведет к матрице 3×4:
Напоминаем, что этот результат получается путем вычисления каждой ячейки результирующей матрицы по следующей формуле:
Где r равно количество строк матрицы A, c — количество столбцов матрицы B, n — количество столбцов матрицы A, которое должно совпадать с количеством строк матрицы B.
3. Умножение матриц
3.1 . Собственная реализация
Начнем с нашей собственной реализации матриц.
Мы не будем усложнять и воспользуемся двумерными двойными массивами:
Это две матрицы нашего примера. Создадим ожидаемый в результате их умножения:
Теперь, когда все настроено, реализуем алгоритм умножения. Сначала мы создадим пустой массив результатов и пройдемся по его ячейкам, чтобы сохранить ожидаемое значение в каждой из них:
Наконец, давайте реализуем вычисление одной ячейки. Чтобы добиться этого, мы будем использовать формулу, показанную ранее в представлении примера:
Наконец, давайте проверим, соответствует ли результат алгоритма нашему ожидаемому результату:
double[][] firstMatrix = {
new double[]{1d, 5d},
new double[]{2d, 3d},
new double[]{1d, 7d}
};
double[][] secondMatrix = {
new double[]{1d, 2d, 3d, 7d},
new double[]{5d, 2d, 8d, 1d}
};3.2. EJML
double[][] expected = {
new double[]{26d, 12d, 43d, 12d},
new double[]{17d, 10d, 30d, 17d},
new double[]{36d, 16d, 59d, 14d}
};Первая библиотека, которую мы рассмотрим, это EJML, что означает эффективная библиотека Java Matrix. На момент написания этого руководства это была одна из самых последних обновленных библиотек матриц Java. Его цель — быть максимально эффективным в отношении вычислений и использования памяти.
double[][] multiplyMatrices(double[][] firstMatrix, double[][] secondMatrix) {
double[][] result = new double[firstMatrix.length][secondMatrix[0].length];
for (int row = 0; row < result.length; row++) {
for (int col = 0; col < result[row].length; col++) {
result[row][col] = multiplyMatricesCell(firstMatrix, secondMatrix, row, col);
}
}
return result;
}Нам нужно добавить зависимость к библиотеке в наш pom.xml:
double multiplyMatricesCell(double[][] firstMatrix, double[][] secondMatrix, int row, int col) {
double cell = 0;
for (int i = 0; i < secondMatrix.length; i++) {
cell += firstMatrix[row][i] * secondMatrix[i][col];
}
return cell;
}Мы будем использовать почти тот же шаблон, что и раньше: создадим две матрицы в соответствии с нашим примером и проверим, что результат их умножения — это то, что мы вычислили ранее.
double[][] actual = multiplyMatrices(firstMatrix, secondMatrix);
assertThat(actual).isEqualTo(expected);Итак, давайте создадим наши матрицы с помощью EJML. Для этого мы будем использовать класс SimpleMatrix, предлагаемый библиотекой.
Он может принимать двумерный двойной массив в качестве входных данных для своего конструктора:
А теперь давайте определим нашу ожидаемую матрицу для умножения:
<dependency>
<groupId>org.ejml</groupId>
<artifactId>ejml-all</artifactId>
<version>0.38</version>
</dependency>Теперь, когда мы все настроили, давайте посмотрим, как перемножить две матрицы вместе. Класс SimpleMatrix предлагает метод mult(), принимающий в качестве параметра другую SimpleMatrix и возвращающий произведение двух матриц:
Давайте проверим, соответствует ли полученный результат ожидаемому.
Так как SimpleMatrix не переопределяет метод equals(), мы не можем полагаться на него при проверке. Но он предлагает альтернативу: метод isIdentical(), который принимает не только еще один матричный параметр, но и двойную отказоустойчивость, чтобы игнорировать небольшие различия из-за двойной точности:
SimpleMatrix firstMatrix = new SimpleMatrix(
new double[][] {
new double[] {1d, 5d},
new double[] {2d, 3d},
new double[] {1d ,7d}
}
);
SimpleMatrix secondMatrix = new SimpleMatrix(
new double[][] {
new double[] {1d, 2d, 3d, 7d},
new double[] {5d, 2d, 8d, 1d}
}
);Это завершает умножение матриц с помощью библиотеки EJML. Посмотрим, что предлагают другие.
SimpleMatrix expected = new SimpleMatrix(
new double[][] {
new double[] {26d, 12d, 43d, 12d},
new double[] {17d, 10d, 30d, 17d},
new double[] {36d, 16d, 59d, 14d}
}
);3.3. ND4J
SimpleMatrix actual = firstMatrix.mult(secondMatrix);Теперь попробуем библиотеку ND4J. ND4J — это вычислительная библиотека, являющаяся частью проекта deeplearning4j. Помимо прочего, ND4J предлагает функции вычисления матриц.
Прежде всего, мы должны получить зависимость библиотеки:
assertThat(actual).matches(m -> m.isIdentical(expected, 0d));Обратите внимание, что мы используем здесь бета-версию, потому что в выпуске GA есть некоторые ошибки.
«Для краткости мы не будем переписывать двухмерные двойные массивы, а просто сосредоточимся на том, как они используются с каждой библиотекой. Таким образом, с ND4J мы должны создать INDArray. Для этого мы вызовем фабричный метод Nd4j.create() и передадим ему двойной массив, представляющий нашу матрицу:
Как и в предыдущем разделе, мы создадим три матрицы: две мы собираемся умножить вместе и тот, который является ожидаемым результатом.
После этого мы хотим выполнить умножение между первыми двумя матрицами, используя метод INDArray.mmul():
<dependency>
<groupId>org.nd4j</groupId>
<artifactId>nd4j-native</artifactId>
<version>1.0.0-beta4</version>
</dependency>Затем мы снова проверяем, соответствует ли фактический результат ожидаемому. На этот раз мы можем положиться на проверку на равенство:
Это демонстрирует, как можно использовать библиотеку ND4J для выполнения матричных вычислений.
INDArray matrix = Nd4j.create(/* a two dimensions double array */);3.4. Apache Commons
Давайте теперь поговорим о модуле Apache Commons Math3, который предоставляет нам математические вычисления, включая манипуляции с матрицами.
INDArray actual = firstMatrix.mmul(secondMatrix);Опять же, нам нужно указать зависимость в нашем pom.xml:
assertThat(actual).isEqualTo(expected);После настройки мы можем использовать интерфейс RealMatrix и его реализацию Array2DRowRealMatrix для создания наших обычных матриц. Конструктор класса реализации принимает в качестве параметра двумерный двойной массив:
Что касается умножения матриц, интерфейс RealMatrix предлагает методmulti(), принимающий другой параметр RealMatrix:
Мы можем Наконец убедитесь, что результат соответствует ожидаемому:
Давайте посмотрим на следующую библиотеку!
<dependency>
<groupId>org.apache.commons</groupId>
<artifactId>commons-math3</artifactId>
<version>3.6.1</version>
</dependency>3.5. LA4J
RealMatrix matrix = new Array2DRowRealMatrix(/* a two dimensions double array */);Этот называется LA4J, что означает Linear Algebra for Java.
RealMatrix actual = firstMatrix.multiply(secondMatrix);Давайте добавим зависимость и для этой:
assertThat(actual).isEqualTo(expected);Теперь LA4J работает почти так же, как и другие библиотеки. Он предлагает интерфейс Matrix с реализацией Basic2DMatrix, которая принимает двумерный двойной массив в качестве входных данных:
Как и в модуле Apache Commons Math3, метод умножения — умножить() и принимает другую матрицу в качестве параметра: ~ ~~
Еще раз проверим, соответствует ли результат нашим ожиданиям:
Теперь посмотрим на нашу последнюю библиотеку: Colt.
<dependency>
<groupId>org.la4j</groupId>
<artifactId>la4j</artifactId>
<version>0.6.0</version>
</dependency>3.6. Colt
Matrix matrix = new Basic2DMatrix(/* a two dimensions double array */);Colt — это библиотека, разработанная CERN. Он предоставляет функции, обеспечивающие высокую производительность научных и технических вычислений.
Matrix actual = firstMatrix.multiply(secondMatrix);Как и в случае с предыдущими библиотеками, мы должны получить правильную зависимость:
assertThat(actual).isEqualTo(expected);Чтобы создавать матрицы с помощью Colt, мы должны использовать класс DoubleFactory2D. Он поставляется с тремя фабричными экземплярами: плотным, разреженным и rowCompressed. Каждый из них оптимизирован для создания соответствующей матрицы.
Для наших целей мы будем использовать плотный экземпляр. На этот раз вызывается метод make(), и он снова принимает двумерный массив double, создавая объект DoubleMatrix2D:
После создания экземпляров наших матриц мы хотим их умножить. На этот раз для матричного объекта нет метода для этого. Нам нужно создать экземпляр класса Algebra, у которого есть метод mult(), принимающий две матрицы в качестве параметров:
Затем мы можем сравнить фактический результат с ожидаемым:
<dependency>
<groupId>colt</groupId>
<artifactId>colt</artifactId>
<version>1.2.0</version>
</dependency>4. Бенчмаркинг
Теперь, когда мы закончили изучение различных возможностей умножения матриц, давайте проверим, какие из них наиболее эффективны.
DoubleMatrix2D matrix = doubleFactory2D.make(/* a two dimensions double array */);4.1. Маленькие матрицы
Algebra algebra = new Algebra();
DoubleMatrix2D actual = algebra.mult(firstMatrix, secondMatrix);Начнем с маленьких матриц. Здесь матрицы 3×2 и 2×4.
assertThat(actual).isEqualTo(expected);Для проведения теста производительности мы воспользуемся бенчмаркинговой библиотекой JMH. Давайте настроим класс бенчмаркинга со следующими параметрами:
Таким образом, JMH выполнит два полных прогона для каждого метода, аннотированного @Benchmark, каждый с пятью прогревочными итерациями (не учитываемыми при расчете среднего) и десятью замерами. . Что касается измерений, то они будут собирать среднее время выполнения различных библиотек в микросекундах.
Затем мы должны создать объект состояния, содержащий наши массивы:
«
«Таким образом, мы гарантируем, что инициализация массивов не является частью бенчмаркинга. После этого нам еще нужно создать методы, выполняющие умножение матриц, используя объект MatrixProvider в качестве источника данных. Мы не будем повторять здесь код, так как мы видели каждую библиотеку ранее.
public static void main(String[] args) throws Exception {
Options opt = new OptionsBuilder()
.include(MatrixMultiplicationBenchmarking.class.getSimpleName())
.mode(Mode.AverageTime)
.forks(2)
.warmupIterations(5)
.measurementIterations(10)
.timeUnit(TimeUnit.MICROSECONDS)
.build();
new Runner(opt).run();
}Наконец, мы запустим процесс бенчмаркинга, используя наш основной метод. Это дает нам следующий результат:
Как мы видим, EJML и Colt очень хорошо работают с примерно одной пятой микросекунды на операцию, тогда как ND4j менее эффективен с чуть более чем десятью микросекундами на операцию. В других библиотеках спектакли проходят между ними.
@State(Scope.Benchmark)
public class MatrixProvider {
private double[][] firstMatrix;
private double[][] secondMatrix;
public MatrixProvider() {
firstMatrix =
new double[][] {
new double[] {1d, 5d},
new double[] {2d, 3d},
new double[] {1d ,7d}
};
secondMatrix =
new double[][] {
new double[] {1d, 2d, 3d, 7d},
new double[] {5d, 2d, 8d, 1d}
};
}
}Также стоит отметить, что при увеличении количества итераций прогрева с 5 до 10 производительность увеличивается для всех библиотек.
4.2. Большие матрицы
Benchmark Mode Cnt Score Error Units
MatrixMultiplicationBenchmarking.apacheCommonsMatrixMultiplication avgt 20 1,008 ± 0,032 us/op
MatrixMultiplicationBenchmarking.coltMatrixMultiplication avgt 20 0,219 ± 0,014 us/op
MatrixMultiplicationBenchmarking.ejmlMatrixMultiplication avgt 20 0,226 ± 0,013 us/op
MatrixMultiplicationBenchmarking.homemadeMatrixMultiplication avgt 20 0,389 ± 0,045 us/op
MatrixMultiplicationBenchmarking.la4jMatrixMultiplication avgt 20 0,427 ± 0,016 us/op
MatrixMultiplicationBenchmarking.nd4jMatrixMultiplication avgt 20 12,670 ± 2,582 us/opЧто произойдет, если мы возьмем матрицы большего размера, например 3000×3000? Чтобы проверить, что происходит, давайте сначала создадим еще один класс состояния, предоставляющий сгенерированные матрицы такого размера:
Как мы видим, мы создадим 3000×3000 двумерных двойных массивов, заполненных случайными действительными числами.
Теперь создадим класс бенчмаркинга:
Когда мы запустим этот бенчмаркинг, мы получим совершенно другие результаты:
@State(Scope.Benchmark)
public class BigMatrixProvider {
private double[][] firstMatrix;
private double[][] secondMatrix;
public BigMatrixProvider() {}
@Setup
public void setup(BenchmarkParams parameters) {
firstMatrix = createMatrix();
secondMatrix = createMatrix();
}
private double[][] createMatrix() {
Random random = new Random();
double[][] result = new double[3000][3000];
for (int row = 0; row < result.length; row++) {
for (int col = 0; col < result[row].length; col++) {
result[row][col] = random.nextDouble();
}
}
return result;
}
}Как мы видим, самодельные реализации и библиотека Apache теперь намного хуже чем раньше, на умножение двух матриц ушло почти 10 минут.
Кольт занимает чуть больше 3 минут, что лучше, но все равно очень долго. EJML и LA4J работают довольно хорошо, поскольку выполняются почти за 30 секунд. Но именно ND4J выигрывает этот бенчмаркинг, работая менее чем за секунду на бэкенде ЦП.
public class BigMatrixMultiplicationBenchmarking {
public static void main(String[] args) throws Exception {
Map<String, String> parameters = parseParameters(args);
ChainedOptionsBuilder builder = new OptionsBuilder()
.include(BigMatrixMultiplicationBenchmarking.class.getSimpleName())
.mode(Mode.AverageTime)
.forks(2)
.warmupIterations(10)
.measurementIterations(10)
.timeUnit(TimeUnit.SECONDS);
new Runner(builder.build()).run();
}
@Benchmark
public Object homemadeMatrixMultiplication(BigMatrixProvider matrixProvider) {
return HomemadeMatrix
.multiplyMatrices(matrixProvider.getFirstMatrix(), matrixProvider.getSecondMatrix());
}
@Benchmark
public Object ejmlMatrixMultiplication(BigMatrixProvider matrixProvider) {
SimpleMatrix firstMatrix = new SimpleMatrix(matrixProvider.getFirstMatrix());
SimpleMatrix secondMatrix = new SimpleMatrix(matrixProvider.getSecondMatrix());
return firstMatrix.mult(secondMatrix);
}
@Benchmark
public Object apacheCommonsMatrixMultiplication(BigMatrixProvider matrixProvider) {
RealMatrix firstMatrix = new Array2DRowRealMatrix(matrixProvider.getFirstMatrix());
RealMatrix secondMatrix = new Array2DRowRealMatrix(matrixProvider.getSecondMatrix());
return firstMatrix.multiply(secondMatrix);
}
@Benchmark
public Object la4jMatrixMultiplication(BigMatrixProvider matrixProvider) {
Matrix firstMatrix = new Basic2DMatrix(matrixProvider.getFirstMatrix());
Matrix secondMatrix = new Basic2DMatrix(matrixProvider.getSecondMatrix());
return firstMatrix.multiply(secondMatrix);
}
@Benchmark
public Object nd4jMatrixMultiplication(BigMatrixProvider matrixProvider) {
INDArray firstMatrix = Nd4j.create(matrixProvider.getFirstMatrix());
INDArray secondMatrix = Nd4j.create(matrixProvider.getSecondMatrix());
return firstMatrix.mmul(secondMatrix);
}
@Benchmark
public Object coltMatrixMultiplication(BigMatrixProvider matrixProvider) {
DoubleFactory2D doubleFactory2D = DoubleFactory2D.dense;
DoubleMatrix2D firstMatrix = doubleFactory2D.make(matrixProvider.getFirstMatrix());
DoubleMatrix2D secondMatrix = doubleFactory2D.make(matrixProvider.getSecondMatrix());
Algebra algebra = new Algebra();
return algebra.mult(firstMatrix, secondMatrix);
}
}4.3. Анализ
Benchmark Mode Cnt Score Error Units
BigMatrixMultiplicationBenchmarking.apacheCommonsMatrixMultiplication avgt 20 511.140 ± 13.535 s/op
BigMatrixMultiplicationBenchmarking.coltMatrixMultiplication avgt 20 197.914 ± 2.453 s/op
BigMatrixMultiplicationBenchmarking.ejmlMatrixMultiplication avgt 20 25.830 ± 0.059 s/op
BigMatrixMultiplicationBenchmarking.homemadeMatrixMultiplication avgt 20 497.493 ± 2.121 s/op
BigMatrixMultiplicationBenchmarking.la4jMatrixMultiplication avgt 20 35.523 ± 0.102 s/op
BigMatrixMultiplicationBenchmarking.nd4jMatrixMultiplication avgt 20 0.548 ± 0.006 s/opЭто показывает нам, что результаты бенчмаркинга действительно зависят от характеристик матриц, и поэтому сложно выделить единственного победителя.
5. Заключение
В этой статье мы научились перемножать матрицы в Java самостоятельно или с помощью внешних библиотек. Изучив все решения, мы провели бенчмарк всех из них и увидели, что все они, за исключением ND4J, неплохо показали себя на небольших матрицах. С другой стороны, на больших матрицах лидирует ND4J.
Как обычно, полный код этой статьи можно найти на GitHub.
«
In this article, we’ve learned how to multiply matrices in Java, either by ourselves or with external libraries. After exploring all solutions, we did a benchmark of all of them and saw that, except for ND4J, they all performed pretty well on small matrices. On the other hand, on larger matrices, ND4J is taking the lead.
As usual, the full code for this article can be found over on GitHub.