Golang 가방 과 교체 기의 실현

데이터 구조 와 몇 개의 기본 API

package Bag

type Bag struct {
	first *node
	n     int
}

type node struct {
	item interface{}
	next *node
}

func NewBag() Bag {
	return Bag{}
}

func (b Bag) IsEmpty() bool {
	return b.n == 0
}

func (b Bag) Size() int {
	return b.n
}

func (b *Bag) Add(item interface{}) {
	oldfirst := b.first
	b.first = &node{}
	b.first.item = item
	b.first.next = oldfirst
	b.n++
}

간단 한 가방 교체 인터페이스
go 언어 는 원생 의 교체 인터페이스 지원 을 제공 하지 않 았 기 때문에 교 체 를 사용 하려 면 스스로 실현 해 야 한다. 공교롭게도 교 체 는 가방 이라는 데이터 구조의 중요 한 방법 이다.다음은 간단 한 교체 실현 이다.

//             
func (b Bag) Iterator() []interface{} {
	s := []interface{}{}
	p := b.first
	for i := 0; i < b.n; i++ {
		s = append(s, p.item)
		p = p.next
	}
	return s
}

이러한 간단 한 교체 실현 원 리 는 링크 를 옮 겨 다 니 며 그 중의 모든 요 소 를 하나의 절편 으로 내 보 낸 다음 에 돌아 오 는 것 이다. 그러면 go 의 for range 교체 요 소 를 통 해 교체 할 수 있다.이 방안 은 교체 가 시 작 될 때 가방 에 있 는 모든 데 이 터 를 메모리 에 복사 합 니 다. 이렇게 하면 간단 하고 교체 하 는 속도 가 빠 르 지만 절편 을 만 드 는 데 시간 이 걸 리 고 두 배의 메모 리 를 차지 하 므 로 데이터 양 이 많은 경우 에 적합 하지 않 습 니 다.
개 선 된 교체 기
이 교체 기의 디자인 방향: 가방 류 에 변수 index 를 저장 하여 현재 교체 되 는 위 치 를 기록 합 니 다.

type Bag struct {
	first *node
	n     int
	index *node
}

//       

//      
func (b *Bag) InitIterator() {
	b.index = b.first
}

//       
func (b Bag) HasNext() bool {
	return b.index != nil
}

//       
func (b *Bag) Next() interface{} {
	item := b.index.item
	b.index = b.index.next
	return item
}

다음은 교체 기 를 테스트 하 는 코드 입 니 다.

func main() {
	b := Bag.NewBag()
	b.Add(1)
	b.Add(2)
	b.Add(3)
	for b.InitIterator(); b.HasNext(); {
		fmt.Println(b.Next())
	}
}

콘 솔 출력:

[Running] go run "/Users/bbfat/Desktop/Learn/    /  /main.go"
3
2
1

[Done] exited with code=0 in 0.231 seconds

이런 교체 방식 은 시간 효율 과 공간 효율 에 있어 좋 은 표현 을 하지만 특정한 유형 에서 교체 기능 을 실현 하려 면 이 세 개의 인 터 페 이 스 를 정의 해 야 한다. 추상 적 인 청 두 는 높 지 않다.
협 정과 인 터 페 이 스 를 활용 하여 추상 적 인 교체 기 류 를 실현 하 다.
go 언어의 가장 큰 특징 은 바로 동시성 이다. 이것 은 그의 협의 체제 덕분이다. 나 는 지금 협의 와 통 로 를 이용 하여 교체 기 류 를 구축 할 것 이다.

package Iterator

//       
//         StartIterate  ，    ：
//                    
//   nil      
type IteratorObj interface {
	StartIterate(ch chan interface{})
}

type Iterator struct {
	it IteratorObj
	ch chan interface{}
}

//    Iterator  
func InitIterator(it IteratorObj) Iterator {
	ch := make(chan interface{})
	go it.StartIterate(ch)
	return Iterator{it, ch}
}

