기본 콘텐츠로 건너뛰기

가장 빠르게 정수 입력 스트림 읽는법

1. 빠른 정수 입력 스트림 읽기의 필요성

백준 알고리즘 문제를 풀다보면 정수로 구성된 일련의 데이터를 받아서 처리해야할 때가 있다. 백준은 입력과 출력 시간도 알고리즘 수행시간에 포함되다 보니 입, 출력 시간 절약이 아주 중요하다. 사람들이 입력 스트림을 읽는 방법은 크게 4 가지이다.

  • Scanner 사용
  • BufferedReader 사용
  • 사칙연산을 사용하는 커스텀 메소드 사용
  • 비트연산을 사용하는 커스텀 메소드 사용

이중 가장 빠른 것은 사칙 연산을 사용하는 커스텀 메소드이다.

  • 각 방법을 빠른 순으로 나열하면

    1. 사칙연산 사용 커스텀 메소드

    2. 비트연산 사용 커스텀 메소드

    3. BufferedReader

    4. Scanner

  • 커스텀 메소드들의 성능은 거의 같다.

  • BufferedReader는 커스텀 메소드의 두배정도 걸린다.

  • Scanner는 BufferedReader의 두 배이상 걸린다.

  • 테스트 수행 결과

2. 각 방법의 코드 및 사용법

2.1. Scanner

  • 클래스 임포트
import java.util.Scanner;
  • 객체 생성 및 정수 입력 스트림 읽기
Scanner sc = new Scanner(System.in);
//생략
sc.nextInt()
//생략
sc.close();

2.2. BufferedReader

  • 클래스 임포트
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
  • 객체 생성 및 정수 입력 스트림 읽기
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//생략
    //한줄에 여러개의 입력 정수가 공백 하나를 기준으로 나뉘어서 들어올때
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    Integer.parseInt(st.nextToken());
    //입력이 한줄에 하나씩일때
    Integer.parseInt(br.readLine());
//생략
sc.close();

2.3. 사칙연산을 이용하는 커스텀 메소드

  • 메소드 선언
static int readInt() throws IOException {
  int sum = 0;
	boolean isNegative = false;
	while (true) {
    int input = System.in.read();
		if (input == '\n' || input == ' ')
			return isNegative ? sum * -1 : sum;
		else if (input == '-')
			isNegative = true;
		else
			sum = (sum * 10) + input - '0';
	}
}
  • 정수 입력 스트림 읽기
readInt();

2.4 비트연산을 이용하는 커스텀 메소드

  • 메소드 선언
private static int readInt() throws Exception {
  int c, n = System.in.read() & 15;
  boolean isNegative = n == 13;
  if (isNegative) n = System.in.read() & 15;
  while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
  return isNegative ? ~n + 1 : n;
}
  • 정수 입력 스트림 읽기
readInt();

3. 각 방법별 성능 테스트.

JDK 11에서 공백으로 구분한 10000개의 정수입력을 읽는 테스트 3번씩 수행한 결과

  • 사칙연산 사용 커스텀 메소드는 4ms, 5ms, 5ms.
  • 비트연산 사용 커스텀 메소드는 5ms, 5ms, 5ms.
  • BufferedReader는 11ms, 11ms, 10ms.
  • Scanner는 31ms, 30ms, 29ms

3.1. 테스트 코드 작성

  • Scanner 사용
import java.io.IOException;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		System.out.println("시작");
		long startTime = System.currentTimeMillis();
		for(int i=0 ;i<10000; i++) {
			sc.nextInt();
		}
		long endTime = System.currentTimeMillis();
		System.out.println(endTime-startTime);
		sc.close();
	}
}
  • BufferedReader 사용
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Thread.sleep(3000);//3초안에 입력 붙여넣기
		System.out.println("시작");
		long startTime = System.currentTimeMillis();
		for(int i=0 ;i<1000; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for(int j=0; j<10; j++) {
				Integer.parseInt(st.nextToken());
			}
		}
		long endTime = System.currentTimeMillis();
		System.out.println(endTime-startTime);
    br.close();
	}
}
  • 사칙연산 사용 커스텀 메소드사용
