데이터 구조 와 알고리즘 (Golang 구현) (13) 흔 한 데이터 구조 - 가 변 긴 배열
배열 의 크기 가 고정 되 어 있 기 때문에 데이터 요소 가 매우 많 을 때 고정된 배열 은 이렇게 많은 값 을 저장 할 수 없 기 때문에 가 변 긴 배열 이 나 타 났 다. 이것 도 데이터 구조 이다.
Golang 언어 에서 가 변 긴 배열 은 언어 에 내장 되 어 있다. 절편 slice.slice 은 바 텀 배열 에 대한 추상 적 이 고 통제 이다.그것 은 구조 체 이다.type slice struct {
array unsafe.Pointer
len int
cap int
}
Golang 언어 는 원본 메모 리 를 조작 하 는 지침 이 없 기 때문에 unsafe 가방 은 메모리 포인터 에 대한 조작 을 제공 합 니 다. 일반적인 상황 에서 비 전문 인원 은 사용 하지 않 습 니 다) 매번 고정 용량 의 절편 을 초기 화하 고 절편 내부 에 고정 크기 의 배열 을 유지 할 수 있 습 니 다.
append 새로운 요소 가 부족 할 때 고정 크기 의 배열 이 부족 할 때 자동 으로 확 대 됩 니 다. 예 를 들 어:package main
import "fmt"
func main() {
// 2
array := make([]int, 0, 2)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
// append array
_ = append(array, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
_ = append(array, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
_ = append(array, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
fmt.Println("-------")
//
array = append(array, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
array = append(array, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
array = append(array, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
array = append(array, 1, 1, 1, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
array = append(array, 1, 1, 1, 1, 1, 1, 1, 1, 1)
fmt.Println("cap", cap(array), "len", len(array), "array:", array)
}
출력:
cap 2 len 0 array: []
cap 2 len 0 array: []
cap 2 len 0 array: []
cap 2 len 0 array: []
-------
cap 2 len 1 array: [1]
cap 2 len 2 array: [1 1]
cap 4 len 3 array: [1 1 1]
cap 8 len 7 array: [1 1 1 1 1 1 1]
cap 16 len 16 array: [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
우 리 는
Golang 의 절편 이 제자리 append 가 되 지 않 는 것 을 볼 수 있 습 니 다. 요 소 를 추가 할 때마다 새로운 인용 주 소 를 되 돌려 주 고 이 인용 을 이전의 절편 변 수 를 다시 부여 해 야 합 니 다.그리고 용량 이 부족 하면 자동 으로 배수 가 늘 어 나 고 용량 이 늘어난다.실제로 Golang 절편 길이 가 1024 보다 크 면 1.25 배 에 가 까 운 용량 으로 용량 을 확대 한다.구체 적 으로 표준 라 이브 러 리
runtime 하의 slice.go 문 서 를 참고 할 수 있다.1. 가 변 긴 배열 실현
우 리 는 간단 하고 정 수 를 저장 하 는 가 변 적 이 고 긴 배열 버 전 을 실현 합 니 다.
Golang 의 제한 으로 인해 [n]int 고정 크기 n 의 정수 배열 을 만 들 수 없고 상수 로 만 크기 를 만 들 수 있 습 니 다.그래서 우 리 는 절편 의 일부 기능 을 사용 하여 배열 을 대체 할 것 이다. 절편 자체 가 가 변 적 이 고 긴 배열 이지 만 우 리 는 그것 의
append 기능 을 사용 하지 않 고 배열 로 만 사용 할 것 이다.import (
"sync"
)
//
type Array struct {
array []int // ，
len int //
cap int //
lock sync.Mutex //
}
1.1. 배열 초기 화
len 개의 요 소 를 만 들 고 용량 cap 의 가 변 긴 배열 을 만 듭 니 다.//
func Make(len, cap int) *Array {
s := new(Array)
if len > cap {
panic("len large than cap")
}
//
array := make([]int, cap, cap)
//
s.array = array
s.cap = cap
s.len = 0
return s
}
주로 만 용량 과 만 크기 의 절편 을 이용 하여 고정 배열, 구조 체
Array 안의 필드 len 와 cap 를 이용 하여 값 의 접근 을 제어 한다.가 변 배열 len > cap 을 설정 할 수 없습니다.시간 복잡 도 는 다음 과 같다.
O(1) 메모리 공간 을 분배 하고 몇 개의 값 을 설정 하 는 것 이 상수 시간 이기 때문이다.1.2. 요소 추가
//
func (a *Array) Append(element int) {
//
a.lock.Lock()
defer a.lock.Unlock()
// ，
if a.len == a.cap {
// ， ，
newCap := 2 * a.len
// 0， 1
if a.cap == 0 {
newCap = 1
}
newArray := make([]int, newCap, newCap)
//
for k, v := range a.array {
newArray[k] = v
}
//
a.array = newArray
a.cap = newCap
}
//
a.array[a.len] = element
// +1
a.len = a.len + 1
}
먼저 가 변 긴 배열 에 요 소 를 추가 하면 자 물 쇠 를 추가 하여 병발 안전 을 확보 할 수 있 습 니 다.그리고 값 을 배열 에 넣 습 니 다.
a.array[a.len] = element 그리고 len + 1 실제 크기 가 하나 더 많아 졌 음 을 나타 냅 니 다.실제 크기
len = cap 는 위치 가 다 떨 어 졌 음 을 나타 내 고 남 은 공간 이 새 값 을 넣 지 않 으 면 고정 크기 2*len 의 새 배열 을 만들어 서 오래된 배열 을 교체 합 니 다. a.array = newArray 물론 용량 도 커 집 니 다. a.cap = newCap처음에 설 치 된 용량 cap = 0 이 라면 새로운 용량 은 1 부터 다.요 소 를 추가 할 때 주로 오래된 배열 의 데 이 터 를 새 배열 로 이동 합 니 다. 시간 복잡 도 는 다음 과 같 습 니 다.
O(n)물론 용량 이 충분 한 경우 시간 복잡 도 는 다음 과 같다. O(1).여러 요 소 를 추가 하 는 방법:
//
func (a *Array) AppendMany(element ...int) {
for _, v := range element {
a.Append(v)
}
}
간단하게 옮 겨 다 니 면서
Append 함 수 를 호출 합 니 다.그 중에서 ...int 는 Golang 의 언어 특징 으로 여러 함수 변 수 를 나타 낸다.1.3. 지정 한 다음 요 소 를 가 져 옵 니 다.
//
func (a *Array) Get(index int) int {
//
if a.len == 0 || index >= a.len {
panic("index over len")
}
return a.array[index]
}
가 변 긴 배열 의 실제 크기 가 0 이거 나 아래 표
index 가 실제 길이 len 를 초과 하면 panic 경 계 를 넘 을 것 이다.아래 표 시 된 값 만 가 져 오기 때문에 시간 복잡 도 는
O(1) 입 니 다.1.4. 실제 길이 와 용량 가 져 오기
//
func (a *Array) Len() int {
return a.len
}
//
func (a *Array) Cap() int {
return a.cap
}
시간 복잡 도
O(1).예시
현재 우 리 는 완전한 가 변 긴 배열 의 예 를 실행 합 니 다.
package main
import (
"fmt"
"sync"
)
//
type Array struct {
array []int // ，
len int //
cap int //
lock sync.Mutex //
}
//
func Make(len, cap int) *Array {
s := new(Array)
if len > cap {
panic("len large than cap")
}
//
array := make([]int, cap, cap)
//
s.array = array
s.cap = cap
s.len = 0
return s
}
//
func (a *Array) Append(element int) {
//
a.lock.Lock()
defer a.lock.Unlock()
// ，
if a.len == a.cap {
// ， ，
newCap := 2 * a.len
// 0， 1
if a.cap == 0 {
newCap = 1
}
newArray := make([]int, newCap, newCap)
//
for k, v := range a.array {
newArray[k] = v
}
//
a.array = newArray
a.cap = newCap
}
//
a.array[a.len] = element
// +1
a.len = a.len + 1
}
//
func (a *Array) AppendMany(element ...int) {
for _, v := range element {
a.Append(v)
}
}
//
func (a *Array) Get(index int) int {
//
if a.len == 0 || index >= a.len {
panic("index over len")
}
return a.array[index]
}
//
func (a *Array) Len() int {
return a.len
}
//
func (a *Array) Cap() int {
return a.cap
}
//
func Print(array *Array) (result string) {
result = "["
for i := 0; i < array.Len(); i++ {
//
if i == 0 {
result = fmt.Sprintf("%s%d", result, array.Get(i))
continue
}
result = fmt.Sprintf("%s %d", result, array.Get(i))
}
result = result + "]"
return
}
func main() {
// 3
a := Make(0, 3)
fmt.Println("cap", a.Cap(), "len", a.Len(), "array:", Print(a))
//
a.Append(10)
fmt.Println("cap", a.Cap(), "len", a.Len(), "array:", Print(a))
//
a.Append(9)
fmt.Println("cap", a.Cap(), "len", a.Len(), "array:", Print(a))
//
a.AppendMany(8, 7)
fmt.Println("cap", a.Cap(), "len", a.Len(), "array:", Print(a))
}
출력:
cap 3 len 0 array: []
cap 3 len 1 array: [10]
cap 3 len 2 array: [10 9]
cap 6 len 4 array: [10 9 8 7]
용량 이 자동 으로 배로 늘 어 나 는 것 을 볼 수 있다.
총화
가 변 긴 배열 은 실제 개발 에 있어 서 고정 크기 배열 을 바탕 으로 자동 으로 용량 확장 을 하 는 데 자주 사용 된다.
이 데이터 구조의 사용 빈도 가 너무 높 기 때문에
Golang 이 데이터 형식 을 자동 으로 제공 합 니 다. 절편 (가 변 긴 배열).여러분 은 일반적으로 개발 과정 에서 이 유형 을 직접 사용 하면 됩 니 다.시리즈 문장 입구
저 는 진성 입 니 다. 제 가 직접 쓴 데이터 구조 와 알고리즘 (Golang 실현) 을 읽 는 것 을 환영 합 니 다. 글 은 더욱 우호 적 인 GitBook 을 읽 는 데 첫 발 을 내 디 뎠 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
