競プロメモ

競プロなど

【プログラミング言語速度比較】Collatz数列ベンチマークを言語別比較しよー！

AtCoder 番外

Collatz ベンチマーク

目次

追記(2021/02/23)

このベンチマークでは Collatz 数列と呼ばれるものを使って適当に言語ごとの速度を測っているのですが、正直なところ良いベンチマークとは言えません。

適当に書いたら思っていた以上にアクセスされており驚いています。

時間があれば、これよりもっと正確で実用的なベンチマークをしたいと思っているのですが、以下の条件を満たすようないいベンチマークが見つかっていません。

  • 実装が軽い（いろんな言語で書くことを考えると、できるだけ軽いほうがいい）
  • 計算量解析が容易
  • ボトルネックが自明（その処理の速度を言語ごとに比較できる）

Dijkstra や DP など案は適当に上がったのですが、どうもしっくりきていません。良さそうな案があったら是非コメントください。

Collatz 数列とは

整数 n が偶数ならば 2 で割り、奇数ならば 3 倍して 1 を足す。これを n が 1 になるまで繰り返す。

証明されていないが、1020 くらいまでは必ず 1 になるらしい。

やること

コラッツ数列の長さを求める関数を書き、それを用いて言語の実行速度を測る。

計測方法

AtCoder のコードテストを用います（AtCoder 上での処理時間がわかれば、言語別の実行速度の参考になるかと思ったため。サーバーに負荷がかかるとかで怒られたらやめます）

任意の整数i(1 <= i <= 104,105,106, 107)について、iが 1 になるまで上記の操作をしたときの操作回数を求めるプログラムを書き、総和を 1000000007 で割った余りを求める（107 程度ではオーバーフローはしませんでしたが）

基本的には、collatz()関数をmain()関数内でn回回し、その総和の Mod を取る形で実装しています。

Haskell は言語仕様的にループを使わないので、再帰で実装しています。

ベンチマーク結果

結果表

単位は[ms] TLEは 105 ms 以上

言語 104 105 106 107
Rust(メモ化チート) 7 12 61 512
Rust(usize) 10 23 176 1887
Rust(isize) 10 37 275 2910
C++ (GCC) 8 34 301 3211
C++ (Clang) 13 34 302 3211
C++(GCC)編集版 7 25 203 2119
C++(GCC)編集版(unsigned) 9 31 301 3394
C++(Clang)編集版 11 38 272 2727
C++(Clang)編集版(unsigned) 13 25 179 1896
C(GCC) 4 22 194 2027
C(GCC)(unsigned) 8 30 314 3559
C(Clang) 6 27 249 2727
C(Clang)(unsigned) 7 20 171 1887
C(Clang)(unsigned)(アセンブリ参考) 6 19 164 1807
D(LDC) 10 25 175 1870
D(GDC) 30 46 258 2586
D(DMD) 10 51 400 4282
Nim 11 30 229 2424
Nim(uint) 10 35 251 2678
Fortran 12 28 252 2889
Objective-C 76 51 333 2910
Swift 9 40 305 3078
Golang 9 42 291 3103
Haskell 11 30 285 3241
Crystal 15 48 345 3746
Java 116 146 489 4404
Kotlin 119 146 522 4551
Scala 518 565 920 4681
Julia 216 229 383 2071
Pascal 9 50 413 5012
C# 89 109 487 4825
Visual Basic 95 120 511 4702
PyPy2 69 113 805 5522
PyPy3 80 116 599 5528
JavaScript 72 89 1557 TLE
Common Lisp 53 157 1657 TLE
Php 57 454 5269 TLE
Cython 74 364 3885 TLE
Cython2 54 67 280 2552
Clojure 1921 2136 5005 TLE
Ruby 110 685 7384 TLE
Scheme 70 604 7425 TLE
Python 109 1059 TLE TLE
Python(numba) 130 124 271 1968
Lua(Lua) 104 1152 TLE TLE
Lua(LuaJIT) 12 65 642 7169
Perl 124 1244 TLE TLE
Awk 121 1398 TLE TLE
Bc 747 9481 TLE TLE
Raku(Perl6) 1232 TLE TLE TLE
dc 1378 TLE TLE TLE
Vim 3689 TLE TLE TLE
Bash 7674 TLE TLE TLE

編集履歴

詳細を見る

C#を追加しました。 白緑さん、ありがとうございます！

C++の編集版を追加しました。ありがとうございます！

