Производительность функции сборки цепей Kotlin

Я новичок в Kotlin, и я изучаю язык, решая простые головоломки в IntelliJ, используя подсказки, представленные IDE. Я написал этот фрагмент кода (поиск наиболее повторяющегося числа):

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 

Я понимаю, что происходит. Но мне было интересно, будет ли производительность стать O (2n), если я буду использовать предложение IDE. Это O (n) в том, что я придумал. Я знаю, что это теоретически не имеет значения, но я хотел бы знать, использует ли Kotlin какую-либо магию, чтобы поддерживать время работы на O (n). (Любые дополнительные предложения по дальнейшему сокращению кода приветствуются)

TL; DR

Да, есть влияние производительности, поскольку на самом деле это две отдельные итерации.

В этом конкретном контексте вы можете избежать дополнительной итерации, используя выделенный метод maxBy :

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

Важно помнить, что коллекции Kotlin, в отличие от Java-потоков, не ленивы, и все эти причудливые методы инкапсулируют простые императивные реализации.

Таким образом, 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