观察者模式或发布/订阅模式适用于细胞自动机。

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

Observer pattern or a Publish/Subscribe pattern for a cellular automaton

问题

我正在尝试为一种细胞自动机编写观察者模式或发布/订阅模式。

经典的观察者模式行不通，因为如果细胞A订阅细胞B的变化，反之亦然，应用程序将因为递归调用（B.update()将调用A.update()等等），导致堆栈溢出。

因此，我考虑使用发布/订阅模式，其中各个细胞通过传递消息而不是调用彼此的update()方法来通信。

这里有一个简单的示例，其中包含两个细胞A和B：

  1. package main
  3. import (
  4.     "fmt"
  5.     ps "publish/pubsub"
  6. )
  8. func main() {
  10.     fmt.Printf("Starting\n")
  12.     chEnd := make(chan int)
  14.     // 初始化
  15.     a := ps.NewNode(1, 0)
  16.     b := ps.NewNode(2, 0)
  18.     // 连接节点
  19.     a.Connect(b.ChOut)
  20.     b.Connect(a.ChOut)
  22.     // 开始监听
  23.     a.Listen()
  24.     b.Listen()
  26.     // 在一个任意节点上开始发送数据
  27.     // 以启动进程。
  28.     a.ChIn <- 10
  30.     <-chEnd
  31. }

对应的库如下：

  1. package pubsub
  3. import (
  4.     "fmt"
  5. )
  7. type Node struct {
  8.     Id    int
  9.     State int
  10.     ChOut chan int
  11.     ChIn  chan int
  12. }
  14. func NewNode(id int, state int) Node {
  15.     chout := make(chan int)
  16.     var chin chan int
  17.     return Node{id, state, chout, chin}
  18. }
  20. func (p *Node) Broadcast(inItem int) {
  21.     p.ChOut <- inItem + 1
  22.     //time.Sleep(100 * time.Millisecond)
  23. }
  25. func (p *Node) Listen() {
  26.     go func() {
  27.         for {
  28.             select {
  29.             case inItem := <-p.ChIn:
  30.                 fmt.Printf("%d: %d\n", p.Id, inItem)
  31.                 p.Broadcast(inItem)
  32.             }
  33.         }
  34.     }()
  35. }
  37. func (p *Node) Connect(ch chan int) {
  38.     p.ChIn = ch
  39. }

每个节点都有一个输入和一个输出通道。
B的输入通道是A的输出通道，反之亦然。

每次更新仅仅是将另一个细胞传递的数据加一。

看起来是有效的。到目前为止，一切都好。

我尝试使用一组4个细胞A、B、C、D来做类似的事情，以模拟一维细胞自动机。

在这第二次尝试中，
每个细胞都有两个输入通道（左和右）来监听其最近的左右邻居（ChinL和ChinR），
每个细胞都有两个输出通道，用于将其最新更新的状态传递给最近的邻居（ChoutL和ChoutR）。
在这个使用4个细胞的方案的实现中，我一定做错了什么，因为它产生了奇怪的结果：4个细胞之间来回传递的值似乎达到了一个阈值，而不是在每个连续的步骤中递增：以下是代码：

  1. package main
  3. import (
  4.     "fmt"
  5.     ps "publish/pubsub"
  6. )
  8. func main() {
  10.     fmt.Printf("Starting\n")
  12.     chEnd := make(chan int)
  14.     // 初始化
  15.     a := ps.NewNode(1, 0)
  16.     b := ps.NewNode(2, 0)
  17.     c := ps.NewNode(3, 0)
  18.     d := ps.NewNode(4, 0)
  20.     // 连接节点
  21.     a.ChInL = d.ChOutR
  22.     a.ChInR = b.ChOutL
  24.     b.ChInL = a.ChOutR
  25.     b.ChInR = c.ChOutL
  27.     c.ChInL = b.ChOutR
  28.     c.ChInR = d.ChOutL
  30.     d.ChInL = c.ChOutR
  31.     d.ChInR = a.ChOutL
  33.     // 开始监听
  34.     go a.Listen()
  35.     go b.Listen()
  36.     go c.Listen()
  37.     go d.Listen()
  39.     go a.Broadcast()
  40.     go b.Broadcast()
  41.     go c.Broadcast()
  42.     go d.Broadcast()
  44.     // 在一个任意节点上开始发送数据
  45.     // 以启动进程。
  46.     a.ChInL <- 1
  48.     // 读取通道上的虚拟数据，使main()等待
  49.     <-chEnd
  50. }
  52. /*
  53.     A   B   C   D
  54.     LR  LR  LR  LR
  55. */