//               
func (it Iterator) Next() interface{} {
	return 

Start Iterate 인터페이스 방법
교체 가능 류 는 이 인 터 페 이 스 를 실현 해 야 Iterator 로 교체 할 수 있 습 니 다. 이 인터페이스 방법 은 하나의 협 정 으로 작 동 되 고 교체 가능 류 는 자신의 논 리 를 활용 하여 교체 할 수 있 으 며 매번 교체 되 는 결 과 를 버퍼 없 는 채널 ch 로 전달 할 수 있 습 니 다.
InitIterator 함수
이 함 수 는 Iterator Obj 인터페이스 형식 을 매개 변수 로 받 아들 여 인터페이스 형식 채널 을 만 든 다음 협 정 을 시작 하여 Iterator 대상 을 되 돌려 줍 니 다.
Next 방법
이 방법 은 Iterator 대상 에 작용 하 며, 이 방법 은 ch 채널 에서 전 송 된 데 이 터 를 수신 하고 되 돌려 줍 니 다.
가방 Iterator Obj 인터페이스 구현
Bag 클래스 아래 에 방법 을 하나 더 추가 하 겠 습 니 다.

//       
func (b Bag) StartIterate(ch chan interface{}) {
	index := b.first
	for {
		if index == nil {
			ch 

일반적인 링크 가 옮 겨 다 니 며 채널 전송 데 이 터 를 추가 한 것 이다.
가방 테스트 협 정 교체 통과

func main() {
	b := Bag.NewBag()
	for i := 0; i < 100; i++ {
		b.Add(i)
	}

    //            
	it := Iterator.InitIterator(b)
	for v := it.Next(); v != nil; v = it.Next() {
		fmt.Println(v)
	}
}

테스트 출력:

[Running] go run "/Users/bbfat/Desktop/Learn/    /  /main.go"
99
98
//    
1
0

[Done] exited with code=0 in 0.26 seconds

테스트 성공!
서로 다른 교체 방식 의 성능 차 이 를 테스트 하 다.
1. 슬라이스 생 성

func main() {
	b := Bag.NewBag()
	for i := 0; i < 10000000; i++ {
		b.Add(i)
	}
	for _, i := range b.Iterator() {
		fmt.Print(i)
	}
}

테스트 번호
사용 시간 (s)
1
3.091
2
2.606
3
2.486
4
2.478
5
2.538
6
3.031
고 르 게 하 다
2.075
2. 직접 교체 법

func main() {
	b := Bag.NewBag()
	for i := 0; i < 10000000; i++ {
		b.Add(i)
	}
	for b.InitIterator(); b.HasNext(); {
		fmt.Print(b.Next())
	}
}

테스트 번호
사용 시간 (s)
1
1.183
2
1.131
3
1.426
4
1.584
5
1.139
6
1.085
고 르 게 하 다
1.258
3. 협정 교체 법

func main() {
	b := Bag.NewBag()
	for i := 0; i < 10000000; i++ {
		b.Add(i)
	}
	it := Iterator.InitIterator(b)
	for v := it.Next(); v != nil; v = it.Next() {
		fmt.Print(v)
	}
}

테스트 번호
사용 시간 (s)
1
1.154
2
1.555
3
1.491
4
1.541
5
1.526
6
1.544
고 르 게 하 다
1.468
종합 하여 서술 하 다
절편 을 만 드 는 교체 방법 은 좋 은 선택 이 아니다. 메모리 만 차지 하 는 것 이 아니 라 소모 시간 도 길 고 직접 교체 법의 효율 이 가장 높 지만 실현 하기 가 비교적 번거롭다. 협 정 교체 법의 효율 과 직접 교 체 는 조금 차이 가 나 지만 실현 하기 가 매우 편안 하 다. 그래서 나의 선택 은 협 정 교체 법 을 사용 하 는 것 이다. 이것 도 go 라 는 언어의 매력 이다.
협정 교체 법의 개선
현재 의 협 정 교체 방법 에는 우아 하 게 협 정 에서 물 러 날 수 없 는 결함 이 있 습 니 다. 만약 에 교체 가 절반 까지 강제 적 으로 끝나 지 않 으 면 교 체 를 담당 하 는 협 정 은 계속 스 택 에서 차단 상 태 를 유지 하 는 것 이 매우 불쾌 합 니 다. 그 다음 에 저 는 이 문 제 를 개선 하려 고 합 니 다.
Iterator Obj 승급

type IteratorObj interface {
	StartIterate(ch chan interface{}, stop chan bool)
}

협정 종 료 를 제어 할 수 있 는 통로 가 추가 되 었 기 때문에 가방 류 의 인터페이스 실현 도 조정 해 야 한다.

//       
func (b Bag) StartIterate(ch chan interface{}, stop chan bool) {
	index := b.first
	for {
		select {
		case 

selection 구문
이것 은 go 언어 가 협정 을 더욱 잘 지원 하기 위 한 특유 의 문장 입 니 다. 이것 은 흔히 볼 수 있 는 switch 와 유사 하지만, 케이스 마다 통신 과 관련 된 표현 식 이 어야 합 니 다. go 의 switch 는 다른 언어 와 다른 점 이 바로 자체 break 입 니 다. select 도 마찬가지 입 니 다.stop 채널 에서 전 달 된 메 시 지 를 받 았 을 때 함수 가 돌아 오고 협 정 은 우아 하 게 종료 되 며 다른 상황 에서 이전의 교체 논 리 를 계속 수행 합 니 다.
Finish 함수
이 함 수 는 교체 협 정 에 종료 신 호 를 보 내 는 데 사 용 됩 니 다.

//      
func (it Iterator) Finish() {
	mutex := sync.Mutex{}
	mutex.Lock()
	

이 중 에는 Lock () 과 Unlock () 사이 의 코드 가 다른 협 정 에 의 해 중단 되 지 않도록 상호 배척 자 물 쇠 를 사용 했다.이렇게 하면 우 리 는 먼저 자 물 쇠 를 잠 근 다음 에 ch 채널 이 막 힌 데 이 터 를 꺼 내 서 신 호 를 stop 채널 로 보 내 고 마지막 으로 자 물 쇠 를 풀 어 교체 협 정 을 계속 집행 하 게 한다. 이때 교체 협 정 은 stop 채널 에서 들 려 오 는 신 호 를 감 측 할 것 이다. 그러면 return 탈퇴 를 실행 할 것 이다.
테스트

func main() {
	b := Bag.NewBag()
	for i := 0; i < 10; i++ {
		b.Add(i)
	}
	it := Iterator.InitIterator(b)
	for v := it.Next(); v != nil; v = it.Next() {
		fmt.Print(v)
		if v.(int) == 5 {
			it.Finish()
			return
		}
	}
}

콘 솔 출력:

API server listening at: 127.0.0.1:6347
98765

테스트 성공!
이 절 코드