斐波那契数列Kotlin的N种实现方式

前言

半年前开始接触和学习Kotlin，最近看完了两本Kotlin的书，我对Kotlin的看法是这样的：有点东西 -> 唉哟不错 -> 卧槽牛批。

虽然说是有一定的学习成本在那里，但是还是很值得的，思维和效率比起Java，提高的不是一点，而且未来如果Compose有幸占据主流的话，安卓开发Kotlin是必备技能了。对安卓开发感兴趣并想要持续深入的同学，抓紧学起来吧！

背景

网上看到很多斐波那契数列的各种语言版本，花里胡哨的亚子，但感觉不够且凑数（比如while循环和for循环，就算两种了吗 #手动狗头#），于是就心血来潮自己尝试用Kotlin写几种实现方式（PS: 最后要得到数列对象，简单的一个个打印出来不算）

Fibonacci数列定义

*斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89...
这个数列从第3项开始，每一项都等于前两项之和。*

												——来自百度百科
1
2
3
4

Kotlin编程实现

明确要求：

1. 输出一个含斐波那契数列的List对象，并打印List，不能是简单的过程打印
2. 测量计算过程的时间，并打印时间
3. 正常情况下，要计算斐波那契数列到第100位，并打印位数（普通递归方式计算到30位）

1. 简单循环方式

1.1. for循环区间

