斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……

即正整数数列，数字逐渐变大，从第三个数开始，当前数是前2个数之和。

Python版斐波那契代码

import time


def fibonacci(n: int):
    if not isinstance(n, int):
        return "参数必须是整数型！"
    if n <= 0:
        return []
    elif n == 1:
        return [0]
    elif n == 2:
        return [0, 1]
    else:
        result = [0, 1]
        for i in range(2, n):
            result.append(result[i - 1] + result[i - 2])
        return result


if __name__ == "__main__":
    t1 = time.time()
    table = (fibonacci(480000))
    t2 = time.time()
    print(t2 - t1)

输出结果如下：

4.69525814056396

注意，47万次斐波那契的数字非常非常大了！在我的电脑上跑49万次会报下面这种错：

进程已结束，退出代码为 137 (interrupted by signal 9: SIGKILL)

Go版斐波那契代码

package main

import (
	"fmt"
	"math/big"
	"time"
)

func Fibonacci1(n uint) (res []uint64) {
	res = make([]uint64, n)
	switch n {
	case 0:
		return
	case 1:
		res[0] =0
	case 2:
		res[0] =0
		res[1] = 1
	default:
		res[0] = 0
		res[1] = 1
		for i := uint(2); i < n; i++ {
			res[i] = res[i-1]+res[i-2]
		}
	}
	return
}

func main() {
	t := time.Now()
	table := Fibonacci(478000)
	tm := time.Since(t)
	fmt.Println(tm)
	fmt.Println(table[len(table)-1])
}

然后一执行，发现不对头，结果不对！原来是结算结果数字太大，远远超出uint64能表示的最大值了！我晕！！

在python中从来不用担心这一点，在学习go的时候必须得考虑数据会不会越界的问题！！

Go版斐波那契代码(数值不越界)

package main

import (
	"fmt"
	"math/big"
	"time"
)


func Fibonacci(n uint) (res []*big.Int) {
	res = make([]*big.Int, n)
	switch n {
	case 0:
		return
	case 1:
		res[0] = big.NewInt(0)
	case 2:
		res[0] = big.NewInt(0)
		res[1] = big.NewInt(1)
	default:
		res[0] = big.NewInt(0)
		res[1] = big.NewInt(1)
		for i := uint(2); i < n; i++ {
			t := new(big.Int)
			res[i] = t.Add(res[i-1], res[i-2])
		}
	}
	return
}


func main() {
	t := time.Now()
	table := Fibonacci2(470000)
	tm := time.Since(t)
	fmt.Println(tm)
	fmt.Println(table[len(table)-1])
}

输出结果如下：

3.629813036s

跑下来速度和python差不多……

甚至python可以跑48万次，go跑48万次就崩了，提示信息如下：

进程 已完成，退出代码为 137 (interrupted by signal 9: SIGKILL)

这样的代码和python原理是一样的，计算出一条数据动态分配它占用的空间，再将其内存地址保存到数组中，这种情况下并不能发挥出静态语言的优势。

总结

首先，要更加注意数据底层的存储结构，千万不要犯数据越界的错误！

其次，在保存大量计算结果的场景，预申请足够的空间比动态申请空间效率高很多！

请留意下面这两句代码：

res = make([]uint64, n)
res = make([]*big.Int, n)