比较两个树在Golang中是否等价，使用goroutines。

huangapple
go评论144阅读模式
英文:

Compare Two trees are equivalent in Golang Using goroutines

问题

不使用通道，我可以比较这两棵树是否相等，但是使用通道时，我无法弄清楚如何做到这一点。

以下是使用通道编写的示例代码：

  1. func Walk(t *Tree, ch chan int) {
  2.     if t == nil {
  3.         return
  4.     }
  5.     Walk(t.Left, ch)
  6.     ch <- t.Value
  7.     Walk(t.Right, ch)
  8. }
  10. func Same(t1, t2 *Tree) bool {
  11.     t1Ch := make(chan int)
  12.     t2Ch := make(chan int)
  14.     Walk(t1, t1Ch)
  15.     Walk(t2, t2Ch)
  17.     output := make(chan bool)
  18.     go func() {
  19.         n1 := <-t1Ch
  20.         n2 := <-t2Ch
  21.         output <- n1 == n2
  22.     }()
  24.     return <-output
  25. }
  27. func main() {
  28.     fmt.Println((&root, &root1))
  29. }

注意：你可以在这里找到完整的描述：https://go.dev/tour/concurrency/7

英文:

Without using channels i am able to compare the two trees are Equivalent or not but with using the channels i am not able to figure it out how to do.

Here is my sample code written using channels.

  1. func Walk(t *Tree, ch chan int) {
  2.     if t == nil {
  3. 	    return
  4.     }
  5.     Walk(t.Left, ch)
  6.     ch &lt;- t.Value
  7.     Walk(t.Right, ch)
  8. }
  10. func Same(t1, t2 *Tree) bool {
  12. 	t1Ch := make(chan int)
  13. 	t2Ch := make(chan int)
  15. 	Walk(t1, t1Ch)
  16. 	Walk(t2, t2Ch)
  17. 	output := make(chan bool)
  18. 	go func() {
  19. 		n1 := &lt;-t1Ch
  20. 		n2 := &lt;-t2Ch
  21. 		output &lt;- n1 == n2
  22. 	}()
  23. 	return &lt;-output
  25. }
  27. func main() {
  28. 	fmt.Println((&amp;root, &amp;root1))
  29. }

Note:: U can find the full description here https://go.dev/tour/concurrency/7

答案1

得分: 1

我发现了几个问题：

  • Walk 函数从未关闭通道，这可能导致读取者/接收者一直等待，无限期地阻塞或达到死锁。

我建议在完全遍历树之后关闭通道。

  • 在 Same 函数中，你调用了两次 Walk，但第一次调用会无限期地阻塞，因为它将尝试向一个无缓冲通道发送数据（t1Ch := make(chan int)），而没有人在读取/消费它。

给通道添加缓冲区可能看起来是一个简单的修复方法，但我不建议这样做，因为你无法预测树的大小，所以它是不可靠的，而且你只是把问题推到了后面。

尝试在一个 goroutine 中调用 Walk，这样你的 Same 函数就可以继续执行而不被阻塞。

英文:

A few issues I spotted:

  • The Walk function never closes the channel, which might leave readers/receivers waiting for more, blocking indefinitely or reaching a deadlock.
    > I'd recommend closing the channel after you are done fully walking the tree.

  • In the Same function, you call Walk twice, but the first one will block indefinitely, given that it will try to send stuff to an unbuffered channel (t1Ch := make(chan int)), and no one is reading/consuming it yet.
    > Adding a buffer to the channels might seem like an easy fix but I wouldn't recommend it, you can't predict the size of the tree so it's unreliable, and you would just be kicking the problem down the road.

> Try calling Walk in a goroutine, so your Same function can continue unblocked.

答案2

得分: 1

首先，当完成遍历树时，你应该关闭通道。可以通过将递归函数分离出来来实现这一点：

  1. func Walk(t *tree.Tree, ch chan int) {
  2.     defer close(ch)
  3.     if t != nil {
  4.         ch <- t.Value
  5.         walkRecursively(t.Left, ch)
  6.         walkRecursively(t.Right, ch)
  7.     }
  8. }
  10. func walkRecursively(t *tree.Tree, ch chan int) {
  11.     if t != nil {
  12.         ch <- t.Value
  13.         walkRecursively(t.Left, ch)
  14.         walkRecursively(t.Right, ch)
  15.     }
  16. }

