LoginSignup
5

More than 5 years have passed since last update.

nimで、メモ化で、フィボナッチ数列の値を計算しておく。

Last updated at Posted at 2018-01-27

nimを知ったきっかけ

たぶん2年半くらい前だと思うんだけれど、「この頃 流行りの 言語たち(他)でベンチマーク (Dart, Go, Julia, Nim, Python, Rust 他)
」というタイトルのブログ(以下、『流行りの 言語たち(他)でベンチマーク』)を目にしたことがnimを知ったきっかけだと思う。だって、

以上、なんとなくやってみたベンチマークでした。 結果を一言で表すと、
Nim速い!!RustもGoよりちょっと速い!!

なんて書かれていると、nimが気になってくるじゃない。nimという名を僕の記憶にとどめてくれたこのブログに感謝。

その後、nimの紹介記事もだいたいこんな感じでnim の速さに言及するしていることが多い。
その通り、nimの実行速度は速いのです。Cとそんなに遜色ない程度には。
コードの速度チューニングをガリガリするとか必要ない立場にいる自分としては、nimの速さは十分満足なのです。
ただ...ベンチマークブログがバズることには罪な側面もあるわけで、ちょっとnim側から(仮想的になってしまっていたgoに)罪滅ぼしをしておこうと。

ただ、nimをこれから推すなら書きやすさの点なのではないかと、僕は思う。

  ベンチマークでの実行速度でいうと、 例えば、気合の入った人の書いたrustのコードにnimが勝つのは難しいと思う(rustは、必要に応じメモリ管理もガリガリとチューニングしてくださいという言語だろうから)。もちろん、nimでも挑戦はできるんだろうけど、そのために気合を入れる必要がある。また、 数値計算ライブラリが充実しているjuliaにもnimが勝つのは結構難しそう(ライブラリのこなれ具合的な意味で)。

  それでも nimの良いところはrustやjuliaやgoよりも可読性が高いコードが書きやすいところ(注、個人差がありry..)だと思うので、僕は困らない。
  

これからのnimブログに期待すること

  他言語との比較(コードの見た目、ベンチマーク)ももちろんいいんだけれど、nimでこんな処理書いてみた的な記事が淡々と蓄積されていくといいなと思う。
  他言語との比較ポエムをたくさん書いてきた自分への自戒もこめて。といいつつ、今回もベンチマークをめぐるポエムなんだけど、以下、nimでメモ化の例をちょっと書いておくので許してね、ということで。

再帰とメモ化、それぞれ。

元ブログ『流行りの 言語たち(他)でベンチマーク』では、nim含めさまざまな言語で、42番めのフィボナッチ数列の値を『再帰』を用いて計算している。
今読み返してみると、この記事には元ネタがあったらしく、以下の方がもともと沢山の言語でフィボナッチ数列の値を『再帰』でベンチマークしてくれている。

AWK、Ada、Bash、Boo、C、C#、C++、Clojure、D、Erlang、Forth、Fortran、Go、Groovy、Haskell、Io、Java、JavaScript、Lisp、Lua、OCaml、Objective-C、PHP、Pascal、Perl、Pike、Prolog、Python、R、Ruby、Scala、Scheme、Smalltalk、Tcl でフィボナッチ数を求める処理時間を計測してみました。

出典 フィボナッチで各種言語をベンチマーク

 ...多すぎ。どうもこちらのブログの方はhaskell推しっぽく、C(gcc -O2)やGo (build)より、Hakell の方が倍以上速いとの結果が得られている。
両ブログを比べた総合ナンバーワンは何なの...というところに興味がいっちゃいそうなところなんだけど、その前に、沢山の言語で再帰を用いたコードでベンチマークすることにどのくらい意味があることなのかを問うておいても良いのではないかと僕は思う(末尾再帰の最適化のあり方とか関数呼出しのメモリ管理方式とかいろいろ言語によっての取扱いがあるわけで...)。

僕は思っただけで読み流してしまっていたんだけれど、nimにもhaskellにもちょっと遅いとやり玉に挙げられたGo使いな方が黙っていなかった。

Goで再帰使うと遅くなりますがそれが何だ』:

()先のコードは最後が末尾再帰でない再帰呼び出しなので、コールスタックがめっちゃ積まれそうです。Goが再帰呼び出しが得意でないのは、Goランタイムのスタックサイズがデフォルトが小さく、かつスタックサイズの大きさを最小にするような最適化を行わないからです。さらにいうと、Goでは末尾再帰ですら最適化されません。

なるほど。Goには末尾再帰最適化がないとは知らなかった。
末尾再帰の最速化はあったほうがよいと思うんだけど...それはそうと、『Goで再帰使うと遅くなりますがそれが何だ』のその後の以下のくだりには全く同意。

今回のプログラムをアルゴリズムで最適化するのであればメモ化をするのが手っ取り早いでしょう。O(n)になります。

