Java를 이용해서 알고리즘 문제를 풀 때, 알고리즘을 어떻게 구현하느냐에 따라서 동작 속도의 차이가 발생합니다. 그리고 거기에 속도 차이를 발생시키는 요소가 한가지 더 있습니다. 바로 입력입니다. 일반적으로 Java의 입력 속도는 C에 비해 느리다고 알려져있습니다. 입력 값이 작은 경우, 문제 풀이에 영향을 주는 경우는 드물지만, 대용량의 입력을 받아야 하는 경우, 입력 처리가 늦게 되면 실제 문제를 위한 연산 시간이 줄어들어 손해를 볼 수 밖에 없습니다.
Java에서 입력을 어떻게 구현하느냐에 따라서 실제 얼마나 차이가 나는지, 비교해봤습니다.
1. Scanner를 그대로 사용하는 경우.
2. BufferedReader를 사용하고, 문자열을 Strring.split로 분리하는 경우.
3. BufferedReader를 사용하고, 문자열을 StringTokenizer를 이용하여 분리하는 경우.
4. Scanner를 쓰되 BufferedInputStream을 이용하는 경우.
일반적으로 Scanner를 쓰면, 느리다고 말합니다. 그렇다고 하면 2번과 3번이 가장 빠르고, 1번과 4번이 느릴 것이라 예상할 수 있습니다.
각 소스코드는 다음과 같습니다. 소스코드는 모두, 100개의 테스트 케이스의 입력을 받으며, n * 2n의 입력을 배열에 집어넣습니다. 테스트에 사용한 입력의 크기는 334kbyte 입니다.
1. Scanner만 사용한 경우.
// scanner만 사용하는 경우
Scanner sc = new Scanner(new File(path));
testcase = sc.nextInt();
while (testcase-- > 0) {
size = sc.nextInt();
board = new int[size * 2 - 1][size];
for (int i = 0; i < size * 2 - 1; i++)
for (int j = 0; j < size; j++)
board[i][j] = sc.nextInt();
}
2. BufferedReader 와 String.split 을 사용한 경우.
BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(path))), 32768);
testcase = Integer.parseInt(br.readLine());
while (testcase-- > 0) {
size = Integer.parseInt(br.readLine());
board = new int[size * 2 - 1][size];
for (int i = 0; i < size * 2 - 1; i++) {
String current = br.readLine();
String[] currentsplit = current.split(" ");
for (int j = 0; j < size; j++)
board[i][j] = Integer.parseInt(currentsplit[j]);
}
}
3. BufferedReader 와 StringTokenizer를 사용한 경우.
InputReader cr = new InputReader(new FileInputStream(new File(path)));
testcase = cr.nextInt();
while (testcase-- > 0) {
size = cr.nextInt();
board = new int[size * 2 - 1][size];
for (int i = 0; i < size * 2 - 1; i++)
for (int j = 0; j < size; j++)
board[i][j] = cr.nextInt();
}
// InputReader Class
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
4. Scanner 와 BufferedInputStream을 사용한 경우
Scanner sc2 = new Scanner(new BufferedInputStream(new FileInputStream(path), 32768));
testcase = sc2.nextInt();
while (testcase-- > 0) {
size = sc2.nextInt();
board = new int[size * 2 - 1][size];
for (int i = 0; i < size * 2 - 1; i++)
for (int j = 0; j < size; j++)
board[i][j] = sc2.nextInt();
}
1번의 경우 예상대로 가장 느린 결과를 보여주었습니다. 10번을 반복해서 테스트를 수행하도록 하였는데, 주어진 입력을 모두 배열안에 넣는 시간이 약 200ms 정도 걸렸습니다. 2, 3번의 경우 예상대로 1번의 경우보다 월등하게 빠른 속도를 보여주였습니다. 각각 약 70ms정도의 시간이 걸렸고, String.split 또는 StringTokenizer 사용에 따른 시간차이는 무시해도 될만한 시간 차이를 보여주었습니다.
그런데 느린편에 속할 것이라는 4번의 경우, 2,3번 케이스와 비슷할 정도로 빠른 결과를 보여줍니다. 마찮가지로 10번의 반복해서 테스트하는 동안, 70ms 정도의 시간안에 처리하는 결과를 보여주었습니다. 따라서 Scanner를 사용하여 느렸다기 보다는, Scanner에 파일을 직접 입력받아 I/O를 처리하는 단위가 속도에 영향을 주었던 것이라고 판단됩니다. 따라서 BufferedinputStream을 이용하여 I/O를 줄이게 된다면, BufferedReader를 사용하는 것과 별다른 차이가 없다는 것을 알 수 있습니다. Scanner의 편리한 인터페이스를 포기하지 않고 속도마저 뒤지지 않은 방법인 것입니다.
결론은 1 << 2 = 3 = 4 입니다. 특별한 경우가 아니라면 Scanner와 BufferedInputStream을 사용하는 것이 성능과 편의를 동시에 취할 수 있는 좋은 방법이라고 생각됩니다.