Comparaison de vitesse de Python, Java, C ++
Comparaison de vitesse de Python, Java, C ++
introduction
Au départ, j'étudiais principalement Python, mais depuis que j'ai commencé à étudier Java et C ++ cette semaine, j'ai décidé de comparer la vitesse d'exécution.
J'ai sélectionné un problème DP avec une grande quantité de calculs d'AtCoder et l'ai soumis avec presque le même algorithme.
question 1
Concours pédagogique DP / Récapitulatif DP Concours L Problème --Deque
Python
DP.py
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = a[i]
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
print(dp[0][n - 1])
Vitesse d'exécution: TLE </ font> </ B>
C'est une solution simple, mais en Python, le délai est dépassé et je ne peux pas me rendre en AC.
PyPy
DP.py
n = int(input())
a = list(map(int, input().split()))
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = a[i]
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])
print(dp[0][n - 1])
Vitesse d'exécution: 324ms </ B> </ font>
Le code est exactement le même, mais si vous le soumettez avec PyPy, il passera. Vous devez bien utiliser PyPy et NumPy pour vous battre en Python dans la programmation compétitive.
Java
Main.java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i=0; i<n; i++) {
a[i] = sc.nextInt();
}
long[][] dp = new long[n][n];
for (int i=0; i<n; i++) {
dp[i][i] = a[i];
}
for (int i = n - 2; i > -1; i--) {
for (int j = i + 1; j < n; j++) {
dp[i][j] = Math.max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1]);
}
}
System.out.println(dp[0][n - 1]);
}
}
Vitesse d'exécution: 258ms </ B> </ font>
Vous faites la même chose, mais le code est beaucoup plus long que Python. Est-ce aussi rapide que PyPy?
C++
main.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; ++i)
int main() {
int n; cin >> n;
vector<long long> a(n);
rep(i, n) cin >> a[i];
long long dp[n][n];
rep(i, n) dp[i][i] = a[i];
for (int i = n - 2; i > -1; --i) {
for (int j = i + 1; j < n; ++j) {
dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1]);
}
}
cout << dp[0][n - 1] << endl;
}
Vitesse d'exécution: 31ms </ B> </ font>
Quel est le problème avec cette vitesse ... </ B>
Problème 2
Concours pédagogique DP / Récapitulatif du concours B du DP - Frog2
Python
DP.py
n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
for j in range(max(i - k, 0), i):
dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))
print(dp[n - 1])
Vitesse d'exécution: TLE </ font> </ B>
Python peut être un code court. Je pensais que c'était à nouveau TLE.
PyPy
DP.py
n, k = [int(i) for i in input().split()]
h = [int(i) for i in input().split()]
dp = [float('inf')] * n
dp[0] = 0
for i in range(1, n):
for j in range(max(i - k, 0), i):
dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]))
print(dp[n - 1])
Vitesse d'exécution: 408ms </ B> </ font>
J'ai soumis le même code sur PyPy et je suis devenu AC.
Java
Main.java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
int[] heights = new int[n];
for (int i = 0; i < n; i++) {
heights[i] = sc.nextInt();
}
int[] dp = new int[n];
for (int i = 0; i < n; i++) {
dp[i] = Integer.MAX_VALUE;
}
dp[0] = 0;
for (int i = 1; i < n; i++) {
for (int j=Math.max(i - k, 0); j < i; j++) {
dp[i] = Math.min(dp[i], dp[j] + Math.abs(heights[i] - heights[j]));
}
}
System.out.println(dp[n - 1]);
}
}
Vitesse d'exécution: 449ms </ B> </ font>
Le problème 1 était plus rapide en Java, mais le problème 2 était plus rapide dans PyPy. La vitesse est-elle presque la même?
C++
main.cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; ++i)
int main() {
int n, k;
cin >> n >> k;
vector<int> h(n), dp(n);
rep(i, n) cin >> h[i];
rep(i, n) dp[i] = 999999999;
dp[0] = 0;
for (int i = 1; i < n; ++i) {
for (int j = max(i - k, 0); j < i; ++j) {
dp[i] = min(dp[i], dp[j] + abs(h[i] - h[j]));
}
}
cout << dp[n - 1] << endl;
}
Vitesse d'exécution: 56ms </ B> </ font>
Vitesse d'exécution inhabituelle. C'est environ 10 fois plus rapide que les autres.
Résumé
question 1
Problème 2
Python est lent, mais je pense que vous pouvez vous battre avec PyPy et NumPy. Java semble être aussi rapide que PyPy. La vitesse C ++ est anormale </ B>.
Recommended Posts