现在，你的Same()函数可以遍历这两个通道，并知道何时完成工作：

  1. func Same(t1, t2 *tree.Tree) bool {
  2.     // 为两棵树创建两个通道
  3.     ch1 := make(chan int)
  4.     ch2 := make(chan int)
  5.     
  6.     // 两个整数切片用于存储结果
  7.     sequence1 := []int{}
  8.     sequence2 := []int{}
  9.     
  10.     // 两个 goroutine 将值推送到通道中
  11.     // 注意！这些必须是 goroutine
  12.     go Walk(t1, ch1)
  13.     go Walk(t2, ch2)
  14.     
  15.     // 遍历通道以填充序列变量
  16.     for n1 := range ch1 {
  17.         sequence1 = append(sequence1, n1)    
  18.     }
  19.     for n2 := range ch2 {
  20.         sequence2 = append(sequence2, n2)    
  21.     }
  23.     // 由于树的结构是随机的，我们对序列进行排序
  24.     sort.Ints(sequence1)
  25.     sort.Ints(sequence2)
  27.     // slicesAreEqual 是一个辅助函数
  28.     return slicesAreEqual(sequence1, sequence2)
  29. }

你的辅助函数可能如下所示：

  1. func slicesAreEqual(a, b []int) bool {
  2.     if len(a) != len(b) {
  3.         return false
  4.     }
  5.     for i, v := range a {
  6.         if v != b[i] {
  7.             return false
  8.         }
  9.     }
  10.     return true
  11. }
英文:

First of all, you should close your channels when finished walking the tree. This could be accomplished by seperating out your recursive function like so:

  1. func Walk(t *tree.Tree, ch chan int) {
  2. 	defer close(ch)
  3. 	if t != nil {
  4. 		ch &lt;- t.Value
  5. 		walkRecursively(t.Left, ch)
  6. 		walkRecursively(t.Right, ch)
  7. 	}
  8. 	
  9. }
  11. func walkRecursively(t *tree.Tree, ch chan int) {
  12. 	if t != nil {
  13. 		ch &lt;- t.Value
  14. 		walkRecursively(t.Left, ch)
  15. 		walkRecursively(t.Right, ch)
  16. 	}
  17. }

Now your Same() function can range over the two channels and know when the work is done:

  1. func Same(t1, t2 *tree.Tree) bool {
  3.     // two channels for walking over two trees
  4. 	ch1 := make(chan int)
  5. 	ch2 := make(chan int)
  6. 	
  7.     // two integer slices to capture two results
  8. 	sequence1 := []int{}
  9. 	sequence2 := []int{}
  10. 	
  11.     // two go routines to push values to the channels
  12.     // IMPORTANT! these must be go routines
  13. 	go Walk(t1, ch1)
  14. 	go Walk(t2, ch2)
  15. 	
  16.     // range over the channels to populate the sequence vars
  17. 	for n1 := range ch1 {
  18. 		sequence1 = append(sequence1, n1)	
  19. 	}
  20. 	for n2 := range ch2 {
  21. 		sequence2 = append(sequence2, n2)	
  22. 	}
  24.     // since trees are randomly structured, we sort
  25. 	sort.Ints(sequence1)
  26. 	sort.Ints(sequence2)
  28.     // slicesAreEqual is a helper function
  29. 	return slicesAreEqual(sequence1, sequence2)
  30. }

Your helper function might look something like this:

  1. func slicesAreEqual(a, b []int) bool {
  2. 	if len(a) != len(b) {
  3. 		return false
  4. 	}
  5. 	for i, v := range a {
  6. 		if v != b[i] {
  7. 			return false
  8. 		}
  9. 	}
  10. 	return true
  11. }

huangapple
  • 本文由 发表于 2023年7月23日 00:38:41
  • 转载请务必保留本文链接：https://go.coder-hub.com/76744868.html
  • binary-search-tree
  • channel
  • go
  • goroutine
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定