【プログラミング言語速度比較】Collatz数列ベンチマークを言語別比較しよー!
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#で計測したところ、10^4,5,6,7の順に89,109,487,4825msでした(三回計測の最小値) 最後以外Javaより若干速いみたいですね
— 白緑@(計算機(工|科)|数)学 (@White_Green2525) 2020年7月18日
コードはgistに置きました https://t.co/5g75F87SA5
C++の編集版を追加しました。ありがとうございます!
Python と PyPy を追加しました。arasius さん、ありがとうございます!
愚直に書いた場合のPython3,PyPy3のコードです。
— arasius (@arasius1) 2020年7月18日
PyPyでは10^7まで計測出来ましたが、Pythonは10^6の時点で実行時間が10秒を超えてしまいました・・・https://t.co/YIWKKKaynX
Crystal を追加しました。yuruhiya さん、ありがとうございます!
https://t.co/C4TQVxSEC6
— yuruhiya (@yuruhiya) 2020年7月18日
Crystalで書きました。
実行時間は15, 48, 345, 3756msで、C++とJavaの間みたいです。
Golang を追加しました。
JavaScript を追加しました。
Fortran を追加しました。jj1gui さん、ありがとうございます!
— JJ1GUJ (@jj1guj) 2020年7月18日
Ruby を追加しました。KowerKoint さん、ありがとうございます!
https://t.co/gYreGDWy35
— KowerKoint2010 (@KowerKoint2010) 2020年7月18日
Ruby書きました
必要なら使ってください...
Rust だけ非負整数だったので、Rust の isize 版、C++の unsigned 版も作りました。
D 言語を追加しました。lempiji さん、ありがとうございます!
D言語で書いてみました。既存回答のうちRustだけ符号なし整数なので揃えたつもりなんですが、結果Rustより速くなってしまい、、https://t.co/LysXgjmpTS
— lempiji@思秋期 (@lempiji) 2020年7月18日
Bash を追加しました。KowerKoint さん、ありがとうございます!
https://t.co/YuFBJKGgvI
— KowerKoint2010 (@KowerKoint2010) 2020年7月18日
Bashですが超遅いです...
Swift を追加しました。
https://t.co/ctJIe0ufCU
— matsumo (@ta_matsumo) 2020年7月18日
↑ベンチマーク大好きなのでSwiftで書いてみました。
JavaScriptのコードをTypeScriptとして投げてみるのも面白そうですね。
Objective−Cでも書こうと思いましたが、需要がなさそうなのでやめましたwww
Objective-C を追加しました。matsumo さん、ありがとうございます!
https://t.co/AraX83eeca
— matsumo (@ta_matsumo) 2020年7月18日
↑需要があったようなのでObjective-Cでも書いてみました。
クラスを使用しない実装だとメッセージ式を使わないので、実はC言語としても動きますwww
C を追加しました。mikhail さん、fujitanozomu さん、ありがとうございます! https://twitter.com/Mikhail_chan/status/1284665518524256256?s=20
> 総合的にはClang(unsigned)が最速みたいです。
— fujita nozomu (@fujitanozomu) 2020年7月19日
clang の出力コードに気になった点があったので小変更してみました。https://t.co/aUYg3Yt630
いくらか改善するようです。
Bc を追加しました。fujitanozomu さん、ありがとうございます!
bc(https://t.co/Aqvux9kIyl)で書いてみました。https://t.co/DAm8451pji
— fujita nozomu (@fujitanozomu) 2020年7月19日
ideoneで実行して10**4で1秒程度掛かるようなのでbashよりは速い感じですね。
Perl を追加しました。fujitanozomu さん、ありがとうございます!
Perlで書いてみました。bc よりは速い感じです。https://t.co/mmhF7ZdE0t
— fujita nozomu (@fujitanozomu) 2020年7月19日
Vim を追加しました。KowerKoint さん、ありがとうございます!
ごめんなさい
— KowerKoint2010 (@KowerKoint2010) 2020年7月19日
practice contestへの提出を共有しようとしたらまだコンテスト時間が続いてるようでした
これなら見えますか?https://t.co/Z4FUfVZIyR
Php と AWK と Lua と Pascal を追加しました。fujitanozomu さん、本当にありがとうございます!!
PHPhttps://t.co/dM8ddePbRz
— fujita nozomu (@fujitanozomu) 2020年7月19日
Perlより速い
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 は特殊ですね。どっちにしろ最速クラスなのには変わりないです。
準最速クラス
- Nim
- Nim(uint)
- Fortran
- D(GDC)
- Objective-C
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 より遅い程度で動作しますね。
ビリ
- JavaScript
- Common Lisp
- Php
- Cython
- Clojure
- Scheme
- Python
- Lua
- Perl
ダントツで遅く、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()))