Python と PyPy を追加しました。arasius さん、ありがとうございます！

Crystal を追加しました。yuruhiya さん、ありがとうございます！

Golang を追加しました。

JavaScript を追加しました。

Fortran を追加しました。jj1gui さん、ありがとうございます！

Ruby を追加しました。KowerKoint さん、ありがとうございます！

Rust だけ非負整数だったので、Rust の isize 版、C++の unsigned 版も作りました。

D 言語を追加しました。lempiji さん、ありがとうございます！

Bash を追加しました。KowerKoint さん、ありがとうございます！

Swift を追加しました。

Objective-C を追加しました。matsumo さん、ありがとうございます！

C を追加しました。mikhail さん、fujitanozomu さん、ありがとうございます！ https://twitter.com/Mikhail_chan/status/1284665518524256256?s=20

Bc を追加しました。fujitanozomu さん、ありがとうございます！

Perl を追加しました。fujitanozomu さん、ありがとうございます！

Vim を追加しました。KowerKoint さん、ありがとうございます！

Php と AWK と Lua と Pascal を追加しました。fujitanozomu さん、本当にありがとうございます！！

Rust のメモ化版を追加しました。

Visual Basic を追加しました。KowerKoint さん、ありがとうございます！ https://twitter.com/KowerKoint2010/status/1285871100329525254?s=20

Raku(Perl6)を追加しました。fujitanozomu さん、ありがとうございます！ https://twitter.com/fujitanozomu/status/1285957649926811654?s=20

dc を追加しました。fujitanozomu さん、ありがとうございます！ https://twitter.com/fujitanozomu/status/1287306706444115968?s=20

Nim を追加しました。Kitagawa さん、ありがとうございます！ https://twitter.com/kitagawahr1992/status/1288004487802572800?s=20

コメントより、Nim の uint 版を追加しました。udoooon さん、ありがとうございます！

コメントより、Cython を追加しました。papico さん、ありがとうございます！

コメントより、Numba を使った Python を追加しました。sooooba さん、ありがとうございます。入力を可変にできていません

Clojure CommonLisp Scheme を追加しました。Linuxmetal さんありがとうございます！ https://twitter.com/linuxmetel/status/1364182475480522756?s=20

Twitter の DM より，Cython, julia, numba を追加しました．ありがとうございます！

感想

基本的に最速クラス

2000ms を切るくらいです。

Rust は相変わらず早いです。ただし、usize から isize にすると結構速度が落ちました。

C++も、Clang においては Rust と同じ傾向です。

Rust も D も C++(Clang)も C(Clang) も、非負整数の最適化が早いみたいです。

特に Rust は、配列の添字に使えるのが usize だけだったり、非負整数を扱う機会が多いのでそれなりに最適化されていそうです。

癖がある最速クラス

2000ms 前半でした。 unsigned より signed のほうが早い、ちょっと癖のある感じです。GCC は特殊ですね。どっちにしろ最速クラスなのには変わりないです。

準最速クラス

2000ms 後半くらいで結構早いです。Java の 1.5~2 倍程度高速です。困らない速さだと思います。

Fortran は速さ的には C++に近い感じです。結構イメージ通りではあります。というか初めて Fortran のコードを見ました（）

Objective-C ってこんなに C なんですね。書きにくそう（）

Nimは思ったより遅かったです。Rust並かRustを超えると思ったんだけどな・・・

まぁまぁ早いクラス

3000ms 台で十分に高速だと思います。ただ、ここから最速とは言われないイメージがあります。

Haskell 思ったより早い！

Golang は C++や Haskell 並の速度は出ますね

Crystal は Ruby 版の Nim だと思うと早いのも不思議じゃないですね。

Swift は Kotlin よりちょっとだけ早いです。

普通クラス

4000ms 台で高速ですが、Rust などと比べると 2 倍の差がついています。

Scala は圧倒的に JVM 起動時間が重いですね。Rust なら 1ms の問題でも Scala だとジャッジがめっちゃ遅いのでちょっと不便です。

C#は JVM の起動時間を無視したとき、Java とほとんど同じくらいの速度に見えます。

Visual Basic ってこんなに早いんですね。

やや遅いクラス

  • PyPy
  • Lua(LuaJIT)

5000ms を超えました。Python と比べれば圧倒的な改善ですが、流石にトップレベルにはかなわない感じです。

PyPy は想像以上に早かったです。Java と対して差がついていないので、PyPy ならどの問題も通せそうです（MLE 問題がありそうですが）。

