#java #c #performance #matrix #matrix-multiplication
#java #c #Производительность #матрица #умножение матрицы
Вопрос:
Я написал коды для умножения матриц огромных размеров (например, 2000×2000) на Java и C, чтобы сравнить их как действие. Я не могу понять, почему код Java выполняется быстрее, чем код C…
Вот результаты:
Размер матрицы 1: 1000 x 500; Размер матрицы 2: 500 x 1000
Time Taken by Java : 13787 ms
Time Taken by C: 20565 ms
Размер матрицы 1: 1000 x 1000; Размер матрицы 2: 1000 x 1500
Time Taken by Java : 64636 ms
Time Taken by C: 65155 ms
Вот коды, которые я написал:
В C:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
int main()
{
// Declaring the variables
long i, j, k, m1, n1, m2, n2;
// Reading the dimensions of the matrices
printf("Enter the row dimension of the matrix 1:t "); scanf("%ld", amp;m1);
printf("Enter the column dimension of the matrix 1:t "); scanf("%ld", amp;n1);
printf("nEnter the row dimension of the matrix 2:t "); scanf("%ld", amp;m2);
printf("Enter the column dimension of the matrix 2:t "); scanf("%ld", amp;n2);
// Variables used by the clock
clock_t start, end;
double cpu_time_used;
// Necessary condition for matrix multiplication
if (n1 != m2)
{
printf("nMuliplication is not possible!n");
printf("Please check the dimensions of the matrices!nn");
}
else
{
char choice;
start = clock(); // Starts the clock
long (*mat1)[n1] = malloc(m1 * sizeof *mat1); // Storing the matrix in heap memory
if (mat1 == NULL) exit(1); // Freeing up space once matrix is NULL
long (*mat2)[n2] = malloc(m2 * sizeof *mat2);
if (mat2 == NULL) exit(1);
long (*mat3)[n2] = malloc(m1 * sizeof *mat3);
if (mat3 == NULL) exit(1);
// Generating matrix with random elements
for(i=0; i<m1; i )
for(j=0; j<n1; j )
mat1[i][j] = (long)rand()%MAX;
// Generating matrix with random elements
for(i=0; i<m2; i )
for(j=0; j<n2; j )
mat2[i][j] = (long)rand()%MAX;
printf("nMatrices Generated!n");
// Initializing the result matrix with zeroes
for(i=0; i<m1; i )
for(j=0; j<n2; j )
mat3[i][j] = 0;
// Performing mat1[m1][n1] x mat2[m2][n2] = mat3[m1][n2]
for (i = 0; i < m1; i )
for (j = 0; j < n2; j )
for (k = 0; k < m2; k )
mat3[i][j] = mat1[i][k] * mat2[k][j];
// Freeing up space occupied by the matrices after process completion
free(mat1); free(mat2); free(mat3);
end = clock(); // Stop the clock timer
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC; // Time taken by the program
printf("nMultiplication took %f milliseconds to execute.nn", cpu_time_used*1000);
}
return 0;
}
В Java:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Matrix {
private static String s;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// Reading the dimensions of matrix 1
System.out.print("Enter the row dimension of the matrix 1:t ");
int m1 = Integer.parseInt(br.readLine());
System.out.print("Enter the column dimension of the matrix 1:t ");
int n1 = Integer.parseInt(br.readLine());
// Reading the dimensions of matrix 2
System.out.print("nEnter the row dimension of the matrix 2:t ");
int m2 = Integer.parseInt(br.readLine());
System.out.print("Enter the column dimension of the matrix 2:t ");
int n2 = Integer.parseInt(br.readLine());
// Print error message if condition not satisfied
if(n1 != m2) {
System.out.println("nMuliplication is not possible!");
System.out.println("Please check the dimensions of the matrices!n");
}
else {
long start = System.currentTimeMillis();
// Declaring matrices
int[][] matrix1 = new int[m1][n1];
int[][] matrix2 = new int[m2][n2];
// Generate random matrices
generateRandom(matrix1);
generateRandom(matrix2);
System.out.println("nMatrices Generated!n");
// Performs matrix1 x matrix2 = result
int[][] result = new int[m1][n2];
for (int i = 0; i < m1; i ) {
for (int j = 0; j < n2; j ) {
for (int k = 0; k < n1; k ) {
result[i][j] = matrix1[i][k] * matrix2[k][j];
}
}
}
long end = System.currentTimeMillis();
s = "Execution time is " (end - start);
System.out.print(s " milliseconds.nn");
}
}
private static void displayMatrix(int[][] matrix) {
int r = matrix.length;
int c = matrix[0].length;
for (int i = 0; i < r; i ) {
for (int j = 0; j < c; j ) {
System.out.print(matrix[i][j] " ");
}
System.out.println();
}
}
// Generates Random Matrices
private static void generateRandom(int[][] matrix) {
int r = matrix.length;
int c = matrix[0].length;
for (int i = 0; i < r; i ) {
for (int j = 0; j < c; j ) {
// Gives numbers in range (0,10)
matrix[i][j] = (int) (Math.random() * 10);
}
}
}
}
Я запускаю их в Windows 10 с последними версиями MinGW и JDK.
Комментарии:
1. Вы не сравниваете умножение матриц. Вы сравниваете создание, генерацию, умножение и удаление матрицы. Так что это не справедливое сравнение. Сравните время только метода умножения матриц.
2. Используете ли вы
-o3?3. В коде C: вместо инициализации
mat3в цикле вы должны выделить его с помощьюcalloc. Тогда вам не нужен цикл. (и, как упоминают другие, обязательно скомпилируйте код C с помощью -O3)4. Я не буду голосовать за любой контрольный вопрос, который не говорит о том, как компилируется код. Действительно надоели вопросы от людей, которые тестируют неоптимизированный код. Дайте нам знать, как вы компилируете, и я откажусь от голосования.
5. Кроме того, вы в основном сравниваете время выделения кучи, а не фактический алгоритм. Вполне возможно, что виртуальная машина Java делает что-то умное с предварительным выделением в смежной памяти, в то время как вызовы C malloc фрагментированы. И вы не можете выполнить бенчмарк
free, потому что в Java этого нет. Для освобождения памяти в Java потребуется больше времени, но вы не знаете, когда она освободится, потому что Java использует сбор мусора.
Ответ №1:
Вы сравниваете апельсины с корзинами яблок. Вы даже учитывали, что long это может быть 64 бита, тогда как Java int — 32 бита.
Другой причиной может быть то, что вы не попросили свой компилятор C оптимизировать код. Java JIT-компилятор оптимизирует код во времени, тогда как по умолчанию GCC выполняет быструю компиляцию, создавая медленный код для упрощения отладки. Оптимизация JIT отсутствует. Никто никогда не тестирует неоптимизированный код, это все равно, что тестировать Ferrari на предельной скорости 20 миль в час.
Без каких-либо оптимизаций я получаю 3216 миллисекунд для Java, 7670 для C для матриц 1000×1000. С -O3 время выполнения C падает до 2225 мс.
Но это все равно сравнение апельсинов с корзинами яблок. После того, как я поменяю Java на use long[][] , это займет 8300 миллисекунд.
Ответ №2:
Вы должны сравнивать только часть умножения, если хотите узнать только время умножения матрицы… не его создание, генерация, умножение и удаление. Измените свой код следующим образом
Для C
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 10
int main()
{
// Declaring the variables
long i, j, k, m1, n1, m2, n2;
// Reading the dimensions of the matrices
printf("Enter the row dimension of the matrix 1:t "); scanf("%ld", amp;m1);
printf("Enter the column dimension of the matrix 1:t "); scanf("%ld", amp;n1);
printf("nEnter the row dimension of the matrix 2:t "); scanf("%ld", amp;m2);
printf("Enter the column dimension of the matrix 2:t "); scanf("%ld", amp;n2);
// Variables used by the clock
clock_t start, end;
double cpu_time_used;
// Necessary condition for matrix multiplication
if (n1 != m2)
{
printf("nMuliplication is not possible!n");
printf("Please check the dimensions of the matrices!nn");
}
else
{
char choice;
long (*mat1)[n1] = malloc(m1 * sizeof *mat1); // Storing the matrix in heap memory
if (mat1 == NULL) exit(1); // Freeing up space once matrix is NULL
long (*mat2)[n2] = malloc(m2 * sizeof *mat2);
if (mat2 == NULL) exit(1);
long (*mat3)[n2] = malloc(m1 * sizeof *mat3);
if (mat3 == NULL) exit(1);
// Generating matrix with random elements
for(i=0; i<m1; i )
for(j=0; j<n1; j )
mat1[i][j] = (long)rand()%MAX;
// Generating matrix with random elements
for(i=0; i<m2; i )
for(j=0; j<n2; j )
mat2[i][j] = (long)rand()%MAX;
printf("nMatrices Generated!n");
// Initializing the result matrix with zeroes
for(i=0; i<m1; i )
for(j=0; j<n2; j )
mat3[i][j] = 0;
start = clock(); // Starts the clock
// Performing mat1[m1][n1] x mat2[m2][n2] = mat3[m1][n2]
for (i = 0; i < m1; i )
for (j = 0; j < n2; j )
for (k = 0; k < m2; k )
mat3[i][j] = mat1[i][k] * mat2[k][j];
end = clock(); // Stop the clock timer
cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC; // Time taken by the program
printf("nMultiplication took %f milliseconds to execute.nn", cpu_time_used*1000);
// Freeing up space occupied by the matrices after process completion
free(mat1); free(mat2); free(mat3);
}
return 0;
}
Для Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Matrix {
private static String s;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// Reading the dimensions of matrix 1
System.out.print("Enter the row dimension of the matrix 1:t ");
int m1 = Integer.parseInt(br.readLine());
System.out.print("Enter the column dimension of the matrix 1:t ");
int n1 = Integer.parseInt(br.readLine());
// Reading the dimensions of matrix 2
System.out.print("nEnter the row dimension of the matrix 2:t ");
int m2 = Integer.parseInt(br.readLine());
System.out.print("Enter the column dimension of the matrix 2:t ");
int n2 = Integer.parseInt(br.readLine());
// Print error message if condition not satisfied
if(n1 != m2) {
System.out.println("nMuliplication is not possible!");
System.out.println("Please check the dimensions of the matrices!n");
}
else {
// Declaring matrices
int[][] matrix1 = new int[m1][n1];
int[][] matrix2 = new int[m2][n2];
// Generate random matrices
generateRandom(matrix1);
generateRandom(matrix2);
System.out.println("nMatrices Generated!n");
long start = System.currentTimeMillis();
// Performs matrix1 x matrix2 = result
int[][] result = new int[m1][n2];
for (int i = 0; i < m1; i ) {
for (int j = 0; j < n2; j ) {
for (int k = 0; k < n1; k ) {
result[i][j] = matrix1[i][k] * matrix2[k][j];
}
}
}
long end = System.currentTimeMillis();
s = "Execution time is " (end - start);
System.out.print(s " milliseconds.nn");
}
}
private static void displayMatrix(int[][] matrix) {
int r = matrix.length;
int c = matrix[0].length;
for (int i = 0; i < r; i ) {
for (int j = 0; j < c; j ) {
System.out.print(matrix[i][j] " ");
}
System.out.println();
}
}
// Generates Random Matrices
private static void generateRandom(int[][] matrix) {
int r = matrix.length;
int c = matrix[0].length;
for (int i = 0; i < r; i ) {
for (int j = 0; j < c; j ) {
// Gives numbers in range (0,10)
matrix[i][j] = (int) (Math.random() * 10);
}
}
}
}
Я установил время запуска и остановки только для умножения матриц
Комментарии:
1. Ну, учитывая название вопроса, этот ответ отчасти правильный. Но тогда остается один вопрос: «почему создание, генерация, умножение и удаление быстрее в java?»
2. У вас есть сочетание стека и кучи в C, но только кучи в java.
Ответ №3:
Насколько я знаю, в Java нет free (или delete ) — сборщику мусора остается «очистить», когда на объект больше не ссылаются. Когда именно это произойдет, мы не можем сказать. Следовательно, ваш Java-код работает не совсем так, как ваш C-код, поскольку C-код имеет явный free вызов. Возможно, сравнение было бы «более справедливым», если бы код C не вызывался free во время работы таймера.
Некоторые другие примечания:
-
Используйте
callocformat3и удалите цикл, который инициализируетmat3 -
Удалите все отпечатки в коде, который вы используете для измерения времени (как в C, так и в Java)
По крайней мере, для кода C вы также должны добавить несколько отпечатков результата после остановки таймера. Это делается для того, чтобы настоящий умный компилятор не оптимизировал все матричные материалы до «ничего». Но обратите внимание, что вы не сможете этого сделать, если сначала вызовете free .
Кстати: я считаю само собой разумеющимся, что вы компилируете код C с включенной оптимизацией (например, -O3) — если нет, то самое время.
Комментарии:
1. «Обязательно скомпилируйте код C с включенной оптимизацией» Давай, нам не нужно этого говорить. Это все равно, что сказать: «Убедитесь, что код скомпилирован кем-то, кто знает программирование».
2. @Lundin отчасти согласен … с другой стороны — ТАК что получаю много вопросов от пользователей, которые на самом деле не «знают программирование», а повторяются в процессе изучения программирования. В любом случае — основной смысл этого ответа заключается в том, что я считаю, что это не сравнение яблок с яблоками.