Go Slice Tricks

개요

 

링크의 Slice trick 들을 따라가 보며 정리해보았다. 

링크: Slice Tricks: https://github.com/golang/go/wiki/SliceTricks

 

 

append() 와 copy() 의 탄생

 

buiit-in 함수인 append() 와 copy() 가 제공되면서 container/vector 패키지는 더 이상 쓸 필요가 없다.

 

Append - 뒤에 이어서 붙여넣기	a = append(a, b...)	a 라는 슬라이스에 b 라는 녀석(들)을 뒤에 붙여준다.
Copy - 복사하기	1) not perfect   b = make([]T, len(a)) copy(b, a)   2) not perfect   b = append([]T(nil), a...)   3) perfect   b = append(a[:0:0], a...)	문제점과 해법 링크: http://bit.ly/3532Slc 1) b를 먼저 a의 길이만큼 만들고 b에 a 를 copy 한다. - a가 nil 인 경우 b 는 nil 이 아니다 2) nil 인 녀석에다 a… 를 append 한걸 b 로 생성한다. - a 가 nil 이 아닌 빈 슬라이스이면 b 는 nil 이 된다.   완벽한 해법은  3) 이다. 3) 은 a 가 nil 이면 b 도 nil, a 가 nil 이 아니면 b 도 nil 이 아니다. - 심지어는 이게 더 빠르기까지 하다. http://bit.ly/2F2gyCh   *  three-index subslice - a[2:4:7] 이라면 a[2], a[3] 까지를 가지지만, capacity 는 a[7] 까지라는 것 - 즉 cap(a) 는  5가 된다. - a[:0:0] (= a[0:0:0]) 이녀석이 nil 일때는 nil, 아닐때는 아닌게 핵심이다.   테스트 코드: https://play.golang.org/p/lOTpKDlkUCc
Cut - 잘라내기	a = append(a[:i], a[j:]...)	a[i:j] 만큼을 잘라내는 셈이다.
Delete - 삭제하기	a = append(a[:i], a[i+1:]...)   a = a[:i+copy(a[i:], a[i+1:])]	a[i] 를 삭제하려는 것인데   1) 은 i 전까지 에다가 i후를 이어붙이는 것이다. 2) 는 쪼금 더 복잡해 보이기는 하다. 장점이 없다면 쓸 필요 없을 듯
Delete without perserving order - 순서 무시하고 삭제하기	a[i] = a[len(a)-1] a = a[:len(a)-1]	이건 삭제하고 난 순서가 꼬여도 상관없을때 쓰는 방법이다. 1) 맨 끝에 녀석을 지우려는 녀석에다 덮어쓰고 2) 슬라이스 자체의 길이를 하나 줄여서 덮어쓴다.

 

만약 슬라이스의 타입이 pointer 이거나, 구조체인데 pointer field 가 있을 경우에는 위의 cut 과 delete 는 memory leak 문제가 발생할 수 있다.

slice 에 의해 element 의 값이 참조된다면  가비지컬렉트 되지 못하는 것이다. (정확한 사례는 감이 오지 않는다.)

아래 코드는 그 문제를 해결해준다.

 

Memory leak 방지버전

 

Cut	copy(a[i:], a[j:]) for k, n := len(a)-j+i, len(a); k < n; k++ {         a[k] = nil // or the zero value of T } a = a[:len(a)-j+i]	1) 일단 copy() 를 이용하여 지우려는 a[i:j] 영역을, a[j:] 로 덮어쓴다. 2) 그러고 원래 a의 남는 부분을 타입의 초기값을 먹여준다. - Pointer value 인 경우 nil 을 먹여주면서 Reference 를 끊어주고, - 따라서 Garbage collection 이 되게 해주는 것이다. 3) 마지막으로 a 를 정확하게 새로 생성해준다.   테스트 코드: https://play.golang.org/p/75jpfmUq1py
Delete	if i < len(a)-1 {   copy(a[i:], a[i+1:]) } a[len(a)-1] = nil // or the zero value of T a = a[:len(a)-1]	1) if 를 안넣어도 큰 상관은 없어 보이지만 2) 암튼 맨 마지막 녀석을 nil 먹여주고 3) a의 정확한 길이만큼 slice 해준다.
Delete without perserving order	a[i] = a[len(a)-1] a[len(a)-1] = nil a = a[:len(a)-1]	이것도 memory leak 방지하는 방식은 위랑 똑같다.

 

Expand 와 Extend

 

Expand   - Expand는 중간에 일정사이즈의 공간을 만드는 것이다. - i 위치에서부터 j 만큼 공간을 만들어라 - 테스트 코드: https://play.golang.org/p/Gojtu7M3MYV
Extend 는 별거 없다. 그냥 j 만큼 늘리는 것이다.	a = append(a, make([]T, j)...)

 

Filter 와 Insert

 

Filter (in place)   - keep() 라는 조건에 맞으면 n 을 증가하면서 값을 넣어준다. - 그리고 최종적으로 a를 적정 길이의 녀석으로 만들어준다.   Cut 과 마찬가지로 memory leak 이 발생할 수 있겠다. - 마찬가지로 a[n:] 영역을 초기화 해주면 해결되겠다.	n := 0 for _, x := range a {         if keep(x) {                 a[n] = x                 n++         } } a = a[:n]
Insert   아까의 Expend 와 유사하다. 다만 특정한 값 x 를 중간에 넣어주는 것이다.   이 구현의 문제는 복사가 두 번이나 일어난다는 것. → 복사는 비용이 많이 든다. 1) 두번째 append 에서  []T{x} 가 생성되고 a[i:] 가 복사된다음 2) 다시 이 녀석들을 a[:io] 에 복사한다.	a = append(a[:i], append([]T{x}, a[i:]...)...)   // compare to Expand a = append(a[:i], append(make([]T, j), a[i:]...)...)
Insert 최적화   Insert 의 복사를 한 번으로 줄여주는 방법이 오른쪽에 있다. 1) 길이를 하나 늘리고 2)  한칸 뒤로 밀어서 공간을 만든 다음에 (복사!) 3) 집어 넣는다.	s = append(s, 0 /* use the zero value of the element type */) copy(s[i+1:], s[i:]) s[i] = x

 