Lua も JIT コンパイルすると PyPy より遅い程度で動作しますね。

ビリ

ダントツで遅く、TLE が出ました・・・。 動的型付け言語なので仕方ないですね。

JavaScript は Python に比べれば圧倒的に早いですが、それでも静的型付け言語には全然及びませんね。想定解が通らない問題は少なそうですが、あんまり書きやすいイメージもないので、競プロにはあんまり向いていないかもしれません。

Php も思ったより早いですね。JS に近いイメージでしょうか

Ruby は JavaScript には及びませんが、Python と比べると結構早いですね。Ruby は関数がめちゃめちゃ豊富で、すごく短いコードを見かけたりすることがあるので、問題によっては楽に解けそうです。ただ、ゴリゴリの実装問題とかだともしかすると間に合わないことがあるかもしれないですね・・・。

PyPy に対して Python は想像以上に遅かった・・・。想定解が通らない問題があってもおかしくないかもしれないです。Cython ももうちょっと早いと思ってました。

う 笑

う 笑

言語別実装

Rust メモ化版

メモ化すると 500ms 程度になりましたが、これ以上は早くなりませんでした。（HashMap や BTreeMap ですべての要素をメモ化したり、一部の要素をメモ化したりしましたが、Vector で n 個までメモ化するのが最速でした）

コードを見る

#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use std::io::stdin;
use std::collections::{HashMap, BTreeMap};

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let n = buf.split_whitespace().next().unwrap().parse().unwrap();
    // let mut memo = HashMap::new();
    let mut memo = vec![None; n];


    let mut acc = 0;
    for i in 1..=n {
        acc += collatz(i, &mut memo);
        acc %= 1000000007;
    }
    println!("{}", acc);
}

fn collatz(i: usize, memo: &mut [Option<usize>]) -> usize {
    match memo.get(i).and_then(|o| *o) {
        Some(t) => t,
        None => {
            let cnt =
                if i == 1 { 0 } else if i % 2 == 0 { 1 + collatz(i / 2, memo) } else { 1 + collatz(i * 3 + 1, memo) };

            if (0..memo.len()).contains(&i) {
                memo[i] = Some(cnt);
            }
            cnt
        }
    }
}

Rust

大好き！適当に書いてもコンパイルが通れば一定に高速で安全なコードになるのは最高です。

isize 版はcollatz(mut i:isize)->isizeとして測定しました。

コードを見る

#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use std::io::stdin;

const U_INF: usize = 1 << 60;
const I_INF: isize = 1 << 60;

fn main() {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    let n = buf.split_whitespace().next().unwrap().parse().unwrap();
    let mut acc = 0;
    for i in 1..=n {
        acc += collatz(i);
        acc %= 1000000007;
    }
    println!("{}", acc);
}

fn collatz(mut i: usize) -> usize {
    let mut cnt = 0;
    while i != 1 {
        cnt += 1;
        if i % 2 == 0 {
            i /= 2;
        } else {
            i *= 3;
            i += 1;
        }
    }
    cnt
}

C++

意外と Rust のほうが早いです C++の書き心地は Rust とあんまり変わりませんね。危ない橋を渡れる言語だと思っています。

for を 0 から始めるようにすると 1.5 倍位早くなりました。不思議。

unsigned 版はusing ll = unsigned long longにしました。

編集前

コードを見る

#include <iostream>

using namespace std;

using ll = long long;

ll collatz(ll i) {
    ll cnt = 0;
    while (i != 1) {
        cnt++;
        if (i % 2 == 0) {
            i /= 2;
        } else {
            i *= 3;
            i += 1;
        }
    }
    return cnt;
}

int main() {
    ll n;
    cin >> n;
    ll acc = 0;
    for (ll i = 1; i <= n; i++) {
        acc += collatz(i);
        acc %= 1000000007;
    }
    cout << acc << endl;
}

編集後

コードを見る

#include <iostream>

using namespace std;

using ll = long long;

ll collatz(ll i) {
    ll cnt = 0;
    while (i != 1) {
        cnt++;
        if (i % 2 == 0) {
            i /= 2;
        } else {
            i *= 3;
            i += 1;
        }
    }
    return cnt;
}

int main() {
    ll n;
    cin >> n;
    ll acc = 0;
    for (ll i = 0; i < n; i++) {
        acc += collatz(i+1);
        acc %= 1000000007;
    }
    cout << acc << endl;
}

Java

C++,Rust ほどではないが早いです。

