코테에서 Golang을 빠르게

• 자료의 공간 확보: Slice, Map에 cap 설정하기
• 빠른 입력: 입력 방식 변경으로 속도 17x 이상 향상
• 문자열 합치기: Builder를 이용해 속도 71x 이상 향상
• 정규 표현식: 직접 구현으로 속도 2.6x 이상 향상
• 함수 인라인 ( < v1.17)

---

자료의 공간 확보

s := make([]int, 100)  // 슬라이스, len: 100, cap: 100
s[i] = val  // 값 대입

s := make([]int, 0, 100)  // 슬라이스, len: 0, cap: 100
s = append(s, val)  // 값 대입

Slice를 생성할 때, 해당 Slice에 저장될 값의 범위를 알 수 있다면 미리 메모리에 공간을 확보하는 것이 유리하다. make는 slice의 형식을 입력받은 후, len과 cap을 입력받는다. len은 슬라이스의 길이로 []int를 3으로 선언하면 [0 0 0]이 만들어진다.
중요한 점은 Capacity이다. 만약 길이가 3인 슬라이스에 값을 추가해 길이가 4인 슬라이스를 만든다고 하자. 그럼 Go는 새로운 슬라이스를 만들게 된다. 이 때 성능 저하가 발생한다. 불필요한 슬라이스의 재생성을 막기 위해서는 cap을 지정하면 된다. cap은 미리 메모리 공간을 얼마나 확보해둘지에 대한 값이다. len이 3, cap이 5라면 [0 0 0]을 생성하지만 5개의 값이 들어갈 수 있는 메모리 공간을 확보해둔 상태이다. 따라서 값을 하나 추가해도 새로운 슬라이스를 생성하지 않는다. 

len: 3, cap: 5
0	0	0

배열을 사용해 공간을 확보하는 방법도 있지만 Go에서는 유연하게 길이를 조정할 수 있는 Slice를 권장한다. 실제 함수에 값을 넘길 때 배열보다 Slice가 더 범용적으로 사용될 수 있다. 

// 모든 int Slice를 받음
func GetSlice(s []int) []int {
	return s
}

// 길이가 5인 int 배열만 받음
func GetArray(a [3]int) [3]int {
	return a
}

func main() {
	// 정상 실행
	a := make([]int, 3)
	a = GetSlice(a)

	// 에러 발생
	s := [5]int{}
	s = GetArray(s) // 배열의 길이가 다름
}

---

빠른 입력

입력이 많은 문제의 경우, 입력 구문으로 인한 성능 저하가 발생할 수도 있다. 
[백준 14425번] 문제를 4가지 입력 방식을 이용해 풀이해 보았다. 

입력 방식	풀이 시간
scanner.Scan	116ms
reader.ReadString	124ms
fmt.Fscan(reader, ...)	268ms
fmt.Scan	시간 초과 (2초 이상)

어떤 입력을 사용하는가에 따라 시간을 2배 이상 단축하기도 하고, 시간 초과가 발생하기도 한다. 

// 가장 빠른 풀이
var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Scan()       
	sentence := sc.Text()
}

 

※ 주의 ※

하지만 scanner.Scan은 큰 입력을 받지 못한다. 

[백준 27649]을 풀어보니 분명 Python에서 문제가 없었는데 Go로 작성하니 계속 '틀렸습니다'가 나왔다. 그런데 Scanner를 Reader로 교체하니 문제가 해결되었다.

const (
	// MaxScanTokenSize is the maximum size used to buffer a token
	// unless the user provides an explicit buffer with Scanner.Buffer.
	// The actual maximum token size may be smaller as the buffer
	// may need to include, for instance, a newline.
	MaxScanTokenSize = 64 * 1024

	startBufSize = 4096 // Size of initial allocation for buffer.
)

Scanner를 구현한 소스코드를 살펴보면 MaxScanTokenSize라는 값이 정의되어 있다. 만약 입력의 크기가 64KB보다 크면 문제가 발생할 수 있다. 따라서 값이 클 것으로 예상되면 reader.ReadString을 사용하는 것이 안전하다.
 

Go 다양한 입출력

입력 방식에 관한 자세한 내용은 위 글을 참고하자. 

---

문자열 합치기 (출력)

res := []string{"a", "b", "c"}
fmt.Println(strings.Join(res, "-"))
// a-b-c

문자열을 연결할 때 + 연산자를 사용할 수도 있지만 느리다. 따라서 strings.Join을 사용하면 빠르게 문자열을 이어붙일 수 있다. 첫 인자로 string Slice를 입력받고, 두 번째 인자로 문자열 사이에 삽입할 문자열을 건네준다. 
Join 메서드가 문자열을 합치는 과정을 보면 내부적으로 Builder.WriteString 메서드를 사용하고 있다. 따라서 상황에 따라 WriteString 메서드를 직접 조작해 문자열을 이어붙이는 것도 좋은 방법이다. 

words := []string{"a", "b", "c"}

var b strings.Builder

b.WriteString(words[0])
for _, s := range words[1:] {
    b.WriteString("-")
    b.WriteString(words)
}

fmt.Print(b.String())
// a-b-c

 
[백준 1181번] 문제를 풀이한 결과를 보자.

문자열 결합	풀이 시간
builder.WriteString("\n")	28ms
Println	884ms
+= "\n"	시간 초과 (2초 이상)

WriteString이 압도적으로 빠른 것을 볼 수 있다. 심지어는 Python을 이용한 동일한 풀이도 200ms가 나왔다. 그에 비해 Go가 884ms나 시간 초과를 내는 것을 보면 잘못된 문자열 조작이 얼마나 치명적인가를 알 수 있다.  

---

정규 표현식

Golang의 정규 표현식인 regexp는 비교적 느리다고 알려져 있다. 따라서 직접 Go 레벨에서 처리해주는 것이 속도 향상에 도움이 될 수 있다.

// regexp를 이용한 풀이
re := regexp.MustCompile(`[<>\(\)]|&&|\|\|`)
sentence = re.ReplaceAllString(sentence, ` $0 `)

풀이 방식	풀이 시간
for { switch }	168ms
regexp.ReplaceAllString	444ms

[백준 27649]을 풀어본 결과, 복잡한 regexp를 사용하는 것보다 반복문+조건문으로 직접 구현하는 것이 더 빠른 것을 볼 수 있다. 
 
다만 [백준 2870] [백준 1264] 등 문제를 정규 표현식으로 풀어본 결과, 간단한 문제는 정규 표현식을 사용해도 성능에 큰 영향은 없었다. 

---

함수 인라인

만약 사용 중인 Go의 버전이 1.16 이하라면 함수의 인자와 반환값을 스택에 전달하는 방식을 사용한다. 이로 인해 약간의 성능 저하가 발생할 수 있으므로 간단한 함수라면 인라인 처리하는 것이 유리하다. 

Go 1.17 implements a new way of passing function arguments and results using registers instead of the stack. Benchmarks for a representative set of Go packages and programs show performance improvements of about 5%, and a typical reduction in binary size of about 2%.

- Go 1.17 Release Notes

그리고 이 부분은 Go 1.17에서 해결되었다.
(23.09.28) 현재 백준과 leetcode에서 Go 1.18을 사용하고 있기 때문에 큰 문제가 되지 않는다.