InsertVector, Push, Pop, Push Front/Unshift,  Pop Front/Shift

 

테스트 코드: https://play.golang.org/p/wY8-ziA9ErF

 

InsertVector   b 라는 녀석을 가운데 넣는 법 a = append(a[:i], append(b, a[i:]...)...) Push   a 의 뒤에 넣는 법 a = append(a, x) Pop   a 의 뒤에서 하나를 빼내는 법 → Push + Pop 은 Stack! x, a = a[len(a)-1], a[:len(a)-1] Push Front/Unshift   앞에다가 집어 넣는 법 a = append([]T{x}, a...) Pop Frotn/Shift   앞에서 빼내는 법 x, a = a[0], a[1:]

Additional Tricks

Filtering without allocating   - 두번째꺼가 위에 이미 있던 필터 - a = a[:n] 이라는 부분이 메모리 재할당 되는 부분을 개선하는 의미가 있다.	b := a[:0] for _, x := range a {         if f(x) {                 b = append(b, x)         } } n := 0 for _, x := range a {         if keep(x) {                 a[n] = x                 n++         } } a = a[:n]
위의 filtering 이후 filter 된 녀석들의 memory leak 을 방지해주는 코드이다. - 다시 말하지만 reference 하는 놈이 없도록 해버리는 거다.	for i := len(b); i < len(a); i++ {         a[i] = nil // or the zero value of T }
Reversing   - 순서를 뒤바꾸는 코드이다. - 양 끝에서부터 가운데로 오며 서로를 바꾼다고 보면 된다.	for i := len(a)/2-1; i >= 0; i-- {         opp := len(a)-1-i         a[i], a[opp] = a[opp], a[i] }
이 방식을 더 많이 본 것 같다. 장단점은 모르겠지만 개인적으로는 이게 더 알아보기 좋다.	for left, right := 0, len(a)-1; left < right; left, right = left+1, right-1 {         a[left], a[right] = a[right], a[left] }
Shuffling   1) i를 처음부터 끝까지 돌면서, 랜덤한 element 와 뒤섞는다. - 몇 번 더 돌리면 더욱 좋을 것도 같다. 2) 그런데 Go 1.10 부터는 math/rand.Suhffle 을 쓰면 된다.   테스트 코드: https://play.golang.org/p/wlaHJwQztCE	for i := len(a) - 1; i > 0; i-- {     j := rand.Intn(i + 1)     a[i], a[j] = a[j], a[i] }
Batching with minimal allocation   Slice 에 대한 배치작업 - Slice 가 무지 길다면 그걸 나눠서 작업하는 것이다.   1) actions 를 batch 단위 3 으로 나눠서 작업하는 것이다. - 예를 들어 100만 element 가 있다면, 1000 개씩 작업하는 식이다. 2) 더 이상 나눌 수 없을때까지 == batchSize 보다 len(actions) 보자 작을때까지 계속한다. - actions 의 앞부분부터 batchSize 만큼 잘라서 - batches 의 이중(?) Slice 에 하나씩 append 하는 것이다. 3) 그리고 자투리가 남으면 마지막 줄에서 자투리만 append 한다.	actions := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} batchSize := 3 var batches [][]int for batchSize < len(actions) {     actions, batches = actions[batchSize:], append(batches, actions[0:batchSize:batchSize]) } batches = append(batches, actions)
테스트 코드   - https://play.golang.org/p/XrHbUCHAzmO - batchSize < len(actions) 부분이 절묘하다.          - actions 가 빈 slice 가 되는걸 막아준다.
In-place deduplicate (comparable)   중복을 막아주는 코드이다.   1) 일단 정렬을 먹여준 다음 2) 앞에서부터 2개씩 같은지 여부를 확인한다. - 같으면 continue 로 j++ 되지 않도록 해준다. 3) 다른 녀석, 정렬되어 있으니 j index 보다 큰 녀석을 만나면 - j 를 하나 늘리고, j index 에 i index 의 값을 넣어준다. 4) 마지막으로  새로운 result 라는 slice 를 만들어서 결과를 넣어주면 된다.   테스트 코드: https://play.golang.org/p/gUzv-QekWU5 - preserve version 은 in slice 안에 기존 element 들을 다 가지고 있다.	import "sort" in := []int{3,2,1,4,3,2,1,4,1} // any item can be sorted sort.Ints(in) j := 0 for i := 1; i < len(in); i++ {         if in[j] == in[i] {                 continue         }         j++         // preserve the original data         // in[i], in[j] = in[j], in[i]         // only set what is required         in[j] = in[i] } result := in[:j+1] fmt.Println(result) // [1 2 3 4]