早くエンジニアになりたい

masatany's memorandum

Rubyでもフィボナッチ数を計算してみる

先日、ElixirからRustのプログラムを呼び出してフィボナッチ数の計算を高速化してみたので、今度はRubyを高速化してみます。

環境

  • マシン

    • Microsoft Windows 10 Home
    • Intel64 Family 6 Model 78 Stepping 3 GenuineIntel ~2300 Mhz
    • 3,935 MB

  • Ruby

    • ruby 2.3.1p112 (2016-04-26 revision 54768) [x64-mingw32]

  • Rust

    • rustc 1.9.0 (e4e8b6668 2016-05-18)
    • cargo 0.10.0-nightly (10ddd7d 2016-04-08)

検証したソースコード

Elixirの時同様、どちらの言語もまだまだ初学者レベルなので、細かいところがおかしい場合はご指摘願います。 また、「こうした方が早くなる」等のアドバイスも非常に助かりますので、お時間があればご教示願います。

fibonacci.rb

require "ffi"
require 'benchmark'

module Fib
  extend FFI::Library
  ffi_lib 'lib/fib.dll'
  attach_function :fib, [:uint], :uint
end

def fibonacci(n)
  return n if n <= 1
  fibonacci(n - 1) + fibonacci(n - 2)
end

0.upto(ARGV[0].to_i) do |num|
  ruby_result = Benchmark.realtime do
    fibonacci(num)
  end
  rust_result = Benchmark.realtime do
    Fib.fib(num)
  end
  puts format("%2d, %.9f, %.9f", num, ruby_result, rust_result)
end

lib.rs

#[no_mangle]  //関数名をマングリングさせないようにする
pub extern fn fibonacci(n: u32) -> u32 {
    match n {
        0 => 0,
        1 => 1,
        _ => fibonacci(n-1) + fibonacci(n-2)
    }
}

Cargo.toml

[package]
name = "fib"
version = "0.1.0"
authors = ["k-masatany"]

[dependencies]

[lib]
name = "fib"
crate-type = ["dylib"]

rustはreleaseで最適化してビルドしています。

結果

f:id:k_masatany:20160801230259p:plain * 画像が大きすぎて文字がつぶれました。青い棒がRubyのみ、赤い棒（見にくい）がRust呼び出し版です。

まとめ

  • Rubyはとても書きやすい。Rustは少しレベルアップしました？（マッチング使ってみました）
  • やっぱりRustはやい。

Elixirでフィボナッチ数を計算してみる

プログラミング Elixir Rust

このごろ流行のruby風味の関数型言語「Elixir」でフィボナッチ数を計算してみました。
そして、これまた、このごろ流行の関数型言語Rustで実装したフィボナッチ数を求めるプログラムを呼び出して、速度比較をしてみました。 とくに意味はありません。

環境

  • マシン

    • Microsoft Windows 10 Home
    • Intel64 Family 6 Model 78 Stepping 3 GenuineIntel ~2300 Mhz
    • 3,935 MB

  • Elixr

    • Erlang/OTP 18 [erts-7.2.1] [64-bit] [smp:4:4] [async-threads:10]
    • Elixir 1.3.1

  • Rust

    • rustc 1.9.0 (e4e8b6668 2016-05-18)
    • cargo 0.10.0-nightly (10ddd7d 2016-04-08)

検証したソースコード

どちらの言語もまだまだ初学者レベルなので、細かいところがおかしい場合はご指摘願います。 また、「こうした方が早くなる」等のアドバイスも非常に助かりますので、お時間があればご教示願います。

fibonacci.ex

defmodule Fibonacci do
  def start do
    [num_string|_] = System.argv
    num = String.to_integer(num_string)
    exec_cmd = "lib/rust_fib.exe " <> num_string
    IO.puts "Elixir fibonacci"
    {result_elixir, :ok} = :timer.tc(Fibonacci, :fibonacci_elixir, [num])
    IO.puts "#{result_elixir/1000}ms"
    IO.puts "Rust   fibonacci"
    {result_rust, :ok} = :timer.tc(Fibonacci, :fibonacci_rust, [exec_cmd])
    IO.puts "#{result_rust/1000}ms"
  end

  # Elixirのみで計算する場合
  def fibonacci_elixir(num) do
    IO.puts fibonacci(num)
  end
  
  def fibonacci 0 do 0 end
  def fibonacci 1 do 1 end
  def fibonacci(num) when (is_integer num) and (num > 0) do
    fibonacci(num - 1) + fibonacci(num - 2)
  end


  # Rustプログラムを呼び出す場合
  def fibonacci_rust(exec_cmd) do
    port = Port.open({:spawn, exec_cmd}, [:binary])
    Port.command(port, "")

    receive do
      {^port, {:data, result}} -> IO.puts(String.trim(result))
    end
  end
