在 Kotlin 中快速 I/O

Question

Kotlin for competitive programming 建议使用以下代码读取控制台输入。

readLine()!!.split(" ").map{ str -> str.toInt() } //read space separated Integer from console

直到现在，我对每一个竞争问题都使用了相同的方法，老实说，它从未让我失望过。

但是对于输入整数的数量非常大的某些问题（接近 2 * 10^6） 这种方法太慢并且导致 TLE (超过时间限制).

是否有更快的方法从控制台读取输入？

Answer 1

如果您怀疑 .split() 调用是瓶颈，您可以探索一些替代方案 in this thread。

如果您怀疑 toInt() 调用是瓶颈，也许您可以尝试使用 Java 8 流 API 并行化流。例如：

readLine()!!.split(" ").parallelStream().map { str -> str.toInt() }...

为获得最佳性能，您可以将这两种方法结合使用。

Answer 2

我认为，toInt() 转换比 split(" ") 更昂贵。

您确定要在最开始将输入的Int 全部个字符串转换成

吗？

这取决于任务，但有时可以避免部分转换。例如，如果你有一个任务“检查输入中是否没有负数”，你可以将字符串一个一个地转换为Int，如果你遇到负数，不需要转换其他的

Answer 3

我认为 JMH 在这里可能会有用。您可以运行类似于下面的基准测试，并尝试找出您的瓶颈。

请注意，这是在 Mode.SingleShotTime 中，因此模拟了 JIT 几乎没有机会做它的事情的场景。

import org.openjdk.jmh.annotations.*
import java.util.concurrent.TimeUnit
import kotlin.random.Random

//@BenchmarkMode(Mode.AverageTime)
@BenchmarkMode(Mode.SingleShotTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@State(Scope.Benchmark)
open class SplitToInt {

    val count = 2 * 1_000_000

    lateinit var stringToParse: String
    lateinit var tokensToParse: List<String>

    @Setup(Level.Invocation)
    fun setup() {
        stringToParse = (0..count).map { Random.nextInt(0, 100) }.joinToString(separator = " ")
        tokensToParse = (0..count).map { Random.nextInt(0, 100) }.map { it.toString() }
    }

    @Benchmark
    open fun split() =
        stringToParse.split(" ")

    @Benchmark
    open fun map_toInt() =
        tokensToParse.map { it.toInt() }


    @Benchmark
    open fun split_map_toInt() =
        stringToParse.split(" ").map { it.toInt() }
}

我机器上的统计数据是：

Benchmark                   Mode  Cnt    Score   Error  Units
SplitToInt.map_toInt          ss        48.666          ms/op
SplitToInt.split              ss       124.899          ms/op
SplitToInt.split_map_toInt    ss       186.981          ms/op

所以拆分字符串并映射到 Ints 的列表需要大约 187 毫秒。允许 JIT 预热 (Mode.AverageTime) 给我：

Benchmark                   Mode  Cnt    Score    Error  Units
SplitToInt.map_toInt        avgt    5   30.670 ±  6.979  ms/op
SplitToInt.split            avgt    5  108.989 ± 23.569  ms/op
SplitToInt.split_map_toInt  avgt    5  120.628 ± 27.052  ms/op

这是快还是慢取决于 curmstances 但你确定这里的输入转换是你得到 TLE 的原因吗？

编辑：如果您确实认为 split(" ").map{ str -> str.toInt() } 太慢，您可以替换创建两个列表（一个来自 split，一个来自 map) 通过一次拆分和转换与单个列表。我写了一个快速 hack off kotlin.text.Regex.split 来做到这一点，它快了大约 20%。

如果在您的用例中您只需要检查部分输入，splitToSequence 可能是更好的选择。

在 Kotlin 中快速 I/O

Fast I/O in Kotlin

io

optimization

performance

kotlin