More than 5 years have passed since last update.

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

Last updated at 2019-08-02Posted 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)の表示にかかる時間(偽・真・メモ化)を比較しました。

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さんよりコメントに実装を頂きました。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up