对应的库如下：

  2. package pubsub
  4. import (
  5.     "fmt"
  6.     "strings"
  7. )
  9. type Node struct {
  10.     Id     int
  11.     State  int
  12.     ChOutL chan int
  13.     ChOutR chan int
  14.     ChInL  chan int
  15.     ChInR  chan int
  16.     ChIO   chan int
  17. }
  19. func NewNode(id int, state int) Node {
  20.     choutL := make(chan int)
  21.     choutR := make(chan int)
  22.     var chinL chan int
  23.     var chinR chan int
  24.     chIO := make(chan int)
  25.     return Node{id, state, choutL, choutR, chinL, chinR, chIO}
  26. }
  28. func (p *Node) Broadcast() {
  29.     for item := range p.ChIO {
  30.         p.ChOutL <- item + 1
  31.         p.ChOutR <- item + 1
  32.         fmt.Printf("%d: %d %s\n", p.Id, item, strings.Repeat("*", item))
  33.     }
  34. }
  36. func (p *Node) Listen() {
  37.     for {
  38.         //time.Sleep(100 * time.Millisecond)
  39.         select {
  40.         case inItem := <-p.ChInL:
  41.             go func() {
  42.                 p.ChIO <- inItem
  43.             }()
  44.         case inItem := <-p.ChInR:
  45.             go func() {
  46.                 p.ChIO <- inItem
  47.             }()
  48.         }
  49.     }
  50. }

为了完整起见，这是上述模块的go.mod文件：

  1. module publish
  3. go 1.17
英文:

I am trying to code an observer pattern or a publish/submit pattern for a sort of cellular automaton.

The classical observer pattern does not to the trick because if a cell A subscribes to changes in a cell B and vice-versa, the application will run out of stack owing to the recursive approach (B.update() will call A.update() and so on and the app will run out of stack).

So I thought about using a publish/subscribe pattern where respective cells pass each other messages, rather than calling each other's update() methods.

Here is a simple example with two cells A and B:

  1. package main
  3. import (
  4.     &quot;fmt&quot;
  5.     ps &quot;publish/pubsub&quot;
  6. )
  8. func main() {
  10.     fmt.Printf(&quot;Starting\n&quot;)
  12.     chEnd := make(chan int)
  14.     // initialize
  15.     a := ps.NewNode(1, 0)
  16.     b := ps.NewNode(2, 0)
  18.     // connect nodes
  19.     a.Connect(b.ChOut)
  20.     b.Connect(a.ChOut)
  22.     // Start listening
  23.     a.Listen()
  24.     b.Listen()
  26.     // Start sending data on one arbitrary node
  27.     // to start the process.
  28.     a.ChIn &lt;- 10
  30.     &lt;-chEnd
  31. }

and the corresponding lib

  1. package pubsub
  3. import (
  4.     &quot;fmt&quot;
  5. )
  7. type Node struct {
  8.     Id    int
  9.     State int
  10.     ChOut chan int
  11.     ChIn  chan int
  12. }
  14. func NewNode(id int, state int) Node {
  15.     chout := make(chan int)
  16.     var chin chan int
  17.     return Node{id, state, chout, chin}
  18. }
  20. func (p *Node) Broadcast(inItem int) {
  21.     p.ChOut &lt;- inItem + 1
  22.     //time.Sleep(100 * time.Millisecond)
  23. }
  25. func (p *Node) Listen() {
  26.     go func() {
  27.         for {
  28.             select {
  29.             case inItem := &lt;-p.ChIn:
  30.                 fmt.Printf(&quot;%d: %d\n&quot;, p.Id, inItem)
  31.                 p.Broadcast(inItem)
  32.             }
  33.         }
  34.     }()
  35. }
  37. func (p *Node) Connect(ch chan int) {
  38.     p.ChIn = ch
  39. }

Each node has a input and an output channe.
The input channel of B is the output channel of A and vice-versa.

Every update consists merely of incrementing the data passed by the other cell.

It seems to work. So far, so good.

I tried to do something similar with a set of 4 cells A, B, C, D, in order to simulate a one dimensional cellular automaton of sorts.