コードは C++以上に書きにくい印象があります。

コードを見る

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        long acc = 0;
        for (long i = 1; i <= n; i++) {
            acc += collatz(i);
            acc %= 1000000007;
        }
        System.out.println(acc);
    }

    public static long collatz(long j) {
        long i = j;
        long cnt = 0;
        while (i != 1) {
            cnt++;
            if (i % 2 == 0) {
                i /= 2;
            } else {
                i *= 3;
                i += 1;
            }
        }
        return cnt;
    }
}

Kotlin

Java とほとんど変わらないです。

Kotlin がかける環境ならば Java を書く理由がない気がします。

コードを見る

import java.util.*

fun main() {
    val sc = Scanner(System.`in`)
    val n = sc.nextLong();
    var acc = 0L;
    for (i in 1..n) {
        acc += collatz(i)
        acc %= 1000000007
    }
    println(acc)
}

fun collatz(j: Long): Long {
    var cnt = 0L
    var i = j
    while (i != 1L) {
        cnt += 1
        if (i % 2L == 0L) {
            i /= 2
        } else {
            i *= 3
            i += 1
        }
    }
    return cnt
}

Scala

JVM 起動時間がすごく重いですねー。 N が大きくなると差がなくなることから、ロジック部分の処理速度は Java と対して変わらなそうです

コードを見る

import java.util.Scanner

object Main {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)
    val n = sc.nextLong()
    var acc = 0L
    for (i <- 1L to n) {
      acc += collatz(i)
      acc %= 1000000007L
    }
    println(acc)
  }

  def collatz(j: Long): Long = {
    var i = j
    var cnt = 0
    while (i != 1) {
      cnt += 1
      if (i % 2 == 0) {
        i /= 2
      } else {
        i *= 3
        i += 1
      }
    }
    cnt
  }
}

Haskell

Haskell は C と同じデータ構造とアルゴリズムならば同等の速度を出せると聞いていました。

その話通り、Int 型の指定を入れると C++（編集前）並に爆速です。

solve :: Int -> Int を指定しないと solve :: Integral a => a -> a と多相になるので遅いです

コードを見る

main = do
  n <- read <$> getLine
  print $ solve n

solve :: Int -> Int
solve 1 = collatz 1 0
solve n = (collatz n 0 + solve (n-1)) `mod` 1000000007

collatz :: Int -> Int -> Int
collatz 1 acc = acc
collatz n acc | n `mod` 2 == 0 = collatz (n `div` 2) (acc + 1)
collatz n acc = collatz (n * 3 + 1) (acc + 1)

CSharp

Java と同じくらいの速度なので、罠が少なければ結構良い言語かもしれないです（人気ありますよね）

コードを見る

using System;

class Test{
  public static void Main(string[] args){
    var n = long.Parse(Console.ReadLine());
    long acc=0;
    for(long i=1;i<=n;i++){
      acc+=collatz(i);
      acc%=1_000_000_007;
    }
    Console.WriteLine(acc);
  }

  private static long collatz(long i){
    long cnt = 0;
    while (i != 1) {
      cnt++;
      if (i % 2 == 0) {
        i /= 2;
      } else {
        i *= 3;
        i += 1;
      }
    }
    return cnt;
  }
}

Python & PyPy

コードはやっぱりシンプルですね

PyPy じゃないと速度はだいぶ遅いです

コードを見る

def collatx(i):
    cnt=0
    while i!=1:
        cnt+=1
        if i%2==0:
            i//=2
        else:
            i*=3
            i+=1
    return cnt

def main():
    n=int(input())
    acc=0
    for i in range(1,n+1):
        acc+=collatx(i)
        acc%=1000000007
    print(acc)

if __name__ == "__main__":
    main()

Crystal

コードが凄くシンプルでびっくりです。

それでいてかなり高速でした。

コードを見る

def collatz(i)
  cnt = 0i64
  while i != 1
    cnt += 1
    if i.even?
      i //= 2
    else
      i *= 3
      i += 1
    end
  end
  cnt
end

n = read_line.to_i64
puts (1i64..n).reduce(0i64) { |acc, i|
  acc += collatz(i)
  acc %= 1_000_000_007
}

Golang

結構早いです。

IDE との相性もよく、気持ちよく書けます。

コードを見る

package main

import "fmt"

func main() {
 var n int
 _, _ = fmt.Scan(&n)
 acc := 0

 for i := 1; i <= n; i++ {
  acc += collatz(i)
  acc %= 100000007
 }

 fmt.Println(acc)
}

