Geschwindigkeitsvergleich von Python, Java, C ++
Geschwindigkeitsvergleich von Python, Java, C ++
Einführung
Ursprünglich habe ich hauptsächlich Python studiert, aber seit ich diese Woche angefangen habe, Java und C ++ zu studieren, habe ich beschlossen, die Ausführungsgeschwindigkeit zu vergleichen.
Ich habe ein DP-Problem mit einem hohen Rechenaufwand von AtCoder ausgewählt und es mit fast demselben Algorithmus eingereicht.
Frage 1
DP-Bildungswettbewerb / DP-Zusammenfassungswettbewerb L Problem --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])
Ausführungsgeschwindigkeit: TLE </ font> </ B>
Es ist eine einfache Lösung, aber in Python ist das Zeitlimit überschritten und ich kann es nicht zu AC schaffen.
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])
Ausführungsgeschwindigkeit: 324 ms </ B> </ font>
Der Code ist genau der gleiche, aber wenn Sie ihn mit PyPy einreichen, wird er bestanden. Sie müssen PyPy und NumPy gut verwenden, um in Python in wettbewerbsfähiger Programmierung zu kämpfen.
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]);
}
}
Ausführungsgeschwindigkeit: 258 ms </ B> </ font>
Sie machen das Gleiche, aber der Code ist viel länger als Python. Ist es so schnell wie 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;
}
Ausführungsgeschwindigkeit: 31 ms </ B> </ font>
Was ist los mit dieser Geschwindigkeit ... </ B>
Problem 2
Pädagogischer DP-Wettbewerb / DP-Zusammenfassungswettbewerb B Problem - Frosch2
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])
Ausführungsgeschwindigkeit: TLE </ font> </ B>
Python kann Kurzcode sein. Ich dachte, es wäre wieder 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])
Ausführungsgeschwindigkeit: 408 ms </ B> </ font>
Ich habe den gleichen Code auf PyPy eingereicht und wurde 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]);
}
}
Ausführungsgeschwindigkeit: 449 ms </ B> </ font>
Problem 1 war in Java schneller, aber Problem 2 war in PyPy schneller. Ist die Geschwindigkeit fast gleich?
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;
}
Ausführungsgeschwindigkeit: 56 ms </ B> </ font>
Ungewöhnliche Ausführungsgeschwindigkeit. Es ist ungefähr zehnmal schneller als die anderen.
Zusammenfassung
Frage 1
Problem 2
Python ist langsam, aber ich denke, Sie können mit PyPy und NumPy kämpfen. Java scheint so schnell zu sein wie PyPy. C ++ - Geschwindigkeit ist abnormal </ B>.