AtCoderのある問題についてC++ / Python での速度比較

概要

AtCoderやり始めてPython/C++の両方を使用しています。常識的に考えてスクリプト言語のPythonよりC++の方がはやいだろうなってことは想像できるけど、どのくらい違うんかなということで測定してみました。結果は「C++めちゃ速い!!」でした。

対象にした問題と解法概要

対象にした問題はAtCoderのABC143, D-Triangles。当日は海外出張中でちょうど搭乗手続き時間中にぶつかりリアルタイムに参加できなかったのですが、当面の目標はDがコンスタントにサクッと解けるようになることなので自習の対象に選んでみました。

解説はこちらAtCoderのABC143 解説PDFにあります。

三角形を構成する棒のうち，1 番目と 2 番目に長いものを固定します (ただし，同じ長さを持つ棒が 複数存在する場合は，予め適当に大小関係を定めておきます).
このとき，3 番目に長い棒として使える棒は，「2 番目の棒より短く，一定以上の長さを持つもの」です.

「3つの長さa,b,cの線分（a <= b, b<=c）で三角形が作れるためには a > c - b であることが必要十分」ってことですね。わたしは c < a + b の方が自分の感覚に近いのでこっちでコーディングしてみました。（どちらの考え方でも処理量は同じと思われるが違う可能性あるのかはなさそうだけど、深く考えてない）

方針として

• 与えられた線分を長さでソート。
• a,b をループで回して、(a,b)の組に対して(a,b,c）で三角形を作れるcがいくつあるか数えて合計していけばいいだろう。
• N=2000まで対応させないといけないのでa,b,cすべての組を回すとN^3のオーダになって計算間に合わなさそう。だから(a,b)の組に対して三角形を作れるcがいくつあるかは順番にチェックするんじゃなくて二分探索とかつかってやらんと間に合わないな。

というところまではすぐに考えが及んだ。二分探索使用するのって自分でコード書いていては時間足りないので既存の関数なりルーチン使うのだろうということも想像つくのだけど、そこで関数名がすぐに出てこないところろがまだまだ初心者たる所以。リアルタイムではないのですでに提出ずみの人のコードを参考にして
Python: bisect_left
C++: upper_bound
を使うとできそうと判明。この辺のよく使うルーチンを利用法を含めて覚えてしまう必要があるのだろうなと思われる。

##結果

結果はこんな感じになりました。

プログラムの種類（名前）	実行時間(ms)	提出時刻
C++ 二分探索不使用	883	2019-10-27 00:34:48
C++ 二分探索使用	48	2019-10-27 00:32:52
Python 二分探索使用(Code#2)	1366	2019-10-27 00:10:45
Python 二分探索使用(Code#1)	1272	2019-10-27 00:09:57

C++ でupper_boundを使用して書くと49msec。これは、Pythonの二分探索使用したCode#1の1272msecと比較して26.5倍高速です。C++だとupper_bound使わずに順番にチェックしていく方法でも883msecでPythonの二分探索使用したものよりも高速。C++早いです。

Python 二分探索使用のCode#1/Code#2の違いは、Code#1が参考にしたソースそのままでリストL（したのソースコード参照）全体を対象にしてbisect_leftをサーチしているのに対して、Code#2は

• L[i]+L[j]より大きくなるのはL[j+1]より後ろの要素にしかなり得ないのは分かっているのでサーチ対象をL[j+1]〜L[N-1]に限定したら多少早くなるのでは？という期待
• そもそも頭の中のイメージはこれだったという事実

を理由にサーチ対象を限定したもの。でも速度は却って悪化。悪化する理由は良くわからない。

所感

Python/C++どちらを使用するか？と考えた時、これだけ速度に差があると実行速度に不安がある問題についてはC++一択かと感じました。

ソースコード

Pythonのコード（ほとんど誰かのを丸パクリです。でも参照元わからなくなってしまった）

test143D.py

import bisect
N=int(input())
L=sorted(list(map(int,input().split())))

ans=0
for i in range(N-2):
  for j in range(i+1,N-1):
    ans+=bisect.bisect_left(L,L[i]+L[j])-j-1 # Code 1 
    # ans+=bisect.bisect_left(L,L[i]+L[j],j)-j-1 # Code 2 
print(ans)

二分探索upper_boundを使ったC++のコード

test143D.cpp

#include <iostream>
#include <algorithm>

using namespace std;

const int DIM = 2010;

int i,j,k,n,sum, v[DIM], *p;

int main(){
    long count = 0 ; 
    cin >> n;
    for (i = 1; i <= n; ++i) {
        cin >> v[i];
    }
    sort(v + 1, v + n + 1);
    for (i = 1; i<= n - 2; i++){
        for (j = i + 1; j <= n-1 ; j++){
            sum = v[i] + v [j]; 
            /* for(k = j + 1 ; k <= n; k++){
                if (v[k] < sum){
                    count ++;
                }
            } */
            p =  upper_bound(v+j+1, v + n + 1, sum - 1); 
            k = (p - v ) - j -1;   
            // cout << i<< " " <<  j << " " << (p - v ) << " " << k << "\n"; 
            count += k; 
        }
    }
    cout << count << "\n";
    return 0; 
}

二分探索upper_boundを使用せず、順番に三つ目の線分の長さをチェックしたC++のコード

test143D.1.cpp

#include <iostream>
#include <algorithm>

using namespace std;

const int DIM = 2010;

int i,j,k,n,sum, v[DIM], *p;

int main(){
    long count = 0 ; 
    cin >> n;
    for (i = 1; i <= n; ++i) {
        cin >> v[i];
    }
    sort(v + 1, v + n + 1);
    for (i = 1; i<= n - 2; i++){
        for (j = i + 1; j <= n-1 ; j++){
            sum = v[i] + v [j]; 
            for(k = j + 1 ; k <= n; k++){
                if (v[k] < sum){
                    count ++;
                } else {
                    break;
                }
            } 
        }
    }
    cout << count << "\n";
    return 0; 
}