Help us understand the problem. What is going on with this article?

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

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++の速度は異常

Lily0727K
東大医学部卒、血液内科専門医です。令和元年にソフトウェアエンジニアに転職しました!競技プログラミングはPythonとC++でAtCoder青色。ポーカーのGTO戦略を研究して、noteに記事を書いています。
https://note.mu/nekochan0214
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした