时间戳

首页 > 解决方案 > kotlin 中 Int.toString() 的时间复杂度

kotlin - kotlin 中 Int.toString() 的时间复杂度

问题描述

我想知道 kotlin 中默认方法 toString() 的时间复杂度。是 O(1) 还是 O(n)。我做了一些搜索，但没有找到任何答案。例如：如果我想将 int 数组转换为 String，我使用过：

var s = ""
array.forEach{
  s+= it.toString()
}

但如果数组大小为 10^4，我会得到 TLE。如果我不使用 toString() 那么我不会得到 TLE。我知道还有其他方法可以将 Int 数组转换为 String。但我想知道 kotlin 中默认 toString() 方法的时间复杂度。TIA

标签： kotlintime-complexity

解决方案

Kotlin 不保证toString().

它可能因对象而异；每个对象都必须实现它，因此它可能取决于对象的结构及其字符串表示形式。在许多情况下，我猜它可能在字符串的长度上是线性的，但你不应该依赖它。但这确实意味着具有短字符串表示的对象可能会花费很少的时间，因此不值得担心。

特别是，对于Ints，它很可能与字符串的大小成线性关系（因此与数字的对数成正比）。但这对于任何现实世界的程序来说都不太可能是重要的。

但是，可能重要的是构造的对象的数量，String因为它们占用内存，然后加速下一次垃圾回收。（即使对于无论“死”对象的数量如何都花费相同时间的垃圾收集器，拥有大量临时对象也会导致它们更频繁地运行。在高吞吐量系统中，这可能非常重要。）

对于问题中的代码来说，这肯定是一个问题，String每次循环都会创建两个新实例！一是调用的结果toString()；另一个是将其附加到s. （虽然前者总是很小，但后者每次都会增长，这使得空间需求呈二次方。）这就是为什么在循环中进行字符串连接通常是个坏主意！

当然，String它是不可变的——但它有一个可变的辅助类，StringBuilder. 因此，使用 a来累积结果几乎总是更好StringBuilder，然后String在最后创建一个（如果需要）：

val sb = StringBuilder()
array.forEach {
  sb.append(it.toString())
}
val s = sb.toString()

在这种情况下，您可以做得更好，因为StringBuilder重载append(). 因此，您可以直接附加一个Int，而根本不需要创建中间件String：

val sb = StringBuilder()
array.forEach {
  sb.append(it)
}
val s = sb.toString()

创建的唯一临时对象是StringBuilder的内部数组；随着内容的增长和增长，它将需要重新分配其数组来保存它们。如果您可以估计最终结果的大小，则可以预先调整大小StringBuilder以避免这种开销。

但实际上，您可能根本不会使用循环。你会使用joinToString()，它会为你做所有这些：

val s = array.joinToString("")

这更短、更简单、更易于阅读，并且可能与手动编码的版本一样好。Kotlin 有很多有用的扩展功能；熟悉它们非常值得！

如果您需要尽可能高效地自己构建一个复杂的字符串表示，而不是使用toString()它来创建每个部分，每个相关类都可以有一个方法，该方法将 aStringBuilder作为参数，并将其部分附加到 that。这可以让你在没有任何实例的情况下构建任意复杂的字符串String！

推荐阅读