import java.io.IOException;
public class Main {

	public static void main(String[] args) throws Exception {
		Thread.sleep(3000);//3초안에 입력 붙여넣기
		System.out.println("시작");
		long startTime = System.currentTimeMillis();
		for(int i=0 ;i<10000; i++) {
			readInt();
		}
		long endTime = System.currentTimeMillis();
		System.out.println(endTime-startTime);
	}
	static int readInt() throws IOException {
		int sum = 0;
		boolean isNegative = false;
		while (true) {
			int input = System.in.read();
			if (input == '\n' || input == ' ')
				return isNegative ? sum * -1 : sum;
			else if (input == '-')
				isNegative = true;
			else
				sum = (sum * 10) + input - '0';
		}
	}
}
  • 비트연산 사용 커스텀 메소드사용
public class Main {

	public static void main(String[] args) throws Exception {
		Thread.sleep(3000);//3초안에 입력 붙여넣기
		System.out.println("시작");
		long startTime = System.currentTimeMillis();
		for(int i=0 ;i<10000; i++) {
			readInt();
		}
		long endTime = System.currentTimeMillis();
		System.out.println(endTime-startTime);
	}
	private static int readInt() throws Exception {
		int c, n = System.in.read() & 15;
		boolean isNegative = n == 13;
		if (isNegative) n = System.in.read() & 15;
		while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);
		return isNegative ? ~n + 1 : n;
	}
}

3.2. 테스트 데이터 준비

테스트 입력 데이터 준비, 및 복사해놓기. 한줄에 1~10쓰고 1000번 반복한 전체 데이터를 복사.

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
...
1 2 3 4 5 6 7 8 9 10

3.3 테스트 프로그램 실행 및 데이터 붙여넣기

3초간의 sleep시간안에 입력 스트림에 복사해둔 10000개의 숫자 데이터를 붙여넣기 후 enter, 프로그램은 3초의 sleep이 끝난후 startTime에 타임스템프를 찍고 스트림을 읽기 시작한다.

...
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
시작
5
라벨:

댓글

댓글 쓰기

이 블로그의 인기 게시물

Cubase : Serum 사용법(1) : 소개와 오실레이터, 필터, 모듈레이터의 사용법

큐베이스 가상악기 Serum 사용법(1) Serum 소개와 오실레이터, 필터, 모듈레이터의 사용법 1. Serum 이란? 큐베이스에서 사용가능한 가상악기 VST 플러그인 형태로 나온 Software Synthesizer 이다. 사운드의 시각화가 잘 되어있는게 특징이며, 웨이브테이블을 통해 다체로운 사운드를 만들 수 있는게 특징이다. Serum 사용 화면. 2. Serum 의 구조 소프트웨어 신디사이저는 구조는 다음과 같고 Serum도 이러한 구조로 이루어져있다. 신디사이저의 구조 여기에서 각 모듈들이 하는 역활은 다음과 같다. 오실레이터 (Oscillator) : 소리를 발진 시킨다. 필터 (Filter) : 오실레이터로부터 받은 소리를 필터링 한다. 엠프 (Amp) : 필터를 거쳐온 소리를 증폭시켜서 최종적으로 출력한다. 모듈레이터 (Modulator) : 각 모듈(오실레이터, 필터, 엠프)에 ENV, LFO 신호를 줘서 변형을 준다. ENV (Envelope Generator) : ADSR의 패턴을 가지고 신디사이저의 모듈들을 컨트롤 할 수 있는 Envelope를 생성한다. 보통 키보드 게이트의 신호를 통해 작동되어 시간에 따라 변하는 전압(Envelope)을 생성한다. LFO (Low Frequency Oscillator) : 저주파 발진기로. 저주파 패턴을 만들어서 음성을 변조하는대 사용한다. 그리고 Serum에서 각 모듈의 위치는 다음과 같다. Serum의 모듈 위치 3. Serum 각 모듈별 사용법 - 오실레이터(Oscillator) 오실레이터에서 Osc A, B가 활성화 되어있다 오실레이터는 크게 Sub와 Noise, Osc A, Osc B로 이루어져 있다. Sub는 기본파형을 발생시킬수 있으며 Noise는 치지직거리는 배경 잡음을 발생시키고, Osc A와 B는 각각 웨이브테이블을 이용해 다양한 파형의 소리를 발진시킨다. 각 요소...
댓글 쓰기
자세한 내용 보기

