[BOJ 15552] 빠른 A+B

문제 링크 :  www.acmicpc.net/problem/15552
문제 분류 : 입출력

 

사용 언어에 맞는 빠른 입출력을 요구하는 문제이다.

 

문제 풀이는 했지만, 다른 사람들의 풀이를 보고 새롭게 알게된 내용이 있어서 정리 차원에서 기록을 남긴다.

 

속도 향상을 위한 방법

1. 컴파일 속성 조정 (최적화 옵션 및 타겟 설정)
2. 빠른 입출력 사용

참고)

register 변수를 사용하는 경우도 있는데, C++17부터 이 키워드는 사용되지 않는다고 한다.

기존 코드에 register 키워드가 있어도, 실제 레지스터를 사용하는 것은 컴파일러나 CPU에 따라 다르다고 한다.

 

C언어의 경우 해당 키워드가 적용된다.

RAM대신 CPU의 Register를 사용하게 되어 자주 사용 되는 변수를 register키워드로 선언할 경우 속도가 향상된다.

 

1. 컴파일 속성 조정하기

GCC 컴파일 속성은 다음과 같은 형태로 적용 될 수 있다.

#pragma GCC 속성 변수(속성 변수의 값)

 

위와 같이 전처리 지시어 #pragma를 사용할 경우 컴파일러에게 특정 정보를 전달하여 변수나 함수에 특정 속성값을 지정할 수 있다.

 

컴파일러에 따라 함수나 변수 앞에 다음과 같은 같이 속성값이 적용된다.

__attribute__((속성 변수("속성 변수 값")))

 

 

1. #pragma GCC optimize ("O3") - 최적화 옵션을 O3으로 설정
2. #pragma GCC target("arch=skylake") - cpu 아키텍쳐를 skylake로 설정(특정 명령어 집합 구조(ISA)를 사용)

위 전처리 지시문은 GCC 컴파일러에게 각각의 변수나, 함수에 속성값을 부여 하라는 의미이다.

위와 같이 처리했을 경우 다음과 같은 추가 속성값이 각각 함수에 붙게 된다.

void __attribute__((target("arch=skylake")))__ __attribute__((optimize("O3"))) func(void) { }

 

특정 부분의 함수에서만 속성값을 적용하려면 다음과 같이 하면 된다.

#pragma GCC push_options

#pragma GCC optimize ("O3")

// 속성 적용할 코드 작성

#pragma GCC pop_options

 

참고) 전처리 지시어 #pragma

#pragma ?
#pragma는 define 이나 include와 같이 #으로 시작하는 전처리 구문(Precompiler)의 하나이다. 
컴파일러에 종속적인 명령으로, 컴파일러에 직접 정보를 전하기 위해 사용하는데, 컴파일러에 종속적이기 때문에 컴파일러를 변경했을 경우 실행을 보장하진 못한다.

1. #pragma once

컴파일러에게 한번만 컴파일 하라고 알려준다.

2. #pragma comment()

사용 형식 : #prgma comment( comment-type, comment string

comment type :  compiler, exestr, lib, linker 등

설정방법

1. 명시적인 라이브러리 링크
   • #pragma comment(lib, "lib 이름")
2. subsystem 설정
   • #pragma comment(linker, "/subsystem:windows")
   • #pragme comment(linker, "/subsystem:console")
3. section의 설정(공유메모리사용)
   • #pragma comment(linker, "SECTION :.SHAREDATA, RWS")
   • #pragma data_seg("SHAREDATA")와 함께 사용하여 공유 메모리 생성

3. #pragma warning
사용 형식

#pragma warning( warning-specifier : warning-number-list [; warning-specifier : warning-number-list...] )

#pragma warning( push[,n] )

#pragma warning( pop )

사용 예

#pragma warning(disable:4996)

4. #pragma message() 
컴파일중에 메시지를 뿌리기 위함. 
ex) #pragma message("메세지")

#pragma ?
#pragma는 define 이나 include와 같이 #으로 시작하는 전처리 구문(Precompiler)의 하나이다. 
컴파일러에 종속적인 명령으로, 컴파일러에 직접 정보를 전하기 위해 사용하는데, 컴파일러에 종속적이기 때문에 컴파일러를 변경했을 경우 실행을 보장하진 못한다.

 

1. #pragma once

컴파일러에게 한번만 컴파일 하라고 알려준다.

 

2. #pragma comment()