当然也可以循环列表等，也可以用while循环，原理类似，就不列举了

	fun fibonacci1_1() {
        measureNanoTime {
            val list = mutableListOf<BigInteger>()
            var x = BigInteger.ONE
            var y = BigInteger.ONE
            var z: BigInteger

            for (i in 1..100) {
                list.add(x)
                z = x
                x = y
                y += z
            }
            println("list = $list")
            println("size = ${list.size}")
        }.also{ println("cost time = $it Nano") }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

结果：

这里花费了3,944,200纳秒的时间，也就是3.9毫秒，其实是非常快的

1.2. 使用kotlin的标准函数also，简化写法

这样的好处是不用创建临时变量z来保存x了，代码简洁些，但是测试了几次发现好像是会稍微耗费多一点时间，不确定是不是其他原因

    fun fibonacci1_2() {
        measureNanoTime {
            val list = mutableListOf<BigInteger>()
            var x = BigInteger.ONE
            var y = BigInteger.ONE

            for (i in 1..100) {
                list.add(x)
                x = y.also { y += x }
            }
            println("list = $list")
            println("size = ${list.size}")
        }.also{ println("cost time = $it Nano") }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

结果：

花费了6毫秒，也挺快了

2. 递归方式

2.1 普通递归

简单递归是Fibonacci数列最常见的方式，它是根据Fibonacci数列的通项式演变来的，如下：

看代码：

    private fun fib(n: Int): BigInteger =
        when (n) {
            1 -> BigInteger.ONE
            2 -> BigInteger.ONE
            else -> fib(n - 1) + fib(n - 2)
        }


    @Test
    fun fibonacci2_1() {
        measureNanoTime{
            val list = mutableListOf<BigInteger>()
            for (i in 1..30) {
                list.add(fib(i))
            }
            println("list = $list")
            println("size = ${list.size}")
        }.also { println("cost time = $it Nano") }
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

结果：

可以看到才计算30位，但是花了104毫秒，比前面的循环法计算100位都满，而且普通递归法耗时呈指数增长，调用基数稍大还会有内存溢出风险

2.2 尾递归优化

kotlin支持尾递归优化，专门解决上述普通递归的痛点，关键字：tailrec
使用尾递归优化，函数的最后必须有调用自身，所以这里我们要做一些调整
看代码：

	private tailrec fun fib_tail(
        x: BigInteger = BigInteger.ONE,
        y: BigInteger = BigInteger.ONE,
        count: Int = 100,
        list: MutableList<BigInteger> = mutableListOf()
    ): List<BigInteger> {
        return if (count > 0) {
            fib_tail(y, x + y, count - 1, list.apply { add(x) })
        } else {
            list
        }
    }
    
	@Test
    fun fibonacci2_2() {
        measureNanoTime {
            fib_tail().also {
                println("list = $it")
                println("size = ${it.size}")
            }
        }.also { println("cost time = $it") }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

结果：

可以看到，经过尾递归优化后，计算到第100位所用的时间和我们之前使用循环法差不多，也是4毫秒左右。因为尾递归优化，转成java字节码后可以看到，其实就是编译器帮我们转换成了循环，所以它的效率是和循环方式是差不多的。

3.1 Flow方式

flow是kotlin协程库里的，需要导入以下依赖

    implementation 'org.jetbrains.kotlinx:kotlinx-coroutines-core:1.6.1'
1

看代码：

    //Flow方式
    fun fib_flow(): Flow<BigInteger> = flow {
        var x = BigInteger.ONE
        var y = BigInteger.ONE
        var z: BigInteger

        while (true) {
            emit(x)
            z = x
            x = y
            y += z
        }
    }

    //调用flow生成数列
    @Test
    fun fibonacci3_1() {
        runBlocking {
            measureNanoTime {
                fib_flow()
                    .take(100)  //计算100次
                    .toList()   //末操作符，在此时才执行和收集Flow
                    .also {
                        println("list = $it")
                        println("size = ${it.size}")
                    }
            }.also { println("cost time = $it") }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

结果：

这里用了14毫秒左右，可还是比较可以的。注意，这里如果把计算时间放在runBlocking作用域外的话，时间会久100多毫秒，因为runBlocking函数会阻塞当前线程。

3.2. 使用also简化

    //Flow方式
    fun fib_flow(): Flow<BigInteger> = flow {
        var x = BigInteger.ONE
        var y = BigInteger.ONE

        while (true) {
            emit(x)
            x = y.also { y += x }
        }
    }

    //调用flow生成数列
    @Test
    fun fibonacci3_1() {
        runBlocking {
            measureNanoTime {
                fib_flow()
                    .take(100)  //计算100次
                    .toList()   //末操作符，在此时才执行和收集Flow
                    .also {
                        println("list = $it")
                        println("size = ${it.size}")
                    }
            }.also { println("cost time = $it") }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

可以看到只用了13毫秒左右

Sequence序列方式

Sequence对刚接触kotlin的童鞋可能比较陌生，它和List、set、map等其他的集合类有很大的不同，序列的迭代是逐个元素的迭代，而集合是整个迭代，在一些场景可以大大优化代码效率，例如查找等。

直接看代码：

    //Sequence序列方式
    fun fib_seq(): Sequence<BigInteger> {
        var x = BigInteger.ONE
        var y = BigInteger.ONE

		//生成无限序列
        return generateSequence(BigInteger.ONE) {
            x = y.also { y += x }
            x  //将x放进序列
        }
    }

    @Test
    fun fibonacci4_1(){
        measureNanoTime {
            fib_seq().take(100).toList().also {
                println("list = $it")
                println("size = ${it.size}")
            }
        }.also { println("cost time = $it") }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

结果：

16毫秒左右，也还可以

结论

Kotlin的几种生成斐波那契数列的方式里，最快的是简单的循环方式，与第一几乎并列的是尾递归优化方式，因为它的本质其实也是循环，其次是Flow方式，和Sequence序列方式，他们效率差不多，Flow稍高一些，最差的是普通递归方式，计算30位却用的时间最多。

PS最后发现其实测量计算时间应该排除掉打印List和Size的时间，排除掉之后，差不多相差3毫秒左右，这么一看，循环的效率是真的高，最后我把每个方式计算10000位，并取中间值，整理了个图，更加直观。（单位纳秒）

写在结尾

为了这篇文章，花费了半个周末，还有其他方式或者好的想法，欢迎评论或私信，一起学习进步鸭~
后续有补充的话我再更新