I originally studied Python mainly, but since I started studying Java and C ++ this week, I decided to compare the execution speeds.
I selected a DP problem with a large amount of calculation from AtCoder and submitted it with almost the same algorithm.
Educational DP Contest / DP Summary Contest 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])
Execution speed: TLE </ font> </ B>
It's a simple solution, but in Python, the time limit is exceeded and it doesn't become 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])
Execution speed: 324ms </ B> </ font>
The code is exactly the same, but if you submit it with PyPy, it will pass. You need to use PyPy and NumPy well to fight in Python in competitive programming.
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]);
}
}
Execution speed: 258ms </ B> </ font>
You're doing the same thing, but the code is a lot longer than Python. Is it as fast as 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;
}
Execution speed: 31ms </ B> </ font>
What's wrong with this speed ... </ B>
Educational DP Contest / DP Summary Contest B Problem --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])
Execution speed: TLE </ font> </ B>
Python can be short code. I thought, it's TLE again.
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])
Execution speed: 408ms </ B> </ font>
I submitted the same code on PyPy and became 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]);
}
}
Execution speed: 449ms </ B> </ font>
Problem 1 was faster in Java, but problem 2 was faster in PyPy. Is the speed almost the same?
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;
}
Execution speed: 56ms </ B> </ font>
Unusual execution speed. It's about 10 times faster than the others.
Question 1
Problem 2
Python is slow, but I think you can fight with PyPy and NumPy. Java seems to be as fast as PyPy. C ++ speed is abnormal </ B>.
Recommended Posts