在 Java 中，toCharArray() 和 toString() 的运行时是什么?

Question

这些性能如何？

BigInteger -> toString() // what is the runtime?
String -> toCharArray()  // what is the runtime?

谢谢。

Answer 1

BigInteger到 string 的转换是O(N^2)，其中N是结果中的位数，当内部表示的基不除以目标基时;当目标基数可以被存储基整除时，转换需要O(N)。

当内部表示为基数 256 时，请考虑转换为基数 10。除以十必须发生N次;每次，BigInteger表示的所有元素都会被修改。表示中的元素数与打印输出中的位数成正比，因此整体转换需要O(N^2)。

另一方面，在以 256 为基的内部表示中转换为大整数的十六进制需要O(N)，因为在这种情况下不需要除法。每个子元素可以独立于其余的子元素进行转换，子元素的数量与打印输出中的位数成正比。

就String.toCharArray()而言，它是O(N)，其中N是字符串中的字符数，因为每个字符都必须复制到输出中。

Answer 2

toString() 方法是使用 System.arrayCopy 实现的，它恰好是一个本机方法。

public char[] toCharArray() {
char result[] = new char[count];
getChars(0, count, result, 0);
return result;
}
public void getChars(int srcBegin, int srcEnd, char dst[], int dstBegin) {
// bounds checking
System.arraycopy(value, offset + srcBegin, dst, dstBegin,
srcEnd - srcBegin);
}

我想本机方法可能在引擎盖下使用 memcpy，即 O(N)，因此运行时 O 依赖于实际的 jvm 实现。 您可以查看打开的 jdk 源代码以检查此本机方法的源代码。