func collatz(j int) int {
 i := j
 cnt := 0
 for ; i != 1; {
  cnt++
  if i%2 == 0 {
   i /= 2
  } else {
   i *= 3
   i += 1
  }
 }
 return cnt
}

JavaScript

動的型付け言語書けません

コードを見る

"use strict";

const main = (arg) => {
    const n = parseInt(arg);

    let acc = 0;
    for (let i = 1; i <= n; i++) {
        acc += collatz(i);
        acc %= 1000000007;
    }

    console.log(acc);
};
main(require("fs").readFileSync("/dev/stdin", "utf8"));

function collatz(i) {
    let cnt = 0;
    while (i !== 1) {
        cnt++;
        if (i % 2 === 0) {
            i /= 2;
        } else {
            i *= 3;
            i += 1;
        }
    }
    return cnt;
}

Fortran

コードを雰囲気で読むことができませんでした。

bash とかとも近い気がしました（素人感）

コードを見る

program main
    implicit none
    integer(8) n,i,acc
    read*,n
    acc=0
    do i=1,n
        acc=acc+collatz(i)
        acc=mod(acc,1000000007)
    end do
    print'(i0)',acc
contains
integer(8) function collatz(n_in)
    integer(8) n,n_in
    collatz=0
    n=n_in

    do while(n/=1)
        collatz=collatz+1
        if(mod(n,2)==0)then
            n=n/2
        else
            n=3*n+1
        end if
    end do
end function
end program main

Ruby

Ruby のコードは左によっているイメージがあります。

コードを見る

def collatz(i)
  cnt = 0
  while i != 1 do
    cnt += 1
    if i % 2 == 0
      i /= 2
    else
      i *= 3
      i += 1
    end
  end
  cnt
end

n = gets.to_i
acc = 0
n.times do |i|
  acc += collatz(i + 1)
  acc %= 1000000007
end
puts(acc)

D 言語

びっくりするくらい早かったです。

コードを見る

import std.stdio;
import std.conv;

size_t collatz()(size_t i)
{
    size_t cnt = 0;
    while (i != 1)
    {
        cnt++;
        if (i % 2 == 0)
        {
            i /= 2;
        }
        else
        {
            i *= 3;
            i += 1;
        }
    }
    return cnt;
}

void main()
{
    size_t n = readln().to!size_t;

    size_t acc = 0;
    for (size_t i = 1; i <= n; i++)
    {
        acc += collatz(i + 1);
        acc %= 1000000007;
    }
    writeln(acc);
}

Bash

Bash に処理速度を期待してはいけません

コードを見る

collatz() {
    cnt=0
    j=$1
    while [ $j -ne 1 ] ; do
        cnt=$((cnt+1))
        if [ $((j % 2)) -eq 0 ]; then
            j=$((j / 2))
        else
            j=$((j * 3))
            j=$((j + 1))
        fi
    done
    return_var=$cnt
}

read n
acc=0
for i in `seq 1 $n`; do
    collatz $i
    acc=$((acc + return_var))
    acc=$((acc % 1000000007))
done
echo $acc

Swift

Swift のコードも見やすいと思います。

速度も申し分ないですね。

コードを見る

func collatz(_ j: Int64) -> Int64 {
    var cnt: Int64 = 0
    var i = j
    while (i != 1) {
        cnt += 1
        if (i % 2 == 0) {
            i /= 2
        } else {
            i *= 3
            i += 1
        }
    }
    return cnt
}

let n = Int64(readLine()!)!
var acc: Int64 = 0;
for i in 1...n {
    acc += collatz(i)
    acc %= 1000000007
}
print(acc)

Objective-C

見た目は C++と同じ感じですね

思ったより遅かったです。

コードを見る

#import <stdio.h>

typedef long long ll;

ll collatz(ll i) {
    ll cnt = 0;
    while (i != 1) {
        cnt++;
        if (i % 2 == 0) {
            i /= 2;
        } else {
            i *= 3;
            i += 1;
        }
    }
    return cnt;
}

int main() {
    ll n;
    scanf("%lld", &n);
    ll acc = 0;
    for (ll i = 1; i <= n; i++) {
        acc += collatz(i);
        acc %= 1000000007;
    }
    printf("%lld\n", acc);
}

C

longは AtCoder 上では 64bit らしいです https://twitter.com/Mikhail_chan/status/1284743491872907265?s=20