윈도우 10 부팅시 자꾸 start process as current user get session user token failed 뜨는 현상 해결법

start process as current user get session user token failed 가 뜨는 경우는 분명 여러가지가 있으므로 이 해결책은 극히 일부의 문제에만 해당하는 해결법임을 명시합니다. 얼마전 컴퓨터를 부팅하는데 start process as current user get session user token failed 메시지가 뜨면서 부팅을 방해받았던적이있다. 물론 내 컴퓨터는 아니었지만, 딱히 그럴만한 이유가 떠오르지 않았다. 바이러스에 노출될 환경이 아니었기 때문이다.  그렇다면 문제가 무었일까? 나는 구글에서 검색을 해보았고 해당 문제를 겪고있는 많은 사람들을 볼 수 있었다. 특이한점은 내가 본사람들은 전부 한국 사람이었고 전부 11월 1일 이후로 이 문제를 겪고 있었다는 것이었다. 그리고 나는 이문제의 해결법을 찾았다. 다름아닌 vpwalletservice.exe 가 문제였다. 작업관리자에서 VPwalletservice 또는 그와 관련된 VP.inc에서 배포한 프로그램을 모두 종료하고 msconfig를 실행해 서비스 목록에서 vpwalletservice 와 관련 프로그램을 제외시켜야 한다. 이렇게 해결을 보고 지금은 문제없이 잘 사용중이다.
댓글 쓰기
자세한 내용 보기

윈도우 10 마우스(커서) 옆에 자꾸 Progress bar(진행중 아이콘)가 나타난다면

이 글은 윈도우10 사용자 중 자꾸만 마우스 커서 옆에 뭔가가 실행중이라고 진행 아이콘이 뜨는 사람에게 조그마한 희망을 주는 글 입니다. 또한 백그라운드에서 프로그램이 실행되는 경우는 아주 다양하니 이 글에서 제시하는 방법은 수많은 문제 중 한가지 문제의 해결책일 뿐임을 미리 알려드립니다. 본인은 원래 해당컴퓨터에서 바이러스에 걸릴만한 행위를 일체 하지않았다. 토렌트나 웹하드는 전혀 사용하지 않고 인터넷에서 파일도 대기업의 공인된 파일만 다운받아서 썼었다. 그러나 어느 날 부턴가 다음과 같은 현상이 발생하였다. 아무런 프로그램도 실행중이지 않지만 자꾸 마우스 아이콘에 실행중이라고 뜨는 문제였다. 이해를 돕기위한 삽화 나는 실행한 프로그램이 없지만 뭔가가 실행중이라는 것은 백그라운드 서비스가 원인이라는 것이다. 그렇다면 어떤 서비스가 다음과같은 현상을 야기했을까? 나는 작업관리자에서 의심가는 백그라운드 프로세스를 종료해보았다. 바로 vpwalletservice VP.Inc에서 배포한 프로그램이었다. 아니나 다를까 해당 프로세스를 삭제하자마자 현상은 사라졌다. 백그라운드 서비스인만큼 msconfig의 서비스 목록에서도 제거하였고 이제 확실히 이런 현상은 발생하지 않을 것이다. 해당 프로그램은 현재 여러 문제를 야기시키는 것으로 인터넷에서 유명하다. 얼마전에는 해당프로그램이 윈도우 부팅시에 start process as current user get session user token failed 메시지를 띄우게 만들어 부팅을 방해했던 문제도 직접 경험해 본적이있다. 이 경우에도 해결방법은 같다.
댓글 쓰기
자세한 내용 보기