In this second attempt,
each cell has two input channels (let and right) to listen to its closest left- and right-hand neighbour, respectively (ChinL and ChinR).
each cell has to output channels to communicate its latest updated state to its closest neighbours (ChoutL and ChoutR).
I must have done something wrong in the implementation of that scheme with 4 cells, because it yields odd results : the values passed back and forth between the 4 cells seem to hit a threshold instead of increasing at every consecutive step: here is the code:

  1. package main
  3. import (
  4.     &quot;fmt&quot;
  5.     ps &quot;publish/pubsub&quot;
  6. )
  8. func main() {
  10.     fmt.Printf(&quot;Starting\n&quot;)
  12.     chEnd := make(chan int)
  14.     // initialize
  15.     a := ps.NewNode(1, 0)
  16.     b := ps.NewNode(2, 0)
  17.     c := ps.NewNode(3, 0)
  18.     d := ps.NewNode(4, 0)
  20.     // connect nodes
  21.     a.ChInL = d.ChOutR
  22.     a.ChInR = b.ChOutL
  24.     b.ChInL = a.ChOutR
  25.     b.ChInR = c.ChOutL
  27.     c.ChInL = b.ChOutR
  28.     c.ChInR = d.ChOutL
  30.     d.ChInL = c.ChOutR
  31.     d.ChInR = a.ChOutL
  33.     // Start listening
  34.     go a.Listen()
  35.     go b.Listen()
  36.     go c.Listen()
  37.     go d.Listen()
  39.     go a.Broadcast()
  40.     go b.Broadcast()
  41.     go c.Broadcast()
  42.     go d.Broadcast()
  44.     // Start sending data on one arbitrary node
  45.     // to start the process.
  46.     a.ChInL &lt;- 1
  48.     // Dummy read on channel to make main() wait
  49.     &lt;-chEnd
  50. }
  52. /*
  53.     A   B   C   D
  54.     LR  LR  LR  LR
  55. */

and the corresponding lib

  2. package pubsub
  4. import (
  5.     &quot;fmt&quot;
  6.     &quot;strings&quot;
  7. )
  9. type Node struct {
  10.     Id     int
  11.     State  int
  12.     ChOutL chan int
  13.     ChOutR chan int
  14.     ChInL  chan int
  15.     ChInR  chan int
  16.     ChIO   chan int
  17. }
  19. func NewNode(id int, state int) Node {
  20.     choutL := make(chan int)
  21.     choutR := make(chan int)
  22.     var chinL chan int
  23.     var chinR chan int
  24.     chIO := make(chan int)
  25.     return Node{id, state, choutL, choutR, chinL, chinR, chIO}
  26. }
  28. func (p *Node) Broadcast() {
  29.     for item := range p.ChIO {
  30.         p.ChOutL &lt;- item + 1
  31.         p.ChOutR &lt;- item + 1
  32.         fmt.Printf(&quot;%d: %d %s\n&quot;, p.Id, item, strings.Repeat(&quot;*&quot;, item))
  33.     }
  34. }
  36. func (p *Node) Listen() {
  37.     for {
  38.         //time.Sleep(100 * time.Millisecond)
  39.         select {
  40.         case inItem := &lt;-p.ChInL:
  41.             go func() {
  42.                 p.ChIO &lt;- inItem
  43.             }()
  44.         case inItem := &lt;-p.ChInR:
  45.             go func() {
  46.                 p.ChIO &lt;- inItem
  47.             }()
  48.         }
  49.     }
  50. }

For completeness, here is the go.mod for the modules above:

  1. module publish
  3. go 1.17

答案1

得分: 4

对于节点在 p.ChInL 或 p.ChInR 上接收到的每个信号，你发送两个信号。第一个信号发送到 p.ChOutL，第二个信号发送到 p.ChOutR。由于每个节点都这样做，信号的数量将呈指数增长。

在本地运行时，阈值在20到25之间。因此大约有2^25（33554432）个信号在传递。要看到26，程序将需要处理67108864个信号。因此，它将超过这个阈值，但速度会指数级变慢。

现在来修复一下。我认为你应该实现一种 tick 系统。所以，不是在每次自动机发生变化时发送更新信号，而是每个 tick 发送一次更新信号，比如每秒20次。

或者更好的是，不使用例程和通道，只需创建一个节点的切片并循环遍历它们（同样只在同一个 tick/循环中更新邻居而不传播）。循环的每次迭代都会改变所有节点的状态。我相信这也是其他自动机（如生命游戏）的工作原理。现在，你可以以计算机的最快速度运行模拟。

英文:

For every signal a node receives on p.ChInL or p.ChInR you send out 2 signals. The first to p.ChOutL and the second to p.ChOutR. Since every node does this there will be an exponential amount of signals going around.

When running it locally the threshold is between 20 and 25. So about 2^25 33554432 signals going around. To see 26, the program will need to process 67108864 signals. So it will go past this threshold, just exponentially slower.

