java - 优化 - 将整数数组输出到 std 输出的最有效方法，在 Java 中用换行符分隔

Question

我面临着对输入大小 n 从 0 到 1m 的 32 位有符号整数序列(-2,147,483,648 到 2,147,483, 647)进行排序的问题。输入数字由换行符分隔，std in 中的第一个数字表示输入/数字的数量。我首先使用缓冲输入读取器读取输入

BufferedReader bufferedInput = new BufferedReader(new InputStreamReader(System.in));
int NOI = 0; // Number of inputs
try{
    NOI = Integer.parseInt(bufferedInput.readLine());
} 
catch(IOException e) {
}
int[] a = new int[NOI];
try{
    for(int i = 0; i < NOI; i++){
         a[i] = Integer.parseInt(bufferedInput.readLine());
    }
} 
catch(IOException e){
}

然后我对数组 a 进行基数排序(就地)，然后继续将排序后的数组(升序)打印到 std 输出，每个数字由新行分隔。

for(int i = 0; i < NOI; i++){
    System.out.println(Integer.toString(a[i]));
}

这是一个优化问题，我在 ideone.com 上测试了我的代码使用 appincredible.com/online/random-number-generator/ 的输入发现对于 1000 个数字的输入大小，每个步骤 3sf 的运行时间如下:

读取输入 - 14.5 毫秒

排序 - 1.28 毫秒

打印输出 - 56.2 毫秒

我希望使我的解决方案更有效地解决这个问题，并且从我所做的一点测试中我注意到大部分运行时间都在输出阶段。那么，我怎样才能更有效地迭代数组，将每个元素打印到 std 输出中的新行？正在查看What is the most efficient way to convert an int to a String?和 Most efficient way of converting String to Integer in java建议 Integer.toString() 是将整数转换为字符串以进行输出的最有效的方法。

有什么指点吗？这是我的第一个问题，我希望得到一些帮助，我环顾四周，找不到类似的问题。可能我的问题在于我用来存储数组的数据结构？我不太确定 谢谢:)

Answer 1

我假设这是某种编程竞赛。否则，答案是首先不要将此数据序列化为文本。我也会非常小心地在任何“现实世界”程序中引入这些优化。

在如此紧密的循环中，一切都变得昂贵。您需要担心通常认为理所当然的事情:

避免系统调用

System.out.println 将立即打印每一行。这需要调用操作系统——这有点昂贵。收集一批输出并一次将其全部写入会更有效。您可以使用 StringBuilder 或使用 BufferedWriter 手动完成此操作:

BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
for (int i = 0; i < n; i++) {
    out.write(a[i]+"\n");
}
out.flush();

避免对象分配

每个Integer.toString调用都会创建新的String对象。由于该循环的其余部分非常简单，因此可能会花费大量时间。 StringBuilder.append(int) 将把整数附加到其缓冲区而不分配字符串:

StringBuilder sb = new StringBuilder();
for(int i = 0; i < n; i++){
    sb.append(a[i]);
    sb.append('\n');
}
System.out.print(sb)

StringBuilder 将在空间不足时重新分配其内部缓冲区。我们知道 n 个数字不会超过 n*11 个字符。我们可以通过从一开始就分配足够的空间来进一步减少分配数量。

使用字节而不是字符

无论如何，输出都会以字节形式结束。通过将数字直接转换为字节，我们可以节省内存并跳过一个额外的步骤。请注意，输出是以相反的顺序写入的，以简化整数转换:

OutputStream out = System.out;
byte[] buffer = new byte[n*11];
int position = buffer.length;
for (int i = n - 1; i >= 0; i--) {
    int number = a[i];
    buffer[--position] = '\n';
    do {
        buffer[--position] = (byte) ('0' + number % 10);
        number /= 10;
    } while (number != 0);
}
out.write(buffer, position, buffer.length - position);

在应用任何这些想法之前，请确保首先根据真实数据对它们进行基准测试。优化最重要的部分是测试并确保您的假设符合现实。

以下是 1k、10k 和 100k 行输入的结果:

                   1k      10k     100k
original           18ms    46ms    117ms
BufferedWriter     6ms     11ms    32ms
StringBuilder      3ms     6ms     23ms
bytes              1ms     2ms     8ms

最后但并非最不重要的一点是，确保这些优化确实值得增加的复杂性和可能的​​错误。特别要注意的是，最后一个版本不处理负数。