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

競プロで使いたい言語

tl;dr

競技プログラミングで今までと別の言語を使いたかったので、いくつかの言語の性能などを調べた。

  • Go
  • Javascript
  • Node.js
  • PHP
  • Python
  • Ruby
  • Rust

→ Go, PHP, Rust は可。Goはいいぞ。

検討対象

  • Go
  • Javascript
  • Node.js
  • PHP
  • Python
  • Ruby
  • Rust

基準

  1. 64 bit 整数の演算ができる (MUST)
  2. 1,000,000回単位の変数読み込みと代入ができる (MUST)
  3. 優先度付きキューがある (WANT)
  4. 書きやすい (WANT)
  5. その他

調査

(1) 1から 4000002 の総和をループで求めて、10^18を足して出力する。

期待する出力:

1000008000010000003

(2) その他、調べた or 試した内容を追記。

結果

Go (go 1.12.1)

https://ideone.com/d9YYlG

ソースコード:

package main
import "fmt"

func main() {
    a := "hello"
    val := int64(1000000000000000000)
    for x := int64(1); x <= 4000002; x++ {
        val += x
    }
    fmt.Println(a)
    fmt.Println(val)
}

実行時間:

0s
ループ回数を100倍にすると0.12s 程度かかる。

その他:

  • int上限は実行環境に依存し、Codeforcesでは 32 bit整数のそれになる。問題は 64 bit整数を扱える前提で出題されるので、Goで解く時は int64 を一通り使いこなす必要がある
  • VSCodeの拡張が優秀
  • 静的型付けが細かいので、テンプレが必要+肥大化しやすい

JavaScript (rhino 1.7.9)

https://ideone.com/RZCMkO

ソースコード:

importPackage(java.io);
importPackage(java.lang);

let a = 'hello';
let val = 1000000000000000000;
for (x = 0; x <= 4000002; x++) {
    val += x;
}
System.out.println(a);
System.out.println(val);

出力:

hello
1.000008000008E18

実行時間:

0.75s
遅い。

その他:

64 bit整数の演算が言語仕様に組み込まれていない。

Node.js (node 11.12.0)

https://ideone.com/8g7QJl

ソースコード:

let a = 'hello';
let val = BigInt(1000000000000000000);
for (x = BigInt(1); x <= 4000002; x++) {
    val += x;
}
process.stdout.write(a + '\n' + (val));

実行時間:

0.56s
遅い。

PHP (php 7.3.5)

https://ideone.com/hwagy7

ソースコード:

<?php

$a = 'hello';
$val = 1000000000000000000;
for ($x = 1; $x <= 4000002; $x++) {
  $val += $x;
}
echo $a;
echo PHP_EOL;
echo $val;

実行時間:

0.06s
スクリプト言語としては最速だろう。

その他:

比較的書きにくい。

  • 変数に$
  • 商を求めるときはintdiv()
  • for ... in記法がない

Python 3 (python 3.7.3)

https://ideone.com/wRuGaZ

ソースコード:

a = 'hello'
val = 1000000000000000000
for x in range(4000003):
  val += x
print(a)
print(val)

実行時間:

0.43s
遅い。

その他:

書きやすい言語ではあるので、今後の性能向上が待たれる。

番外編:PyPy

AtCoder, Coderforcesでは PyPy が利用可能。
Codeforces Custom Testで上記ソースを実行すると、下記のような結果になる。

  • Python 3.7.2 では Used: 702 ms, 0 KB
  • PyPy 3.6 (7.1.1) では Used: 233 ms, 1236 KB

Python を使いたい場合は、代わりに PyPy で提出した方がよい・・・ただし、Paizaの選択肢にPyPyはない。

Ruby (ruby 2.5.5)

https://ideone.com/ja4KyJ

ソースコード:

a = 'hello'
val = 1000000000000000000
for x in 1..4000002 do
  val += x
end
puts a
puts val

実行時間:

0.17s
少し遅い。

その他:

  • 書きやすい。
  • 優先度付きキューは言語仕様に含まれていない。

Rust (rust 1.33.0)

https://ideone.com/NjjPou

ソースコード:

use std::io;

fn main() {
    let mut input_text = String::new();
    io::stdin()
        .read_line(&mut input_text)
        .expect("failed to read from stdin");

    let trimmed = input_text.trim();
    let mut my_int = 0i64;
    match trimmed.parse::<i64>() {
        Ok(i) => my_int = i,
        Err(..) => println!("this was not an integer: {}", trimmed),
    };

    let a = "hello";
    let mut val = 1000000000000000000i64;
    for x in 1..40000003 {
        if x == 1 {
            val += my_int;
        } else {
            val += x;
        }
    }
    println!("{}", a);
    println!("{}", val);
}

入力

1

実行時間:

0.01s
速い。
上記のループを100倍すると 0.8s 程度かかる。

その他:
他の言語と同様に書いた場合はループ回数にかかわらず 0s になる。(コンパイル時に先行して計算している?)
ここでは標準入力を計算に混ぜて回避している。
他の言語より演算量が多くなっているので注意。

結論

  • Go
  • PHP
  • Rust

いずれも競プロの問題を解ける程度の性能はある。

ぎりぎり可?

  • Ruby
  • PyPy (?)

少し実行速度が遅い。

不可

  • Python
  • Javascript
  • Node.js

実行速度が遅すぎてTLEを受ける。または64 bit整数が扱えない。

個人的な意見

Go+VSCodeはいいぞ。テンプレを作れば。

Hope this helps.

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
ユーザーは見つかりませんでした