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:
package main
import (
"fmt"
ps "publish/pubsub"
)
func main() {
fmt.Printf("Starting\n")
chEnd := make(chan int)
// initialize
a := ps.NewNode(1, 0)
b := ps.NewNode(2, 0)
// connect nodes
a.Connect(b.ChOut)
b.Connect(a.ChOut)
// Start listening
a.Listen()
b.Listen()
// Start sending data on one arbitrary node
// to start the process.
a.ChIn <- 10
<-chEnd
}
and the corresponding lib
package pubsub
import (
"fmt"
)
type Node struct {
Id int
State int
ChOut chan int
ChIn chan int
}
func NewNode(id int, state int) Node {
chout := make(chan int)
var chin chan int
return Node{id, state, chout, chin}
}
func (p *Node) Broadcast(inItem int) {
p.ChOut <- inItem 1
//time.Sleep(100 * time.Millisecond)
}
func (p *Node) Listen() {
go func() {
for {
select {
case inItem := <-p.ChIn:
fmt.Printf("%d: %d\n", p.Id, inItem)
p.Broadcast(inItem)
}
}
}()
}
func (p *Node) Connect(ch chan int) {
p.ChIn = ch
}
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:
package main
import (
"fmt"
ps "publish/pubsub"
)
func main() {
fmt.Printf("Starting\n")
chEnd := make(chan int)
// initialize
a := ps.NewNode(1, 0)
b := ps.NewNode(2, 0)
c := ps.NewNode(3, 0)
d := ps.NewNode(4, 0)
// connect nodes
a.ChInL = d.ChOutR
a.ChInR = b.ChOutL
b.ChInL = a.ChOutR
b.ChInR = c.ChOutL
c.ChInL = b.ChOutR
c.ChInR = d.ChOutL
d.ChInL = c.ChOutR
d.ChInR = a.ChOutL
// Start listening
go a.Listen()
go b.Listen()
go c.Listen()
go d.Listen()
go a.Broadcast()
go b.Broadcast()
go c.Broadcast()
go d.Broadcast()
// Start sending data on one arbitrary node
// to start the process.
a.ChInL <- 1
// Dummy read on channel to make main() wait
<-chEnd
}
/*
A B C D
LR LR LR LR
*/
and the corresponding lib
package pubsub
import (
"fmt"
"strings"
)
type Node struct {
Id int
State int
ChOutL chan int
ChOutR chan int
ChInL chan int
ChInR chan int
ChIO chan int
}
func NewNode(id int, state int) Node {
choutL := make(chan int)
choutR := make(chan int)
var chinL chan int
var chinR chan int
chIO := make(chan int)
return Node{id, state, choutL, choutR, chinL, chinR, chIO}
}
func (p *Node) Broadcast() {
for item := range p.ChIO {
p.ChOutL <- item 1
p.ChOutR <- item 1
fmt.Printf("%d: %d %s\n", p.Id, item, strings.Repeat("*", item))
}
}
func (p *Node) Listen() {
for {
//time.Sleep(100 * time.Millisecond)
select {
case inItem := <-p.ChInL:
go func() {
p.ChIO <- inItem
}()
case inItem := <-p.ChInR:
go func() {
p.ChIO <- inItem
}()
}
}
}
For completeness, here is the go.mod for the modules above:
module publish
go 1.17
CodePudding user response：
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.
CodePudding user response：
Here is one possible alternative:
package pubsub
import (
"fmt"
"math/rand"
"strings"
"time"
)
type Node struct {
Id int
State int
ChOutL chan int
ChOutR chan int
ChInL chan int
ChInR chan int
ChIO chan int
}
func NewNode(id int, state int) Node {
choutL := make(chan int)
choutR := make(chan int)
var chinL chan int
var chinR chan int
chIO := make(chan int)
return Node{id, state, choutL, choutR, chinL, chinR, chIO}
}
func (p *Node) Broadcast() {
for item := range p.ChIO {
rnd := rand.Intn(2)
if rnd == 0 {
p.ChOutL <- item 1
} else {
p.ChOutR <- item 1
}
fmt.Printf("%d: %d %s\n", p.Id, item, strings.Repeat("*", item))
}
}
func (p *Node) Listen() {
for {
time.Sleep(100 * time.Millisecond)
select {
case inItem := <-p.ChInL:
p.ChIO <- inItem
case inItem := <-p.ChInR:
p.ChIO <- inItem
}
}
}
CodePudding user response：
Here is a second alternative:
package main
import (
"fmt"
ps "pub/pubsub"
)
func main() {
fmt.Printf("Hello\n")
chEnd := make(chan int)
A := ps.NewNode(1, 0)
B := ps.NewNode(2, 0)
C := ps.NewNode(3, 0)
D := ps.NewNode(4, 0)
B.LeftNode = &A
B.RightNode = &C
C.LeftNode = &B
C.RightNode = &D
D.LeftNode = &C
D.RightNode = &A
A.LeftNode = &D
A.RightNode = &B
A.Listen()
B.Listen()
C.Listen()
D.Listen()
A.State = 1
<-chEnd
}
//----
package pubsub
import (
"fmt"
"strings"
"sync"
"time"
)
type Node struct {
Id int
State int
LeftNode *Node
RightNode *Node
LeftState int
RightState int
}
var m sync.Mutex
func NewNode(id int, state int) Node {
return Node{id, state, nil, nil, 0, 0}
}
func (n *Node) Listen() {
go func() {
for {
m.Lock()
time.Sleep(10 * time.Millisecond)
if n.LeftState != n.LeftNode.State {
n.LeftState = n.LeftNode.State
n.State = n.LeftNode.State 1
fmt.Printf("%d: %d %s\n", n.Id, n.State, strings.Repeat("*", n.State))
}
m.Unlock()
}
}()
go func() {
for {
m.Lock()
time.Sleep(10 * time.Millisecond)
if n.RightState != n.RightNode.State {
n.RightState = n.RightNode.State
n.State = n.RightNode.State 1
fmt.Printf("%d: %d %s\n", n.Id, n.State, strings.Repeat("*", n.State))
}
m.Unlock()
}
}()
}