end

Fibonacci.start

rust_fib.rs

use std::env;

fn calc_fibonacci(n: u32) -> u32 {
    if n <= 1 {
        n
    } else {
        calc_fibonacci(n - 1) + calc_fibonacci(n - 2)
    }
}

fn fibonacci(mut argv: env::Args) -> Result<u32, String> {
    let arg1 = try!(argv.nth(1).ok_or("数字を１つ指定してください。".to_owned()));
    let n = try!(arg1.parse::<u32>().map_err(|err| err.to_string()));
    Ok(calc_fibonacci(n))
}

fn main() {
    match fibonacci(env::args()) {
        Ok(n) => println!("{}", n),
        Err(err) => println!("{}", err),
    }
}

結果

f:id:k_masatany:20160731164719p:plain ※ ms単位にしたため、us単位の数値が消えて0msになっています。すみません。
※ 与える数値が低い範囲（0～25くらいまで）は速度の数値が安定しなかったので、何度か計測して頻度の高い数値を使っています。
※ 画像出力の際に表の縦線が消えました。

  • 0から26までは、Elixirの計算速度の方が早いようです。と言っても、Elixir+Rustが遅いのではなく、外部プログラムを呼び出して結果を受けるまでのオーバーヘッドが必ず入ってしまうので遅くなる感じですね。
  • 27で双方が肩を並べ、30から外部プログラムの恩恵を受けられるようになりました。
  • 45では、Elixir+Rustの方が10倍早い結果が出ています。

まとめ

  • Elixirは書きやすい。Rustは少し取っつきにくかったです。
  • Elixirが遅いときは、重い処理を簡潔な外部プログラムで実装してPortで呼び出すという手もある。
  • 外部プログラムの呼び出しに一定のコストがかかるので、Elixirの実行速度が比較的遅いからと言って、むやみやたらに外部プログラムを呼ぶものではないと感じました。

Raspberry PiでPython3を使う

プログラミング RaspberryPi

仕事でPython3系を使うことになり、趣味で使っているRaspberry PiでもPython3が使いたいので、インストールしました。

環境

Raspberry Pi2 Model B + raspbian

$ cat /etc/debian_version
8.0

インストール手順

インストール手順といっても最新のソースを持ってきてMakeしてインストールするだけです。

$ cd /usr/local/src/
$ sudo wget https://www.python.org/ftp/python/3.5.2/Python-3.5.2.tgz
$ sudo tar xzvf Python-3.5.2.tgz
$ cd Python-3.5.2/
# ソースを落としてきます。/usr/local/src/で作業するとsudoが必要なので、
# 気になる方は/home/の下で作業するといいです。
# その場合はsudoは不要です。

$ ./configure
# デフォルトでは/usr/local/bin/にインストールされるので、
# 場所を変えたい場合はprefixオプションを付けます。
# 私は趣味なので気にせずデフォルトです。
# ./configure --prefix=/your/python/install/path

$ make
# スペックの問題でかなり時間がかかるので、気長に待ちます。私は10分以上かかりました。

$ sudo make install
# prefixオプションでroot権限が不要な場所を指定しているのならsudoは不要です。

pipもインストール

最近のPythonはpipも一緒にインストールしてくれるはずなのですが・・・。

Ignoring ensurepip failure: pip 8.1.1 requires SSL/TLS

はい、ごめんなさい。 OpenSSLをインストールして、改めてpipをインストール。

$ sudo apt-get install libssl-dev
$ sudo make install

動作確認

$ python -V
Python 2.7.9
$ pip -V
pip 1.5.6 from /usr/lib/python2.7/dist-packages (python 2.7)

$ python3 -V
Python 3.5.2
$ pip3 -V
pip 8.1.1 from /usr/local/lib/python3.5/site-packages (python 3.5)

Pythonもpipも問題なくインストールできました。 仕事も趣味も3系に揃えられて、仕様の違いに悩まされずに済みそうです。