GoLang 의 절편 확장 메커니즘

6353 단어 golang
절편 용량[5]int 은 수조 이 고 []int 는 절편 이다.두 사람 은 비슷 해 보이 지만 사실은 근본적으로 다른 데이터 구조 이다.
절편 의 데이터 구조 에는 배열 을 가리 키 는 지침 array, 현재 길이 len, 그리고 최대 용량 cap 이 포함 되 어 있다.make([]int, len) 를 사용 하여 절편 을 만 들 때 실제 세 번 째 선택 가능 한 매개 변수 cap, 즉 make([]int, len, cap) 도 있다.성명 하지 않 은 상태 cap 에서 묵인 cap=len.절편 길이 가 용량 을 초과 하지 않 았 을 때 절편 에 데 이 터 를 추가 하면 지침 의 값 이 바 뀌 지 않 습 니 다.
절편 array 을 조작 하면 길이 가 용량 을 초과 할 때 새로운 배열 을 만 들 고 기 존 절편 과 분 리 될 수 있다.다음 예 에서
 
a := make([]int, 5)
b := a[0:4]
a = append(a, 1)
a[1] = 5
fmt.Println(b)
// [0 0 0 0]
fmt.Println(a)
// [0 5 0 0 0 1]
append 의 길이 가 용량 을 초과 하기 때문에 절편 a 은 성장 후의 새로운 배열 을 가리 키 고 a 은 여전히 원래 의 오래된 배열 을 가리킨다.따라서 이후 b 에 대한 조작 은 a 에 영향 을 주지 않 는 다.
비교 해 보다
 
a := make([]int, 5, 6)
b := a[0:4]
a = append(a, 1)
a[1] = 5
fmt.Println(a, b)
// [0 5 0 0 0 1] [0 5 0 0]

이 사례 에서 b 의 용량 은 6 이기 때문에 a 이후 용량 을 초과 하지 않 았 기 때문에 append 지침 은 변 하지 않 았 다.따라서 array 에 대한 조작 은 a 에 도 영향 을 미 쳤 다.
용량 확장 메커니즘b 이런 방식 으로 절편 을 만 드 는 것 이 어떤 상황 인지 살 펴 보 자.
 
a := []int{}
for i := 0; i < 16; i++ {
    a = append(a, i)
    fmt.Print(cap(a), " ")
}
// 1 2 4 4 8 8 8 8 16 16 16 16 16 16 16 16

이 를 통 해 알 수 있 듯 이 빈 슬라이스 의 용량 은 0 이지 만 뒤쪽 에 슬라이스 에 요 소 를 추가 할 때 슬라이스 할 때마다 용량 이 달라 지 는 것 은 아니다.용량 을 늘 리 면 새 배열 을 만들어 야 하 는데, 이 럴 때 는 원래 배열 에 있 던 모든 요 소 를 새 배열 로 복사 해 야 하기 때문에 비용 이 많이 들 기 때문에 GoLang 은 새 배열 을 만들어 야 하 는 횟수 를 줄 이기 위해 확장 체 제 를 설계 했다.그러나 이 로 인해 a := []int{} 새 배열 을 만 들 었 는 지 여 부 를 직접적 으로 판단 할 수 없 게 되 었 다.
한 번 에 여러 요 소 를 추가 하면 용량 은 어떻게 변 할 까?다음 두 가지 예 를 비교 해 보 세 요.
 
a := []int{}
for i := 0; i < 16; i++ {
    a = append(a, 1, 2, 3, 4, 5)
    fmt.Print(cap(a), " ")
}
// 6 12 24 24 48 48 48 48 48 96 96 96 96 96 96 96 
a := []int{}
for i := 0; i < 16; i++ {
    a = append(a, 1, 2, 3, 4, 5, 6)
    fmt.Print(cap(a), " ")
}
// 6 12 24 24 48 48 48 48 96 96 96 96 96 96 96 96

그렇다면 빈 슬라이스 에 append 요 소 를 삽입 하면 용량 이 2n-1 으로 설정 되 는 것 일 까?다른 데이터 형식 을 시험 해 보 겠 습 니 다.
 
// int8
a := []int8{}
for i := 0; i < 16; i++ {
    a = append(a, 1, 2, 3, 4, 5, 6)
    fmt.Print(cap(a), " ")
}
// 8 16 32 32 32 64 64 64 64 64 128 128 128 128 128 128

// int16
fmt.Println()
b := []int16{}
for i := 0; i < 16; i++ {
    b = append(b, 1, 2, 3, 4, 5)
    fmt.Print(cap(b), " ")
}
// 8 16 32 32 32 64 64 64 64 64 128 128 128 128 128 128

// bool
fmt.Println()
c := []bool{}
for i := 0; i < 16; i++ {
    c = append(c, true, false, true, false, false)
    fmt.Print(cap(c), " ")
}
// 8 16 32 32 32 64 64 64 64 64 128 128 128 128 128 128

