幽默Kotlin之长串表

背景动机

众所周知，Kotlin 内置的不可变列表（listOf）实际上只是包了一下可变列表，因此每次添加元素都需要复制整个列表。通过以下代码可以观测到明显的性能差异：

import kotlin.time.measureTime

fun buildBuiltinImmutableList(): List<Int> {
    var xs = listOf<Int>();
    for (i in 0..10000) {
        xs += i  // 每次操作都要复制整个列表
    }
    return xs
}

fun buildBuiltinMutableList(): List<Int> {
    val xs = mutableListOf<Int>();
    for (i in 0..10000) {
        xs.add(i)  // 直接修改，无需复制
    }
    return xs
}


fun main() {
    val timeToBuildBuiltinImmutableList = measureTime {
        buildBuiltinImmutableList()
    }
    val timeToBuildBuiltinMutableList = measureTime {
        buildBuiltinMutableList()
    }
    println("构建内置不可变列表耗时：$timeToBuildBuiltinImmutableList")
    println("构建内置可变列表耗时：$timeToBuildBuiltinMutableList")

    val builtinImmutableList = buildBuiltinImmutableList()
    val builtinMutableList = buildBuiltinMutableList()

    val timeToQueryBuiltinImmutableList = measureTime {
        builtinImmutableList.find { it == 99999 }
    }
    val timeToQueryBuiltinMutableList = measureTime {
        builtinMutableList.find { it == 99999 }
    }
    println("遍历内置不可变列表耗时：$timeToQueryBuiltinImmutableList")
    println("遍历内置可变列表耗时：$timeToQueryBuiltinMutableList")
}

在我的机器上运行结果：

构建内置不可变列表耗时：144.462443ms
构建内置可变列表耗时：573.612us
遍历内置不可变列表耗时：873.863us
遍历内置可变列表耗时：741.721us

拉完了。我们知道Haskell的链表在头部添加元素时速度很快，所以我们快速在Kotlin实现一个。

sealed interface LinkedList
data class Cons(val head: Int, val tail: LinkedList) : LinkedList
object Nil : LinkedList
// 等价于 Haskell 的 data LinkedList = Nil | Cons Int LinkedList

infix fun Int.cons(xs: LinkedList) = Cons(this, xs)

fun buildImmutableList(): LinkedList {
    var xs: LinkedList = Nil
    for (i in 0..10000) {
        xs = i cons xs  // 头部添加，无需复制
    }
    return xs
}

构建内置不可变列表耗时：110.702514ms
构建内置可变列表耗时：1.272172ms
构建不可变链表耗时：1.932318ms

可以看到性能与可变列表相当，很不错！

那么遍历性能如何呢？

// 会出现栈溢出
fun LinkedList.find(pred: (Int) -> Boolean): Int? = when (this) {
    is Nil -> null
    is Cons -> if (pred(this.head)) head else tail.find(pred)
}

fun LinkedList.find(pred: (Int) -> Boolean): Int? = when (this) { 
tailrec fun LinkedList.find(pred: (Int) -> Boolean): Int? = when (this) { 

虽然稍差一些，但仍然可以接受。

遍历内置不可变列表耗时：1.191294ms
遍历内置可变列表耗时：739.765us
遍历不可变链表耗时：2.041619ms

但总所周知，在链表中尾部添加元素是非常耗时的，让我们来测试一下。

infix fun Int.snoc(xs: LinkedList): LinkedList = when (xs) {
    is Nil -> Cons(this, Nil)
    is Cons -> Cons(xs.head, this snoc xs.tail)  // 递归复制整个链表
}
fun buildImmutableListSnoc(): LinkedList {
    var xs: LinkedList = Nil
    for (i in 0..10000) {
        xs = i snoc xs  // 每次都要复制整个链表
    }
    return xs
}

坏辣！这比直接复制还要慢三倍！

构建内置不可变列表耗时：104.879966ms
构建内置可变列表耗时：710.013us
构建不可变链表耗时：911.997us
构建不可变链表（尾部添加）耗时：323.870489ms

我们能否实现一个既支持快速头部添加又支持快速尾部添加的不可变列表呢？

差异列表（DList）

当然可以，这就是所谓的差异列表（Difference List）。

fun compose(
    f: (LinkedList) -> LinkedList,
    g: (LinkedList) -> LinkedList
): (LinkedList) -> LinkedList = { xs -> f(g(xs)) }

data class DList(val f: (LinkedList) -> LinkedList)
val DNil = DList({ it })

infix fun Int.cons(xs: DList) = DList(compose({ this cons it}, xs.f))
infix fun DList.append(other: DList): DList = DList(compose(f, other.f))
infix fun DList.snoc(x: Int): DList = this append (x cons DNil)

fun buildDList(): DList {
    var xs: DList = DNil
    for (i in 0..10000) {
        xs = i cons xs  // 头部添加
    }
    return xs
}

fun buildDListSnoc(): DList {
    var xs: DList = DNil
    for (i in 0..10000) {
        xs = xs snoc i  // 尾部添加
    }
    return xs
}

构建内置不可变列表耗时：103.096761ms
构建内置可变列表耗时：873.373us
构建不可变链表耗时：1.102246ms
构建不可变链表（尾部添加）耗时：339.708615ms
构建差异列表耗时：3.623470ms
构建差异列表（尾部添加）耗时：2.568577ms

这个结果很不错，但我们如何实际查看数据呢？

我们需要将其转换为链表并进行遍历：

fun DList.find(pred: (Int) -> Boolean): Int? = f(Nil).find(pred)

然而：

Exception in thread "main" java.lang.StackOverflowError
	at org.example.ListsKt.compose$lambda$0(Lists.kt:55)
	at org.example.ListsKt.compose$lambda$0(Lists.kt:55)
	at org.example.ListsKt.compose$lambda$0(Lists.kt:55)

这是因为在JVM上使用了显式的栈调用，导致栈溢出。Haskell能够避免这个问题，因为Haskell没有传统的栈架构，而是大量使用堆分配和指针跳转。

让我有点意外的是JS后端上是可以跑的

构建内置不可变列表耗时：578ms
构建内置可变列表耗时：0s
构建不可变链表耗时：0s
构建不可变链表（尾部添加）耗时：974ms
构建差异列表耗时：2ms
构建差异列表（尾部添加）耗时：1ms
遍历内置不可变列表耗时：0s
遍历内置可变列表耗时：0s
遍历不可变链表耗时：1ms
遍历差异列表耗时：3ms

虽然不算完美（JS可能没有很好地优化compose函数），但至少能够工作。

为了在JVM上使其工作，我们需要实现自己的求值引擎来扁平化匿名函数，可以参考scalaz.DList