[Go] A tour of go Exercise: Equivalent Binary Trees 풀이

tour.golang.org/concurrency/8

A Tour of Go

2개의 이진트리를 병렬로 실행하고 순회한 값이 똑같은지 비교하는 문제다.

Walk는 쉽게 짰고 Same이 문제인데 컴퓨터 3년 하면서 이진트리를 병렬처리해서 비교해볼 생각을 안해서 난감했다.

정확히는 goroutine까지는 괜찮은데 채널 값을 뽑아서 비교하는게 문제였다. 

아래 코드는 채널 값 비교를 빼고 구현한 코드다.

package main

import "golang.org/x/tour/tree"
import "fmt"
// Walk walks the tree t sending all values
// from the tree to the channel ch.
// 바이너리트리 순회해서 채널에 값을 넣어야함
// 순회 방식은 DFS
func Walk(t *tree.Tree, ch chan int) {
	if t != nil {
		Walk(t.Left, ch)
		ch<-t.Value
		Walk(t.Right, ch)
	}
}

// Same determines whether the trees
// t1 and t2 contain the same values.

func Same(t1, t2 *tree.Tree) bool {
	ch1 := make(chan int)
	ch2 := make(chan int)
	go Walk(t1, ch1)
	go Walk(t2, ch2)
	
	// 채널에 들어있는 값을 queue 형태로 비교
	// 다르면 return false
	return true
}

func main() {
	if Same(tree.New(1), tree.New(2)) {
		fmt.Println("true")
	} else {
		fmt.Println("false")
	}
}

비교하는 방법은 2개 정도로 생각했다.

1. channel에 값이 하나씩 서로 들어올 때 까지 다음 채널에 대해 blocking해서 하나씩 비교하기

2. goroutine이 끝나고 channel 값을 다른곳에 저장해서 나중에 한꺼번에 비교하기

 

1번의 경우는 매 순간 비교하니 불필요한 연산을 줄일 수 있다.

2번의 경우는 상대적으로 1번보다 쉽게 구현할 수 있을 것 같다.

 

2번의 경우가 더 쉬워보여서 시도했지만 비교하기 전에 고루틴이 뻗어버린다.

 

1번의 방법으로 방향을 선회했다.

잘 굴러가나 싶었지만? close로 채널을 닫은 후가 문제다. 

여전히 goroutine으로 동작하고 있는 Walk 함수 2개는 실행중이면서 닫힌 채널에 데이터를 넣고 있으니 말이다.

이  문제를 해결할 방법을 찾아야 하는데 

2시간동안 삽질하면서 내린 결론은 goroutine은 호출한 괄호영역 안에서 정리해줘야 한다.

kill goroutine 하고 싶은데 그럴 수가 없다.

 

그래서 아래와 같이 for select를 통해 각 채널값을 저장하는 방식을 채택했다.

하지만 결과를 보니 아무것도 담기지 않는다.

case문에 도달하기전에 채널이 비어있어서 default로 바로 바로 빠지기 때문이다.

 

결국 나는 머리를 쥐어 싸멨지만 내가 원하는 방법을 구현할 능력이 부족했다..

그래서 다른 사람들 것을 참고해보니 함수를 하나 더 빼거나, 클로저를 사용하여 goroutine을 정상적으로 종료시켜주거나 이진트리의 요소가 10개라고 가정하고 코드를 구현한다.

 

함수 하나 더 생성해서 처리해주기

gist.github.com/kaipakartik/8120855

Exercise: Equivalent Binary Trees

 

요소 10개라고 가정하고 구현 codereview.stackexchange.com/questions/90426/equivalent-binary-trees-a-tour-of-go/119430

Equivalent binary trees (A Tour of Go)

익명함수를 고루틴에 집어넣고 defer(연산이 완료되도 함수가 끝날 때 처리함)를 사용해서 close하기 git.ikrypto.club/worf/equivalent-binary-trees/src/7404bc031c9bd6e8c8b3174e0a05330d636435e1/exercise-equivalent-binary-trees.go

worf/equivalent-binary-trees

 

고루틴에 대해서 좀 더 이해가 필요한 것 같다. 책 두권을 샀는데 그 책들 읽으면서 익숙해질 것 같다.

 

병렬처리는 옛날부터 갖고 있던 로망이다. C++에서 동시성은 항상 잘 다루고 싶었던 주제였다. 병렬 컴퓨팅과 그를 위한 아키텍처링은 흥미로운 주제다. 

잘한다는 소리를 들을 때 까지 삽질 하면서 성장하는게 국룰이다. 늘 그랬듯이