사용 형식 : #prgma comment( comment-type, comment string

comment type :  compiler, exestr, lib, linker 등

설정방법

1. 명시적인 라이브러리 링크
   • #pragma comment(lib, "lib 이름")
2. subsystem 설정
   • #pragma comment(linker, "/subsystem:windows")
   • #pragme comment(linker, "/subsystem:console")
3. section의 설정(공유메모리사용)
   • #pragma comment(linker, "SECTION :.SHAREDATA, RWS")
   • #pragma data_seg("SHAREDATA")와 함께 사용하여 공유 메모리 생성

3. #pragma warning
사용 형식

#pragma warning( warning-specifier : warning-number-list [; warning-specifier : warning-number-list...] )

#pragma warning( push[,n] )

#pragma warning( pop )

 

사용 예

#pragma warning(disable:4996)

4. #pragma message() 
컴파일중에 메시지를 뿌리기 위함. 
ex) #pragma message("메세지")

 

2. 빠른 입출력 사용

• 입력 속도 비교
• 출력 속도 비교

 

C언어의 scanf, printf는 충분히 빠르다.

C++ 에서는 cin, cout을 사용하려면 ios_base::sync_with_stdio(false); cin.tie(NULL)을 사용한다.

 

scanf, printf보다 더 빠른 방법이 있지만, 왠만하면 이 함수들로 입출력에 대한 문제는 해결된다.

만약 더 빠른 입출력을 사용해야 된다고 하면 다음과 같은 방법으로 입출력 속도를 좀 더 향상 시킬 수 있다.

 

1. 스트림 사용 방식의 변경
2. 더 빠른 입출력 함수 사용
3. 한번에 입력 받기, 한번에 출력하기 (입출력 함수 호출 최소화)
4. 입출력 함수 직접 구현

 

Stream 사용 방식 변경

int setvbuf(FILE* stream, char* buffer, int mode, size_t size);

위 함수를 사용해서 스트림 방식을 변경할 수 있다.

 

setvbuf 참고

 

scanf보다 더 빠른 입력 함수

1) int fgetc(FILE* stream)

• 스트림에서 하나의 문자를 읽어 들인다.
• 리턴값 : 읽어 들인 문자(int 값)

2) size_t fread(void* ptr, size_t size, size_t count, FILE* stream);

• 스트림에서 한번에 size byte크기 만큼씩 count개의 원소를 읽어 ptr(버퍼)에 넣는다. => 한번에 입력 받을 때 사용
• 리턴값 : 읽어들인 원소 개수

 

printf보다 더 빠른 출력 함수

1) int fputc(int character, FILE* stream)

• 스트림에 하나의 문자를 출력한다.
• 리턴값 : 출력한 문자

2) size_t fwrite(void* ptr, size_t size, size_t count, FILE* stream);

• ptr(버퍼)에서 size byte크기 만큼씩 count개의 원소를 stream에 출력한다. => 한번에 출력 할 때 사용
• 리턴값 : 출력한 원소 개수

 

 

함수 호출 도중 오류가 발생하면 리턴 값으로 오류값이 들어간다. (입력, 출력 함수 동일)

fread와 fwrite 함수가 빠른 성능을 보이기 때문에 자주 사용된다.

 

입출력 함수 커스터마이징

입출력 함수 구현 전에 ASCII Code에 대해서 알아보자 (ASCII 범위 내의 문자만 입력 된다고 가정)

ASCII Code 표

ASCII Code 표의 코드 의미 분류 해보기

• 0~31, 127 : 제어 문자로 출력 불가능한 문자들이다. (null, enter 등이 포함됨)
• 10 : line feed 개행 문자 '\n'
• 32~126 : 출력 가능한 문자
• 32 : ' ' 공백(space) 문자
• 48 ~57 : '0' ~ '9' 까지의 숫자를 나타내는 문자
• 65 ~ 90 : 'A' ~ 'Z' 까지의 대문자
• 97~ 122 : 'a' ~ 'z' 까지의 소문자
• 45 : '-' , 뒤에 '0'~'9' 사이의 문자열이 올 경우 음의 정수로 인식할 수 있다.

문자(0~9) 와 숫자 사이의 변환

- ascii to decimal

• c - '0'
• c - 48
• c ^ 48 => 48은 $2^4 + 2^5$이므로 $2^4$보다 작은 1~9사이의 숫자와 비트 연산을 해도 무방하다
• c&15 => 1~9는 $15 = 1111_{2}$ 사이의 비트로 이루어져 있기 때문에 &연산으로 구할 수 있다.

