在不损失速度的情况下去除可变性

Question

我有这样的功能：

fun randomWalk(numSteps: Int): Int {
    var n = 0
    repeat(numSteps) { n += (-1 + 2 * Random.nextInt(2)) }
    return n.absoluteValue
}

这很好用，除了它使用了一个可变变量，我想尽可能使所有内容不可变，以获得更好的安全性和可读性。所以我想出了一个不使用任何可变变量的等效版本：

fun randomWalk_seq(numSteps: Int): Int =
    generateSequence(0) { it + (-1 + 2 * Random.nextInt(2)) }
        .elementAt(numSteps)
        .absoluteValue

这也能正常工作并产生相同的结果，但需要 3 倍的时间。

我是用下面的方法测的：

@OptIn(ExperimentalTime::class)
fun main() {
    val numSamples = 100000
    val numSteps = 15708
    repeat(5) {
        val randomWalkSamples: IntArray
        val duration = measureTime {
            randomWalkSamples = IntArray(numSamples) { randomWalk(numSteps) }
        }
        println(duration)
    }
}

我知道这有点老套（我本可以使用 JMH，但这只是一个快速测试 - 至少我知道 measureTime 使用单调时钟）。迭代（可变）版本的结果：

2.965358406s
2.560777033s
2.554363661s
2.564279403s
2.608323586s

正如预期的那样，第一行显示由于 JIT 的预热，第一行运行花费了更长的时间，但接下来的 4 行变化相当小。

将randomWalk替换为randomWalk_seq后：

6.636866719s
6.980840906s
6.993998111s
6.994038706s
7.018054467s

有点令人惊讶的是，我没有看到任何预热时间 - 第一行的持续时间总是比以下 4 行短，每次我运行这样做。而且，每次我运行它，持续时间不断增加，第 5 行总是最长的持续时间。

有人可以解释一下这些发现吗？还有什么方法可以使这个函数不使用任何可变变量但仍然具有接近可变版本的性能？

Answer 1

等效的不可变 one-liner 是：

fun randomWalk2(numSteps: Int) = 
    (1..numSteps).sumOf { -1 + 2 * Random.nextInt(2) }.absoluteValue

可能，性能更高的是替换

和

所以你将有一个乘法和 n 个加法，而不是 n 个乘法和 (2*n-1) 个加法：

fun randomWalk3(numSteps: Int) = 
    (-numSteps + 2 * (1..numSteps).sumOf { Random.nextInt(2) }).absoluteValue

更新

正如@Tenfour04 指出的那样，IntProgression.sumOf 没有特定的 stdlib 实现，因此它被解析为 Iterable<T>.sumOf，这将为 int 装箱增加不必要的开销。所以，最好在这里使用 IntArray 而不是 IntProgression:

fun randomWalk4(numSteps: Int) = 
    (-numSteps + 2 * IntArray(numSteps).sumOf { Random.nextInt(2) }).absoluteValue

仍然鼓励你用 JMH 检查这一切

Answer 2

我认为：“在不损失速度的情况下消除可变性” 是错误的标题。因为可变性来处理程序想要实现的流程。你在函数内部使用 var.... 并且 100% 这个 var 永远不会从这个函数之外改变，这是可变性的概念。如果我们 git 到处都摆脱 var 为什么我们在编程中需要它？

Answer 3

您的解决方案速度较慢，主要原因有两个：装箱和 generateSequence() 的 Sequence 实现所使用的迭代器的复杂性。

装箱的发生是因为 Sequence 通用地使用它的类型，所以它不能直接使用基本的 32 位 Int，但必须将它们包装在类中并在检索项目时解开它们。

迭代器的复杂度可以Ctrl+点击generateSequence函数查看源码

@Михаил Нафталь的建议更快，因为它避免了序列的复杂迭代器，但它仍然有装箱。

我尝试编写 sumOf 的重载，它直接使用 IntProgression 而不是 Iterable<T>，因此它不会使用装箱，并且这导致与使用 [= 的命令式代码等效的性能15=]。如您所见，它是内联的，当与@Михаил Нафталь 建议的 { -1 + 2 * Random.nextInt(2) } lambda 放在一起时，生成的编译代码将等同于您的命令式代码。

inline fun IntProgression.sumOf(selector: (Int) -> Int): Int {
    var sum: Int = 0.toInt()
    for (element in this) {
        sum += selector(element)
    }
    return sum
}

最后，我不认为您通过删除这么小的函数中的单个 var 来提高代码清晰度。我会说序列代码可能更难阅读。 vars 可能会增加复杂算法中的代码复杂性，但我认为在如此简单的算法中它们不会这样做，尤其是当它们只有一个并且它是函数的局部时。

在不损失速度的情况下去除可变性

Removing mutability without losing speed

performance

immutability

kotlin