通常版

unsignedをlong longの前に追加するとunsigned版になります

コードを見る

#include <stdio.h>

long long collatz(long long n) {
   long long cnt = 0;
    while (n != 1) {
        cnt++;
        if (n % 2 == 0) {
            n /= 2;
        } else {
            n *= 3;
            n++;
        }
    }
    return cnt;
}

int main(void) {
    long long n, ans = 0;
    scanf("%ld", &n);
    for (unsigned long long i = 0; i < n; i++) {
        ans += collatz(i + 1);
        ans %= 1000000007;
    }
    printf("%ld\n", ans);
}

アセンブリ修正版

コードを見る

    #include <stdio.h>

    #if 1
    unsigned long collatz(unsigned long n);
    __asm(
    "        .text                        \n"
    "        .globl  collatz              \n"
    "        .p2align 4                   \n"
    "collatz:                             \n"
    "        xor     %eax, %eax           \n"
    "        cmp     $1, %rdi             \n"
    "        je      1f                   \n"
    "        .p2align 4, 0x90             \n"
    "0:      inc     %rax                 \n"
    "        mov     %rdi, %rcx           \n"
    "        shr     $1, %rcx             \n"
    "        lea     1(%rdi,%rdi,2), %rdi \n"
    "        cmovnc  %rcx, %rdi           \n"
    "        cmp     $1, %rdi             \n"
    "        jne     0b                   \n"
    "1:      ret                          \n"
    );
    #else
    unsigned long collatz(unsigned long n) {
        unsigned long cnt = 0;
        while (n != 1) {
            cnt++;
            if (n % 2 == 0) {
                n /= 2;
            } else {
                n *= 3;
                n++;
            }
        }
        return cnt;
    }
    #endif

    int main(void) {
        unsigned long n, ans = 0;
        scanf("%lu", &n);
        for (unsigned long i = 0; i < n; i++) {
            ans += collatz(i + 1);
            ans %= 1000000007;
        }
        printf("%lu\n", ans);
    }

Bc

Bash よりは書きやすそうです

コードを見る

define collatz(i) {
    cnt = 0
    while (i != 1) {
        cnt += 1
        if (i % 2 == 0) {
            i /= 2
        } else {
            i *= 3
            i += 1
        }
    }
    return cnt;
}

scale = 0
n = read()
ans = 0
for (i = 1; i <= n; i++) {
    ans += collatz(i);
    ans %= 1000000007;
}
print ans, "\n";

Perl

最近はあんまり聞かない言語ですね～。

速度は Python に近いようです。

コードを見る

#!/usr/bin/perl

sub collatz {
    my ($i) = @_;

    my $cnt = 0;
    while ($i != 1) {
        $cnt += 1;
        if ($i % 2 == 0) {
            $i /= 2
        } else {
            $i *= 3;
            $i += 1
        }
    }
    return $cnt
}

my $scale = 0;
my $n = <STDIN>;
my $ans = 0;
for (my $i = 1; $i <= $n; $i++) {
    $ans += collatz($i);
    $ans %= 1000000007
}
print "$ans\n"

Php

Web で使うからか、Python などより JS に近い速度でした（JS よりは遅いですが）

コードを見る

<?php

function collatz($i) {
    $cnt = 0;
    while ($i != 1) {
        $cnt += 1;
        if ($i % 2 == 0) {
            $i /= 2;
        } else {
            $i *= 3;
            $i += 1;
        }
    }
    return $cnt;
}

$n = fgets(STDIN);
$ans = 0;
for ($i = 1; $i <= $n; $i++) {
    $ans += collatz($i);
    $ans %= 1000000007;
}
echo "$ans\n";

?>

Vim

Vim が提出できるとは思っていませんでした

コードを見る

:function! Collatz(j) abort
    :let cnt = 0
    :let x = a:j
    :while x != 1
        :let cnt += 1
        :if x % 2 == 0
            :let x /= 2
        :else
            :let x *= 3
            :let x += 1
        :endif
    :endwhile
    :return cnt
:endfunction

:delete a
:let n = @a
:let acc = 0
:for i in range(n)
    :let acc += Collatz(i + 1)
    :let acc %= 1000000007
:endfor
:put! = acc
:write
:quit

Awk

Bc に近いイメージでしょうか。Bash や Bc よりは早いです。

コードを見る

function collatz(i) {
    cnt = 0
    while (i != 1) {
        cnt += 1
        if (i % 2 == 0) {
            i /= 2
        } else {
            i *= 3
            i += 1
        }
    }
    return cnt
}