- decimal to ascii

• d + '0'
• d + 48
• d | 48

 

여러개의 문자를 입력 받을 때, 버퍼 사이즈에 따라 한번에 입력 받거나 여러번 나눠서 입력을 받는다.

1. 버퍼가 충분히 큰 경우 : 버퍼를 비우지(flush)않고 한번에 입력 받는게 더 빠르다.
2. 버퍼 사이즈가 충분하지 않은 경우 : 입력 데이터가 많거나, 정수 표현 범위가 클 경우 버퍼를 무한정 크게 할 수 없기 때문에 버퍼를 중간에 비워(flush)야 한다. 너무 크게 할 경우 메모리를 많이 먹고, 너무 작게할 경우 자주 flush 문제에 따라서 적당한 크기로 buffer size를 선정해야 한다.

1. 버퍼가 충분히 큰 경우

#pragma GCC optimize ("O3")
#pragma GCC target("arch=skylake")

#include<cstdio>

char buf[1<<23];
int rIdx, wIdx; // rIdx : read inedx , wIdx : write index
inline void readint(int & r)
{
	r = 0;
	char c = buf[rIdx++];
	while (c < '0') c = buf[rIdx++];
	while ('0' <= c)
	{
		r = r * 10 + (c & 15);
		c = buf[rIdx++];
	}
}

inline void writeint(int n)
{
	char str[4], strIdx = 0; // 0제외 1~4인덱스 사용 (최대 4자리)
	while (n)
	{
		str[strIdx++] = n % 10 | 48; // ascii to int
		n /= 10;
	}
	
	while (strIdx)
	{
		buf[wIdx++] = str[--strIdx];
	}
}

int main()
{
	fread(buf, 1, 1<<23, stdin);
	int n, a, b;
	readint(n);
	while (n--)
	{
		readint(a), readint(b);
		writeint(a + b);
		buf[wIdx++] = '\n';
	}
	
	fwrite(buf, 1, wIdx, stdout);
}

fread 대신 syscall(0, 0, buf, bufferSize)로 fwrite대신 syscall(1, 1, buff, bufferSize) 형태로 사용 가능하다.

 

2. 버퍼가 충분히 크지 않은 경우

빠른 입출력

깃헙 fast io 참고

// fast I/O
// buf_size

inline int readChar();
template<class T = int> inline T readInt();
template<class T> inline void writeInt(T x, char end = 0);
inline void writeChar(int x);
inline void writeWord(const char *s);
static const int buf_size = 1 << 18;
inline int getChar(){
    #ifdef ONLINE_JUDGE
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if(pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
    if(pos == len) return -1;
    return buf[pos++];
    #endif
}
inline int readChar(){
    #ifdef ONLINE_JUDGE
    int c = getChar();
    while(c <= 32) c = getChar();
    return c;
    #else
    char c; cin >> c; return c;
    #endif
}
template <class T>
inline T readInt(){
    #ifdef ONLINE_JUDGE
    int s = 1, c = readChar();
    T x = 0;
    if(c == '-') s = -1, c = getChar();
    while('0' <= c && c <= '9') x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
    #else
    T x; cin >> x; return x;
    #endif
}
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int x){
    if(write_pos == buf_size) fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}
template <class T>
inline void writeInt(T x, char end){
    if(x < 0) writeChar('-'), x = -x;
    char s[24]; int n = 0;
    while(x || !n) s[n++] = '0' + x % 10, x /= 10;
    while(n--) writeChar(s[n]);
    if(end) writeChar(end);
}
inline void writeWord(const char *s){
    while(*s) writeChar(*s++);
}
struct Flusher{
    ~Flusher(){ if(write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0; }
}flusher;

 

위 코드의 경우 버퍼를 비울 수 있고, 음의 정수에 대한 처리도 가능하다.

 

 

볼만한 자료

scanf에 분석

C, C++ 빠른 입출력

 

References

https://gcc.gnu.org/onlinedocs/gcc-4.8.2/gcc/Variable-Attributes.html#Variable-Attributes

http://www.silverwolf.co.kr/cplusplus/4724

웹상에서 컴파일러 동작 확인할 수 있는 곳

getc와 getchar

syscall 숫자 의미

https://modoocode.com/62