Kotlin链接集合功能性能

Question

我是Kotlin的新手,我正在通过使用IDE提供的技巧解决IntelliJ中的简单谜题来学习该语言.我写了这段代码(找到最重复的数字):

fun main(args: Array<String>) {
    val tracer = mutableMapOf<Int,Int>()
    var currentMaxCount = 0

    val numbers = readLine()!!.split(' ').map(String :: toInt)

    for(number in numbers) {
        val currentCountOfNum = incrementAndGetCurrentCountOf(number, tracer)
        currentMaxCount = if(currentCountOfNum > currentMaxCount) currentCountOfNum else currentMaxCount
    }

    println(currentMaxCount)
}

fun incrementAndGetCurrentCountOf(num : Int, tracer: MutableMap<Int,Int>) =
        if(tracer[num] == null) {
            tracer.put(num, 1)
            1
        } else {
            val newCount = tracer[num]!! + 1
            tracer.put(num, newCount)
            newCount
        }

IDE建议以下代码:

    var currentMaxCount = 0
    for(number in numbers) {
            val currentCountOfNum = incrementAndGetCurrentCountOf(number, tracer)
            currentMaxCount = if(currentCountOfNum > currentMaxCount) currentCountOfNum else currentMaxCount
        }

改为:

val currentMaxCount = numbers
            .map { incrementAndGetCurrentCountOf(it, tracer) }
            .max()
            ?: 0

我明白发生了什么.但我想知道如果我使用IDE的建议,性能是否会变为O(2n).我想出的是O(n).我知道它在理论上没有什么区别,但我想知道Kotlin是否使用任何魔法将运行时间保持在O(n).(欢迎进一步缩小代码的任何其他建议)

Answer 1

TL; DR

是的,存在性能影响,因为这些实际上是两次独立的迭代.

在此特定上下文中,您可以通过利用专用maxBy方法避免执行额外迭代:

numbers.maxBy { incrementAndGetCurrentCountOf(it, tracer) } ?: 0

重要的是要记住,与Java Streams不同,Kotlin Collections不是懒惰的,所有那些花哨的方法都封装了简单的命令式实现.

因此,在乐观情况下,M链式map调用会导致O(M*N),即使整个处理可能被短路,因为访问所有元素是不必要的:

listOf(1, 2, 3)
      .map {
          println(it)
      }.first()

这打印:

1
2
3

在这种情况下,重要的是要记住asSequence方法的存在,该方法创建由给定集合支持的延迟评估序列:

listOf(1, 2, 3).asSequence()
      .map {
          println(it)
      }.first()

打印:

1