Python, Java, C ++ speed comparison

Python, Java, C ++ speed comparison

Introduction

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.

Question 1

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>

Problem 2

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.

Summary

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