Java:获取输入整数数组的最有效方法

Question

我正在解决一个问题，需要我将大量整数存储到整数数组中。输入被格式化，使得一行显示整数的数量，下一行显示要存储的所有值。例如:

3
12 45 67

在该问题中，需要存储接近 100,000 个整数。目前我正在使用这种存储整数的方法:

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();

int[] iVau = new int[n];

String[] temp = scanner.nextLine().split(" ");

for(int i = 0; i < n; i++) {
    iVau[i] = Integer.parseInt(temp[i]);
}

这工作正常，但是我正在解决的问题有严格的时间限制，而我当前的解决方案超出了它。我知道有一种更有效的方法可以使用缓冲读取器和输入流来存储此输入，但我不知道该怎么做，有人可以告诉我吗？

Answer 1

您使用 Scanner 的方式使您的程序在内存中一次性保存一个包含整数的字符串。输入的第二行有 100000 个数字，效率不高，您可以一个接一个地读取数字，而无需将前一个数字保留在内存中。因此，这样，避免使用 Scanner.readLine() 应该会让你的程序运行得更快。您不必一次读取整行，然后第二次读取此字符串来解析其中的整数:您只需执行一次这两个操作。

这是一个例子。方法testing()不使用任何扫描仪。 test2() 方法是您提供的方法。文件 tst.txt 包含 100000 个数字。在我的 Mac Mini(Intel Core i5@2.6GHz)上，该程序的输出是:

duration without reading one line at a time, without using a Scanner instance: 140 ms
duration when reading one line at a time with a Scanner instance: 198 ms

如您所见，不使用 Scanner 会使您的程序速度提高 41%((198-140)/140*100 的整数部分等于 41)。

package test1;
import java.io.*;
import java.util.*;

public class Test {
    // Read and parse an Int from the stream: 2 operations at once
    private static int readInt(InputStreamReader ir) throws IOException {
        StringBuffer str = new StringBuffer();
        int c;
        do { c = ir.read(); } while (c < '0' || c > '9');
        do {
            str.append(Character.toString((char) c));
            c = ir.read();
        } while (!(c < '0' || c > '9'));
        return Integer.parseInt(str.toString());
    }

    // Parsing the input step by step
    private static void testing(File f) throws IOException {
        InputStreamReader ir = new InputStreamReader(new BufferedInputStream(new FileInputStream(f)));
        int n = readInt(ir);
        int [] iVau = new int[n];
        for (int i = 0; i < n; i++) iVau[i] = readInt(ir);
        ir.close();
    }

    // Your code
    private static void testing2(File f) throws IOException {
        Scanner scanner = new Scanner(f);
        int n = scanner.nextInt();
        int[] iVau = new int[n];
        scanner.nextLine();     
        String[] temp = scanner.nextLine().split(" ");
        for(int i = 0; i < n; i++)
            iVau[i] = Integer.parseInt(temp[i]);
        scanner.close();
    }

    // Compare durations
    public static void main(String[] args) throws IOException {
        File f = new File("/tmp/tst.txt");          

        // My proposal    
        long t = System.currentTimeMillis();
        testing(f);
        System.out.println("duration without reading one line at a time, without using a Scanner instance: " + (System.currentTimeMillis() - t) + " ms");       

        // Your code    
        t = System.currentTimeMillis();
        testing2(f);
        System.out.println("duration when reading one line at a time with a Scanner instance: " + (System.currentTimeMillis() - t) + " ms");
    }
}

注意:使用 bash 或 zsh 创建输入文件是这样完成的:

echo 100000 > /tmp/tst.txt
for i in {1..100000}
do
  echo -n $i" " >> /tmp/tst.txt
done