// float32
fmt.Println()
d := []float32{}
for i := 0; i < 16; i++ {
    d = append(d, 1.1, 2.2, 3.3, 4.4, 5.5)
    fmt.Print(cap(d), " ")
}
// 8 16 16 32 32 32 64 64 64 64 64 64 128 128 128 128 

// float64
fmt.Println()
e := []float64{}
for i := 0; i < 16; i++ {
    e = append(e, 1.1, 2.2, 3.3, 4.4, 5.5)
    fmt.Print(cap(e), " ")
}
// 6 12 24 24 48 48 48 48 48 96 96 96 96 96 96 96 

// string
fmt.Println()
f := []string{}
for i := 0; i < 16; i++ {
    f = append(f, "1.1", "2.2", "3.3", "4.4", "5.5")
    fmt.Print(cap(f), " ")
}
// 5 10 20 20 40 40 40 40 80 80 80 80 80 80 80 80 

// []int
fmt.Println()
g := [][]int{}
g1 := []int{1, 2, 3, 4, 5}
for i := 0; i < 16; i++ {
    g = append(g, g1, g1, g1, g1, g1)
    fmt.Print(cap(g), " ")
}
// 5 10 20 20 42 42 42 42 85 85 85 85 85 85 85 85

절편 에 대응 하 는 데이터 유형 에 따라 용량 증가 방식 도 큰 차이 가 있 음 을 알 수 있다.관련 소스 코드 는 src / runtime / msize. go, src / runtime / mksizeclasses. go 등 을 포함한다.
우 리 는 절편 이 처음에 비어 있 지 않 은 상황 을 다시 한번 보 았 다.
 
a := []int{1, 2, 3}
fmt.Println(cap(a))
// 3
for i := 0; i < 16; i++ {
    a = append(a, 1, 2)
    fmt.Print(cap(a), " ")
}
// 6 12 12 12 24 24 24 24 24 24 48 48 48 48 48 48

방금 빈 슬라이스 에 int 5 개 를 추가 한 것 과 일치 하 며, 3 개의 int 가 있 는 슬라이스 에 int 2 개 를 추가 하여 용량 이 6 으로 증가 한 것 을 볼 수 있다.
주의해 야 할 것 은 2n 절편 을 확대 할 때 용량 이 일정한 범 위 를 초과 하면 처리 전략 이 달라 질 수 있다 는 것 이다.아래 의 이 예 를 볼 수 있다.
 
a := []int{1, 2, 3, 4}
fmt.Println(cap(a))
// 4
for i := 0; i < 20; i++ {
    a = append(a, a...)
    fmt.Print(cap(a), " ")
}
// 8 16 32 64 128 256 512 1024 2560 5120 10240 20480 40960 80896 158720 310272 606208 1184768 2314240 4520960

구체 적 으로 왜 이런 변화 과정 인지, 소스 코드 에서 답 을 찾 아야 한다.다음은 append 중의 src/runtime/slice.go 함수 중의 핵심 부분 이다.
 
// src/runtime/slice.go
func growslice(et *_type, old slice, cap int) slice {
// ...    
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            for 0 < newcap && newcap < cap {
                newcap += newcap / 4
            }
            // Set newcap to the requested cap when
            // the newcap calculation overflowed.
            if newcap <= 0 {
                newcap = cap
            }
        }
    }
// ...    
}
  • 필요 한 용량 이 원 절편 용량 의 두 배 를 초과 할 때 필요 한 용량 을 새로운 용량 으로 사용한다.
  • 원 절편 의 길이 가 1024 보다 작 을 때 새 절편 의 용량 은 바로 배가 된다.그러나 원 절편 의 용량 이 1024 보다 크 면 새로운 용량 이 필요 한 용량 을 초과 할 때 까지 25% 를 반복 적 으로 증가 할 것 이다.

  • 결론.
    GoLang 의 절편 확장 체 제 는 절편 의 데이터 유형, 원래 절편 의 용량, 필요 한 용량 과 관계 가 있 고 복잡 하 다.흔히 볼 수 있 는 데이터 유형 에 대해 요소 의 수량 이 비교적 적 을 때 대체적으로 확장 은 배로 진행 된다 고 볼 수 있다.그러나 구체 적 인 상황 은 구체 적 으로 분석 해 야 한다.
    절편 확장 문제 로 인해 bug 가 발생 하 는 것 을 피하 기 위해 서 는 필요 할 때 growslice 데 이 터 를 복사 하여 새로운 절편 을 얻어 후속 작업 이 예상 치 못 한 부작용 을 가 져 오지 않도록 하 는 것 이 좋 습 니 다.
    참고 문헌
  • SliceTricks
  • Arrays, slices (and strings): The mechanics of 'append'
  • - 고 - 속 의 각종 함정 을 어떻게 피 하 는 지
  • 좋은 웹페이지 즐겨찾기