LoginSignup
4
2

More than 3 years have passed since last update.

@yosgspec(YOS G-spec)

なんか違うフィボナッチ関数とかメモ化とかそのベンチとか[Lisp,HSP,Python,C#,VB,JS]

Last updated at Posted at 2019-08-01

本編

ぼんやりWikipediaの定義を眺めながらフィボナッチ数列を求める関数を書いていたら一般的なフィボナッチ関数とは違う関数を書いていました。

CommonLisp
(defun fibFake(n &optional (a 0) (b 1))
    (if(<= n 0)
        a
        (fibFake (1- n) b (+ a b))))

これは問題なく結果を出力します。

(format t "~d~%" (fibFake 40))
;102334155
;sbcl 0ms

ループでフィボナッチ数列を求めるアプローチでもこんな感じになるのかな?

ちなみに一般的なやつはこれ。

(defun fib(n)
    (if(< n 2)
        n
        (+(fib(- n 2)) (fib(1- n)))))

(format t "~d~%" (fib 40))
;102334155
;sbcl 2188ms

再帰での関数呼び出し回数が非常に多くなるのでよくベンチマークに使われている印象です。

次はフィボナッチ関数のメモ化を実装して高速化してみます。
キャッシュにはハッシュテーブルが使われることが多いようです。

ということで過程をすっ飛ばして実装。

(defparameter fibMemo 
    (let ((memo (make-hash-table :test #'equal)))
        (labels((fib(n)
            (if(cadr(multiple-value-list(gethash n memo)))
                (gethash n memo)
                (let ((result (if(< n 2)
                        n
                        (+(fib(- n 2))(fib(1- n))))))
                    (setf (gethash n memo) result)
                    result))))
            #'fib)))

(format t "~d~%" (funcall fibMemo 40))
;102334155
;fibMemo: 0ms

キャッシュするハッシュテーブルはクロージャに閉じ込めて外部からは触れないようにして、クロージャの中で生成した関数をリターン。

ちなみにCommon LispはLisp2であるので関数と変数が明確に区別されます。
変数に代入した関数は(funcall)や(apply)を通さないとアクセスできないので注意が必要です。
#'の記号の意味はシンボル化(評価させない)して関数オブジェクトとして評価する、です。

※追記:
@htsignさんより、メモ化関数について改善案を頂きました。
後述の実装も全てそれで書き換えています。
CL的にはfuncallから解放されるのが大きいのでは。

(defun fibMemo(n)
    (let ((memo (make-hash-table :test #'equal)))
        (labels((fib(n)
            (if(cadr(multiple-value-list(gethash n memo)))
                (gethash n memo)
                (let ((result (if(< n 2)
                        n
                        (+(fib(- n 2))(fib(1- n))))))
                    (setf (gethash n memo) result)
                    result))))
            (fib n))))

(format t "~d~%" (fibMemo 40))

ベンチマーク

各言語でのfib(0)からfib(38)の表示にかかる時間(偽・真・メモ化)を比較しました。
fibresult.png

fib(38) command fibFake fibNormal fibMemo
HSP3 hsp3cl 27ms 52824ms 26ms
Python3 py -3 24ms 34226ms 27ms
C#Interactive csi 27ms 3881ms 23ms
CommonLisp sbcl 29ms 2111ms 34ms
Python3 pypy3 25ms 1387ms 26ms
JavaScript node 36ms 1198ms 29ms
CommonLisp wx86cl64 0ms 1022ms 0ms
C# csc 6ms 673ms 25ms
VisualBasic vbc 24ms 652ms 31ms

この表で言えることはいかに普通のフィボナッチ関数が無駄な処理を挟んでいるのかということでしょうか。
言語間の時間差については順当ですね。

実装

以下、各言語の全実装です。

CommonLisp

(defun fibFake(n &optional (a 0) (b 1))
    (if(<= n 0)
        a
        (fibFake (1- n) b (+ a b))))

(defun fib(n)
    (if(< n 2)
        n
        (+(fib(- n 2)) (fib(1- n)))))

(defun fibMemo(n)
    (let ((memo (make-hash-table :test #'equal)))
        (labels((fib(n)
            (if(cadr(multiple-value-list(gethash n memo)))
                (gethash n memo)
                (let ((result (if(< n 2)
                        n
                        (+(fib(- n 2))(fib(1- n))))))
                    (setf (gethash n memo) result)
                    result))))
            (fib n))))

(let ((sw (get-internal-real-time)))
    (dotimes(i (1+ 38)) (format t "fib(~d)=~d~%" i (fibFake i)))
    (format t "fibFake: ~dms~%~%"
        #+sbcl (- (get-internal-real-time) sw)
        #+ccl (/(- (get-internal-real-time) sw)1000)
    )
)
(let ((sw (get-internal-real-time)))
    (dotimes(i (1+ 38)) (format t "fib(~d)=~d~%" i (fib i)))
    (format t "fib: ~dms~%~%"
        #+sbcl (- (get-internal-real-time) sw)
        #+ccl (/(- (get-internal-real-time) sw)1000)
    )
)
(let ((sw (get-internal-real-time)))
    (dotimes(i (1+ 38)) (format t "fib(~d)=~d~%" i (fibMemo i)))
    (format t "fibMemo: ~dms~%~%"
        #+sbcl (- (get-internal-real-time) sw)
        #+ccl (/(- (get-internal-real-time) sw)1000)
    )
)
(quit)

HSP3

#runtime "hsp3cl"
#cmpopt varinit 1
#define mygettime ((gettime(4)*60+gettime(5))*60+gettime(6))*1000+gettime(7)

#module @fibFake
#defcfunc local fibFake int n,int a,int b
    if n<=0: return a
    return fibFake(n-1,b,a+b)
#define global ctype fibFake(%1,%2=0,%3=1) fibFake@@fibFake(%1,%2,%3)
#global

#module
#defcfunc fib int n
    if n<2: return n
    return fib(n-2)+fib(n-1)
#global

dim memo@@fibMemo
#module @fibMemo
#defcfunc fibMemo int n
    if n<length(memo):if 0!memo(n): return memo(n)
    if n<2 {result=n}
    else {result=fibMemo(n-2)+fibMemo(n-1)}
    memo(n)=result+1
    return result
#global

sw=mygettime
repeat 38+1: mes "fib("+cnt+")="+fibFake(cnt): loop
mes "fibFake: "+(mygettime-sw)+"ms"

sw=mygettime
repeat 38+1: mes "fib("+cnt+")="+fib(cnt): loop
mes "fib: "+(mygettime-sw)+"ms"

sw=mygettime
repeat 38+1: mes "fib("+cnt+")="+fibMemo(cnt): loop
mes "fibMemo: "+(mygettime-sw)+"ms"

Python3

from time import time

def fibFake(n,a=0,b=1):
    return (
        a if n<=0 else
        fibFake(n-1,b,a+b))

def fib(n):
    return (
        n if n<2 else
        fib(n-2)+fib(n-1))

def fibMemo(n):
    memo=dict()
    def fib(n):
        if n in memo:
            return memo[n]
        else:
            result=(
                n if n<2 else
                fib(n-2)+fib(n-1))
            memo[n]=result
            return result
    return fib(n)

sw=time();
for i in range(38+1): print(f"fib({i})={fibFake(i)}")
print(f"fibFake: {(time()-sw)*1000}ms\n")

sw=time();
for i in range(38+1): print(f"fib({i})={fib(i)}")
print(f"fib: {(time()-sw)*1000}ms\n")

sw=time();
for i in range(38+1): print(f"fib({i})={fibMemo(i)}")
print(f"fibMemo: {(time()-sw)*1000}ms\n")

VisualBasic.NET

Option Strict On
Option Infer On
Imports System.Diagnostics
Imports System.Collections.Generic

Module Program
    Function fibFake(n As Integer,Optional a As Integer=0,Optional b As Integer=1) As Integer
        Return If(n<=0,
            a,
            fibFake(n-1,b,a+b))
    End Function

    Function fib(n As Integer) As Integer
        Return If(n<2,
            n,
            fib(n-2)+fib(n-1))
    End Function

    Function fibMemo(_n As Integer) As Integer
        Dim memo As New Dictionary(Of Integer,Integer)()
        Dim fib As Func(Of Integer,Integer)=Function(n)
            If memo.ContainsKey(n) Then Return memo(n)
            Dim result=If(n<2,
                n,
                fib(n-2)+fib(n-1))
            memo.Add(n,result)
            Return result
        End Function
        Return fib(_n)
    End Function

    Sub Main()
        Dim sw As New Stopwatch()

        sw.Reset()
        sw.Start()
        For i=0 To 38
            Console.WriteLine($"fib({i})={fibFake(i)}")
        Next
        Console.WriteLine($"fibFake: {sw.ElapsedMilliseconds} ms{vbLf}")

        sw.Reset()
        sw.Start()
        For i=0 To 38
            Console.WriteLine($"fib({i})={fib(i)}")
        Next
        Console.WriteLine($"fib: {sw.ElapsedMilliseconds} ms{vbLf}")

        sw.Reset()
        sw.Start()
        For i=0 To 38
            Console.WriteLine($"fib({i})={fibMemo(i)}")
        Next
        Console.WriteLine($"fibMemo: {sw.ElapsedMilliseconds} ms{vbLf}")
    End Sub
End Module

C#

using System;
using System.Diagnostics;
using System.Collections.Generic;

static class Program{
    static int fibFake(int n,int a=0,int b=1){
        return n<=0?
            a:
            fibFake(n-1,b,a+b);
    }

    static int fib(int n){
        return n<2?
            n:
            fib(n-2)+fib(n-1);
    }

    static int fibMemo(int _n){
        var memo=new Dictionary<int,int>();
        int fib(int n){
            if(memo.ContainsKey(n)) return memo[n];
            var result=n<2?
                n:
                fib(n-2)+fib(n-1);
            memo.Add(n,result);
            return result;
        }
        return fib(_n);
    }

    static void Main(){
        var sw=new Stopwatch();

        sw.Reset();
        sw.Start();
        for(int i=0;i<=38;i++){
            Console.WriteLine($"fib({i})={fibFake(i)}");
        }
        Console.WriteLine($"fibFake: {sw.ElapsedMilliseconds}ms\n");

        sw.Reset();
        sw.Start();
        for(int i=0;i<=38;i++){
            Console.WriteLine($"fib({i})={fib(i)}");
        }
        Console.WriteLine($"fib: {sw.ElapsedMilliseconds}ms\n");

        sw.Reset();
        sw.Start();
        for(int i=0;i<=38;i++){
            Console.WriteLine($"fib({i})={fibMemo(i)}");
        }
        Console.WriteLine($"fibMemo: {sw.ElapsedMilliseconds}ms\n");
    }
}

C#Intetractive

int fibFake(int n,int a=0,int b=1){
    return n<=0?
        a:
        fibFake(n-1,b,a+b);
}

int fib(int n){
    return n<2?
        n:
        fib(n-2)+fib(n-1);
}

int fibMemo(int _n){
    var memo=new Dictionary<int,int>();
    int fib(int n){
        if(memo.ContainsKey(n)) return memo[n];
        var result=n<2?
            n:
            fib(n-2)+fib(n-1);
        memo.Add(n,result);
        return result;
    }
    return fib(_n);
}

var sw=new Stopwatch();

sw.Reset();
sw.Start();
for(int i=0;i<=38;i++) Console.WriteLine($"fib({i})={fibFake(i)}");
Console.WriteLine($"fibFake: {sw.ElapsedMilliseconds}ms\n");

sw.Reset();
sw.Start();
for(int i=0;i<=38;i++) Console.WriteLine($"fib({i})={fib(i)}");
Console.WriteLine($"fib: {sw.ElapsedMilliseconds}ms\n");

sw.Reset();
sw.Start();
for(int i=0;i<=38;i++) Console.WriteLine($"fib({i})={fibMemo(i)}");
Console.WriteLine($"fibMemo: {sw.ElapsedMilliseconds}ms\n");

TypeScript

"use strict";

function fibFake(n:number,a:number=0,b:number=1):number{
    return n<=0?
        a:
        fibFake(n-1,b,a+b);
}

function fib(n:number):number{
    return n<2?
        n:
        fib(n-2)+fib(n-1);
}

function fibMemo(n:number):number{
    const memo:Map<number,number>=new Map();
    return function fib(n:number):number{
        if(memo.has(n)) return memo.get(n);
        var result=n<2?
            n:
            fib(n-2)+fib(n-1);
        memo.set(n,result);
        return result;
    }(n);
}

console.time("fibFake");
for(let i=0;i<=38;i++) console.log(`fib(${i})=${fibFake(i)}`);
console.timeEnd("fibFake");
console.log();

console.time("fib");
for(let i=0;i<=38;i++) console.log(`fib(${i})=${fib(i)}`);
console.timeEnd("fib");
console.log();

console.time("fibMemo");
for(let i=0;i<=38;i++) console.log(`fib(${i})=${fibMemo(i)}`);
console.timeEnd("fibMemo");
console.log();

JavaScript

"use strict";

function fibFake(n,a=0,b=1){
    return n<=0?
        a:
        fibFake(n-1,b,a+b);
}

function fib(n){
    return n<2?
        n:
        fib(n-2)+fib(n-1);
}

function fibMemo(n){
    const memo=new Map();
    return function fib(n){
        if(memo.has(n)) return memo.get(n);
        var result=n<2?
            n:
            fib(n-2)+fib(n-1);
        memo.set(n,result);
        return result;
    }(n);
}

console.time("fibFake");
for(let i=0;i<=38;i++) console.log(`fib(${i})=${fibFake(i)}`);
console.timeEnd("fibFake");
console.log();

console.time("fib");
for(let i=0;i<=38;i++) console.log(`fib(${i})=${fib(i)}`);
console.timeEnd("fib");
console.log();

console.time("fibMemo");
for(let i=0;i<=38;i++) console.log(`fib(${i})=${fibMemo(i)}`);
console.timeEnd("fibMemo");
console.log();

OCaml

@htsignさんよりコメントに実装を頂きました。

4
2
14

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
Sign upLogin
4
2