{
    acc = 0
    for (i = 1; i <= $0; i++) {
        acc += collatz(i)
        acc %= 1000000007
    }
    print acc
}

Lua

コードはなんとなく Bash みたいな雰囲気がありますが Bash より圧倒的に読みやすいです（Pascal に近い構文らしいです）

コードを見る

function collatz(i)
  cnt = 0
  while i ~= 1 do
    cnt = cnt + 1
    if i % 2 == 0 then
      i = i / 2
    else
      i = 3 * i
      i = i + 1
    end
  end
  return cnt
end

n = io.stdin:read()
acc = 0
for i = 1, n do
  acc = acc + collatz(i)
  acc = acc % 1000000007
end
print(acc)

Pascal

C＃より早いくらいの速度でした。コードは Ruby と Bash に近い印象です（あんまり詳しくないのでこの辺的外れだと思います・・・）

コードを見る

program collatz;

function collatz(i: UInt64): UInt64;
var cnt: UInt64;
begin
  cnt := 0;
  while i <> 1 do
    begin
      cnt := cnt + 1;
      if i mod 2 = 0 then
        begin
          i := i div 2
        end
      else
        begin
          i := 3 * i;
          i := i + 1
        end
    end;
  collatz := cnt
end;

var n:   UInt64;
var acc: UInt64;
var i:   UInt64;

begin
  readln(n);
  acc := 0;
  for i := 1 to n do
    begin
      acc := acc + collatz(i);
      acc := acc mod 1000000007
    end;
  writeln(acc)
end.

Visual Basic

思ったより早い言語

コードを見る

Module Collatz
    Function Collatz(ByVal i As Long)
        Dim cnt As Long
        cnt = 0
        While i <> 1
            cnt += 1
            If i Mod 2 = 0 Then
                i \= 2
            Else
                i *= 3
                i += 1
            End If
        End While
        Return cnt
    End Function

    Sub Main(ByVal args() as String)
        Dim n, i, acc As Long
        n = Console.ReadLine()
        acc = 0
        For i=1 To n
            acc += Collatz(i)
            acc = acc Mod 1000000007
        Next
        Console.WriteLine(acc)
    End Sub
End Module

Raku(Perl6)

Perl と比較しても断然遅かったです。(Perl6 とは)

コードを見る

#!/usr/bin/perl6

sub collatz(Int $i is copy --> Int) {
    my Int $cnt = 0;
    while ($i != 1) {
        $cnt += 1;
        if ($i % 2 == 0) {
            $i div= 2;
        } else {
            $i *= 3;
            $i += 1;
        }
    }
    return $cnt;
}

my Int $n = +get();
my Int $ans = 0;
loop (my Int $i = 1; $i <= $n; $i++) {
    $ans += collatz($i);
    $ans %= 1000000007;
}
say "$ans\n"

dc

電卓のあれらしいですが正直全く読めません。このへんの言語ってどんなきっかけで学ぶんでしょうか

コードを見る

[cq]sa[3*1+q]sb[d2%1=b2/]sc[d1=alcxlx1+sxldx]sd[0sxldxlx]se?sn0si0sy[li1+dsilexly+syliln>l]dslxlyn

Nim

Haskellと同じ感じの再帰実装のようです。コードは比較的読みやすいですね。

コードを見る

import strutils, sequtils

const MOD = 1000000007'u

func collatz(i: uint): uint =
  if i == 1: 0'u
  elif i mod 2 == 0: collatz(i div 2) + 1'u
  else: collatz(i * 3 + 1) + 1'u

proc main() =
  let n = stdin.readLine().parseUInt()
  echo (1'u..n).foldl((a + collatz(b)) mod MOD, first = 0'u)

if isMainModule:
  main()

Nim(uint)

uint を使った非再帰実装のようです。

前者とあまり変わらないですね。

コードを見る

import strutils

const MOD = 1000000007'u

proc collatz(i: uint): uint = 
    var 
        i = i 
        res = 0'u 
    while i != 1:
        if (i and 1) == 0:
            i = i shr 1 
        else:
            i *= 3 
            inc i 
            inc res 
    return res

proc main() = 
    let n = stdin.readLine().parseUInt()
    var 
        i = 1'u 
        ret = 0'u

    while i <= n:
        ret += collatz(i)
        ret = ret mod MOD 
        inc i 
    echo ret

if isMainModule:
    main()

