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

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

```cl:CommonLisp
(defun fibFake(n &optional (a 0) (b 1))
	(if(<= n 0)
		a
		(fibFake (1- n) b (+ a b))))
```
これは問題なく結果を出力します。

```cl
(format t "~d~%" (fibFake 40))
;102334155
;sbcl 0ms
```
ループでフィボナッチ数列を求めるアプローチでもこんな感じになるのかな?

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

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

(format t "~d~%" (fib 40))
;102334155
;sbcl 2188ms
```
再帰での関数呼び出し回数が非常に多くなるのでよくベンチマークに使われている印象です。

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

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

```cl
(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](https://qiita.com/yosgspec/items/f93e1b0996bcc5c810fd#comment-aeca5b4a43f17b5c302a)さんより、メモ化関数について改善案を頂きました。
後述の実装も全てそれで書き換えています。
CL的にはfuncallから解放されるのが大きいのでは。

```cl
(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](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/147573/5500a42a-564a-30d1-e9bc-2cfe93dbaa18.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
```cl
(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
```cpp
#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
```py
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
```vb
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<span>#</span>
```cs
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<span>#</span>Intetractive
```cs
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
```ts
"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
```js
"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さんよりコメントに実装を頂きました。](https://qiita.com/yosgspec/items/f93e1b0996bcc5c810fd#comment-aeca5b4a43f17b5c302a)