Now for the fix. I think you should implement some sort of tick system. So instead of sending update signals for every change to the automaton you send one update every tick like 20 times per second.

Maybe better yet, instead of using routines and channels, just make an slice of nodes and loop over them (again only updating the neighbor and not propagating it in the same tick/loop). Each iteration of the loop the state of all nodes has changed. I believe this is also how other automatons like game-of-live work. Now you can run the simulation as fast as your computer can run.

答案2

得分: 0

这是一个可能的替代方案：

  1. package pubsub
  3. import (
  4. 	"fmt"
  5. 	"math/rand"
  6. 	"strings"
  7. 	"time"
  8. )
  10. type Node struct {
  11. 	Id     int
  12. 	State  int
  13. 	ChOutL chan int
  14. 	ChOutR chan int
  15. 	ChInL  chan int
  16. 	ChInR  chan int
  17. 	ChIO   chan int
  18. }
  20. func NewNode(id int, state int) Node {
  21. 	choutL := make(chan int)
  22. 	choutR := make(chan int)
  23. 	var chinL chan int
  24. 	var chinR chan int
  25. 	chIO := make(chan int)
  26. 	return Node{id, state, choutL, choutR, chinL, chinR, chIO}
  27. }
  29. func (p *Node) Broadcast() {
  30. 	for item := range p.ChIO {
  31. 		rnd := rand.Intn(2)
  32. 		if rnd == 0 {
  33. 			p.ChOutL <- item + 1
  34. 		} else {
  35. 			p.ChOutR <- item + 1
  36. 		}
  37. 		fmt.Printf("%d: %d %s\n", p.Id, item, strings.Repeat("*", item))
  38. 	}
  39. }
  41. func (p *Node) Listen() {
  42. 	for {
  43. 		time.Sleep(100 * time.Millisecond)
  44. 		select {
  45. 		case inItem := <-p.ChInL:
  46. 			p.ChIO <- inItem
  47. 		case inItem := <-p.ChInR:
  48. 			p.ChIO <- inItem
  49. 		}
  50. 	}
  51. }

希望对你有帮助！

英文:

Here is one possible alternative:

  1. package pubsub
  2. import (
  3. &quot;fmt&quot;
  4. &quot;math/rand&quot;
  5. &quot;strings&quot;
  6. &quot;time&quot;
  7. )
  8. type Node struct {
  9. Id     int
  10. State  int
  11. ChOutL chan int
  12. ChOutR chan int
  13. ChInL  chan int
  14. ChInR  chan int
  15. ChIO   chan int
  16. }
  17. func NewNode(id int, state int) Node {
  18. choutL := make(chan int)
  19. choutR := make(chan int)
  20. var chinL chan int
  21. var chinR chan int
  22. chIO := make(chan int)
  23. return Node{id, state, choutL, choutR, chinL, chinR, chIO}
  24. }
  25. func (p *Node) Broadcast() {
  26. for item := range p.ChIO {
  27. rnd := rand.Intn(2)
  28. if rnd == 0 {
  29. p.ChOutL &lt;- item + 1
  30. } else {
  31. p.ChOutR &lt;- item + 1
  32. }
  33. fmt.Printf(&quot;%d: %d %s\n&quot;, p.Id, item, strings.Repeat(&quot;*&quot;, item))
  34. }
  35. }
  36. func (p *Node) Listen() {
  37. for {
  38. time.Sleep(100 * time.Millisecond)
  39. select {
  40. case inItem := &lt;-p.ChInL:
  41. p.ChIO &lt;- inItem
  42. case inItem := &lt;-p.ChInR:
  43. p.ChIO &lt;- inItem
  44. }
  45. }
  46. }

答案3

得分: 0