Cython

うーん、PyPy くらい早くなると思っていたのですが。

コードを見る

cpdef int collatx(i):
    cpdef int cnt=0
    while i!=1:
        cnt+=1
        if i%2==0:
            i//=2
        else:
            i*=3
            i+=1
    return cnt

cpdef main():
    cpdef int n=int(input())
    cpdef int acc=0
    for i in range(1,n+1):
        acc+=collatx(i)
        acc%=1000000007
    print(acc)

if __name__ == "__main__":
    main()

Cython2

詳しくないので違いがあんまり判らないんですが，以下のコードだと上のコードに比べかなり高速に実行できるようです

コードを見る

# cython: language_level = 3, nonecheck = False, cdivision = True
ctypedef unsigned long long ull
cdef ull collatz(ull i) nogil:
    cdef ull cnt = 0
    while i != 1:
        cnt += 1
        if i % 2 == 0:
            i //= 2
        else:
            i *= 3
            i += 1
    return cnt

def main():
    cdef:
        ull n = int(input())
        ull acc = 0
    for 1 <= i < n + 1:
        acc += collatz(i)
        acc %= 1000000007
    print(acc)

if __name__ == '__main__':
    main()

Python(Numba)

これ実は動かせていません。

入力を可変にしようと思って色々やったのですが、Python の知識が欠けており…

コードを見る

from numba import jit

@jit('i8(i8)', nopython=True)
def collatx(i):
    cnt = 0
    while i != 1:
        cnt += 1
        if i % 2 == 0:
            i //= 2
        else:
            i *= 3
            i += 1
    return cnt


@jit(nopython=True)
def main():
    n = 10 ** 7
    acc = 0
    for i in range(1, n + 1):
        acc += collatx(i)
        acc %= 1000000007
    print(acc)


if __name__ == "__main__":
    main()

Clojure

コードを見る

(defn collatz [x]
  (loop [i x cnt 0]
    (cond (= i 1) cnt
          (even? i) (recur (quot i 2) (inc cnt))
          :else (recur (inc (* i 3)) (inc cnt)))))

(def n (read))

(println (loop [i 1 acc 0]
           (if (<= i n)
             (recur (inc i) (rem (+ acc (collatz i)) 1000000007))
             acc)))

Common Lisp

コードを見る

(defun collatz (i)
  (loop for cnt from 0
        until (= i 1)
        do (setq i (if (evenp i)
                       (floor i 2)
                       (1+ (* 3 i))))
        finally (return cnt)))

(let ((n (read))
      (acc 0))
  (loop for i from 1 to n
        do (setq acc (rem (+ acc (collatz i)) 1000000007)))
  (princ acc)
  (fresh-line))

Scheme

コードを見る

(define (collatz x)
  (let loop ((i x)
             (cnt 0))
    (if (= i 1)
      cnt
      (if (even? i)
        (loop (quotient i 2) (+ cnt 1))
        (loop (+ 1 (* 3 i)) (+ cnt 1))))))

(define n (read))

(print (let loop ((i 1)
                  (acc 0))
         (if (<= i n)
           (loop (+ i 1) (remainder (+ acc (collatz i)) 1000000007))
           acc)))

Julia

科学計算用途の動的型付け言語らしいんですがかなり早いですね．JIT コンパイルでもしてるんでしょうか

コードを見る

function collatz(i)
    cnt = 0
    while i != 1
        cnt += 1
        if i & 1 == 0
            i >>= 1
        else
            i *= 3
            i += 1
        end
    end
    cnt
end

function main()
    n = parse(Int, readline())
    acc = 0
    for i = 1:n
        acc += collatz(i)
        acc %= 1000000007
    end
    println(acc)
end

if abspath(PROGRAM_FILE) == @__FILE__
    main()
end

numba

i8 を使っているようで結構早いですね．

コードを見る

import sys
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba import *
    from numba.pycc import CC

    @njit('i8(i8)', parallel = True, cache = True)
    def collatz(i):
        cnt = 0
        while i != 1:
            cnt += 1
            if i & 1 == 0:
                i >>= 1
            else:
                i *= 3
                i += 1
        return cnt

    cc = CC('my_module')
    @cc.export('main', 'void(i8)')
    def main(n):
        acc = 0
        for i in prange(1, n + 1):
            acc += collatz(i)
            acc %= 1000000007
        print(acc)
    cc.compile()
    exit()

if __name__ == '__main__':
    from my_module import main
    main(int(input()))