memo1.go
package main

import "fmt"

var mem = make(map[int]int, 100)

func fib(n int) int {
        if n < 2 {
                return n
        }
        if m, ok := mem[n]; ok {
                return m
        }
        m := fib(n-2) + fib(n-1)
        mem[n] = m
        return m
}

func main() {
        fmt.Println(fib(42))
}

メモ化はgoではすなおに書き下せているね(当社比の読みやすさはさておき。)。

もちろん、再帰は再帰で使い所があるわけで、nimやclojure等の再帰が扱いやすい言語では必要に応じどんどん使っていけば良いんだけど。

nimで再帰とメモ化

『流行りの 言語たち(他)でベンチマーク』の再帰で書かれたnimコードは こうだった。

fibrec0.nim
proc fib(n: int): int =
    if n < 2:
      return n
    return fib(n - 2) + fib(n - 1)
echo(fib(42))

ちょっとだけnimらしく書き換えておくならば以下のような感じか。(nimは関数のreturnを省略化)

fibrec.nim
proc fib(n: int): int =
    if n < 2:  n else : fib(n - 2) + fib(n - 1)
echo fib(42)

で、O(1) なメモ化はnimではこんなふうに書く。

memofib.nim
const  num = 42 # 求める数列の「深さ」を定数として指定
var    mem : array[1..num, int] # メモ化用の配列をメモリ上に確保

#for i in 1..num: mem[i] = -1 こうした初期化は不要(メモリ確保済の数値は0で初期化されている模様)

proc fib(n : int): int = #複数のreturnがある場合は、returnを略記しない方が良いと思う。
    if n < 2 : return n
    if mem[n] > 0 : return mem[n]
    var m = fib(n-2) + fib(n-1)
    mem[n] = m #メモを記録
    return m

echo fib(num)

メモ化は、処理結果をメモする配列等を予めメモリ上に確保しておいて行うと知っておけば、
さほど難しいところはないのではないかと。

比較用にpythonのコードを『Goで再帰使うと遅くなりますがそれが何だ』 から引用させてもらう。

memofib.py
def fib(n, mem):
    if n < 2:
        return n
    if n in mem:
        return mem[n]
    m = fib(n-2, mem) + fib(n-1, mem)
    mem[n] = m #メモを記録
    return m

print(fib(42,{}))

当然ながらpythonも簡潔だね。ただ、 python版ではメモを、辞書(dict、いわゆるハッシュ)に記録していることに注意。
この程度のメモ量であれば、ハッシュでも配列でも速度にほとんど差はでないと思う。

とりあえずベンチマーク。

ベンチマークがないとだから何なの、となると思うので、
42番めのフィボナッチ数列の値の計算を『nim-再帰版』、『nim-メモ化版』、『python-メモ化版』で行ってベンチマークしておく。

手元のmacでbashのtime使った手抜き版として。

bench.sh

#!/bin/bash

echo "nim(再帰(元ネタ))"
#nim c -d:release fibrec0.nim
time  {
  ./fibrec0
}

echo "nim(再帰(if式))"
#nim c -d:release fibrec.nim
time  {
  ./fibrec
}

echo "nim(memoize)"
#nim c -d:release memofib.nim
time  {
  ./memofib
}

echo "python3(memoize)"
time  {
  python3 memofib.py
}

実行結果

bash bench.sh 3823ms  土 1/27 23:07:13 2018
nim(再帰(元ネタ))
267914296
real 0m1.890s
user 0m1.881s
sys 0m0.005s
nim(再帰(if式))
267914296
real 0m1.920s
user 0m1.911s
sys 0m0.005s
nim(memoize)
267914296
real 0m0.003s
user 0m0.001s
sys 0m0.001s
python3(memoize)
267914296
real 0m0.055s
user 0m0.042s
sys 0m0.011s
bash bench.sh 3872ms  土 1/27 23:07:25 2018
nim(再帰(元ネタ))
267914296
real 0m1.873s
user 0m1.859s
sys 0m0.006s
nim(再帰(if式))
267914296
real 0m1.871s
user 0m1.857s
sys 0m0.005s
nim(memoize)
267914296
real 0m0.007s
user 0m0.001s
sys 0m0.002s
python3(memoize)
267914296
real 0m0.076s
user 0m0.040s
sys 0m0.014s

すわなち、実行時間は概ね以下のようになっている:

『nim-再帰版』 > 1秒 > 『python-メモ化版』 > 0.01秒 ≒ 『nim-メモ化版』

おわりに。

結論は、Nimすごいね、でも、メモ化最高!でもなく、プログラム言語は手に馴染んでいるものをケースバイケースで用いていけばいいだよねということ。
ただ、Nimは慣れてくれば守備範囲は広そうだよねということで、みんなNimも書いてみようとやっぱり言っておく ;)

そして、ベンチマークは書く方も読む方も、計画的に^^; おしまい。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5