192
111

More than 5 years have passed since last update.

Python, Java, C++の速度比較

Last updated at Posted at 2019-07-28

Python, Java, C++の速度比較

はじめに

私はもともとPythonをメインに勉強してきたのですが、今週からJavaとC++の勉強を始めたので、実行速度の比較をしてみることにしました。

AtCoderから計算量の多いDPの問題を選んで、ほぼ同一のアルゴリズムで提出してみました。

問題1

Educational DP Contest / DP まとめコンテスト L問題 - 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])

実行速度:TLE

シンプルに解けていますがPythonではなんと制限時間オーバーで間に合わず、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])

実行速度:324ms

まったく同じコードですが、PyPyで提出すれば通ります。競技プログラミングでPythonで戦うにはPyPyやNumPyをうまく使う必要があります。

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]);
    }
}

実行速度:258ms

やっていることは同じですが、Pythonよりもコードがずいぶん長くなりますね。速度は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;
}

実行速度:31ms

なにこの速度おかしくないですか…

問題2

Educational DP Contest / DP まとめコンテスト B問題 - 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])

実行速度:TLE

Pythonはコードが短くていいですね。と思いきや、またも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])

実行速度:408ms

PyPyで同一のコードを提出して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]);
    }
}

実行速度:449ms

問題1はJavaの方が早かったですが、問題2では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, 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;
}

実行速度:56ms

尋常ではない実行速度です。他より10倍くらい高速ですね。

まとめ

問題1
自分の提出

問題2
自分の提出

Pythonは遅いけどPyPyやNumPyを使えば戦えると思います。
JavaはPyPyと同じくらいの速度のようです。
C++の速度は異常

192
111
18

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
192
111