这是第二个替代方案：

  1. package main
  3. import (
  4. 	"fmt"
  5. 	ps "pub/pubsub"
  6. )
  8. func main() {
  10. 	fmt.Printf("Hello\n")
  12. 	chEnd := make(chan int)
  14. 	A := ps.NewNode(1, 0)
  15. 	B := ps.NewNode(2, 0)
  16. 	C := ps.NewNode(3, 0)
  17. 	D := ps.NewNode(4, 0)
  19. 	B.LeftNode = &A
  20. 	B.RightNode = &C
  21. 	C.LeftNode = &B
  22. 	C.RightNode = &D
  23. 	D.LeftNode = &C
  24. 	D.RightNode = &A
  25. 	A.LeftNode = &D
  26. 	A.RightNode = &B
  28. 	A.Listen()
  29. 	B.Listen()
  30. 	C.Listen()
  31. 	D.Listen()
  33. 	A.State = 1
  34. 	<-chEnd
  36. }
  38. //----
  40. package pubsub
  42. import (
  43. 	"fmt"
  44. 	"strings"
  45. 	"sync"
  46. 	"time"
  47. )
  49. type Node struct {
  50. 	Id         int
  51. 	State      int
  52. 	LeftNode   *Node
  53. 	RightNode  *Node
  54. 	LeftState  int
  55. 	RightState int
  56. }
  58. var m sync.Mutex
  60. func NewNode(id int, state int) Node {
  61. 	return Node{id, state, nil, nil, 0, 0}
  62. }
  64. func (n *Node) Listen() {
  65. 	go func() {
  66. 		for {
  67. 			m.Lock()
  68. 			time.Sleep(10 * time.Millisecond)
  69. 			if n.LeftState != n.LeftNode.State {
  70. 				n.LeftState = n.LeftNode.State
  71. 				n.State = n.LeftNode.State + 1
  72. 				fmt.Printf("%d: %d %s\n", n.Id, n.State, strings.Repeat("*", n.State))
  73. 			}
  74. 			m.Unlock()
  75. 		}
  76. 	}()
  77. 	go func() {
  78. 		for {
  79. 			m.Lock()
  80. 			time.Sleep(10 * time.Millisecond)
  81. 			if n.RightState != n.RightNode.State {
  82. 				n.RightState = n.RightNode.State
  83. 				n.State = n.RightNode.State + 1
  84. 				fmt.Printf("%d: %d %s\n", n.Id, n.State, strings.Repeat("*", n.State))
  85. 			}
  86. 			m.Unlock()
  87. 		}
  88. 	}()
  89. }
英文:

Here is a second alternative:

  1. package main
  2. import (
  3. &quot;fmt&quot;
  4. ps &quot;pub/pubsub&quot;
  5. )
  6. func main() {
  7. fmt.Printf(&quot;Hello\n&quot;)
  8. chEnd := make(chan int)
  9. A := ps.NewNode(1, 0)
  10. B := ps.NewNode(2, 0)
  11. C := ps.NewNode(3, 0)
  12. D := ps.NewNode(4, 0)
  13. B.LeftNode = &amp;A
  14. B.RightNode = &amp;C
  15. C.LeftNode = &amp;B
  16. C.RightNode = &amp;D
  17. D.LeftNode = &amp;C
  18. D.RightNode = &amp;A
  19. A.LeftNode = &amp;D
  20. A.RightNode = &amp;B
  21. A.Listen()
  22. B.Listen()
  23. C.Listen()
  24. D.Listen()
  25. A.State = 1
  26. &lt;-chEnd
  27. }
  28. //----
  29. package pubsub
  30. import (
  31. &quot;fmt&quot;
  32. &quot;strings&quot;
  33. &quot;sync&quot;
  34. &quot;time&quot;
  35. )
  36. type Node struct {
  37. Id         int
  38. State      int
  39. LeftNode   *Node
  40. RightNode  *Node
  41. LeftState  int
  42. RightState int
  43. }
  44. var m sync.Mutex
  45. func NewNode(id int, state int) Node {
  46. return Node{id, state, nil, nil, 0, 0}
  47. }
  48. func (n *Node) Listen() {
  49. go func() {
  50. for {
  51. m.Lock()
  52. time.Sleep(10 * time.Millisecond)
  53. if n.LeftState != n.LeftNode.State {
  54. n.LeftState = n.LeftNode.State
  55. n.State = n.LeftNode.State + 1
  56. fmt.Printf(&quot;%d: %d %s\n&quot;, n.Id, n.State, strings.Repeat(&quot;*&quot;, n.State))
  57. }
  58. m.Unlock()
  59. }
  60. }()
  61. go func() {
  62. for {
  63. m.Lock()
  64. time.Sleep(10 * time.Millisecond)
  65. if n.RightState != n.RightNode.State {
  66. n.RightState = n.RightNode.State
  67. n.State = n.RightNode.State + 1
  68. fmt.Printf(&quot;%d: %d %s\n&quot;, n.Id, n.State, strings.Repeat(&quot;*&quot;, n.State))
  69. }
  70. m.Unlock()
  71. }
  72. }()
  73. }

huangapple
  • 本文由 发表于 2021年11月14日 22:34:27
  • 转载请务必保留本文链接：https://go.coder-hub.com/69964054.html
  • channel
  • go
  • observer-pattern
  • publish-subscribe
匿名

发表评论

匿名网友

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

确定