baggiiiie

go-channel-prime-sieve

go sieve-of-eratosthenes

tags: learning go programming concurrency

content

  • sieve of eratosthenes

    1. give an array [2, infinity)
    2. the first element is prime, add to prime_list
    3. filter out elements that are the multiple of the first element
    4. generate a new array
    5. repeat 2~3, until prime_list is desired length

  • with Go channels and concurrency

    1. component 1: a goroutine keeps writing into a channel ch1, simulate an array input
    2. main:
      1. reads ch1 (which is 2, prime)
      2. creates new goroutine (new component) and passes in ch1 (after 2 is read) and 2(prime)
    3. component 2:
      1. a goroutine takes from ch1, check if it’s a multiple of prime
      2. filters out multiples, and writes to ch2
    4. main (repeats 2.1, 2.2):
      1. reads ch2 (which is the next prime next_prime)
      2. creates new goroutine and passes in ch2 and the next_prime

  • basically, how each goroutine writes to the channels is like creating new arrays

  • from Visualizing Concurrency in Go · divan’s blog, we can see each goroutine’s life time lasts until main finishes

draw this with excalidraw tbc

Iteration 1:
Generate -2→ [ch] → main reads here, prints 2
 
After iteration 1:
Generate -3→ [ch] → Filter(2) → [ch1] → main reads here, prints 3
                           ^      ^---- ch1 is 3, (3%2!=0, 3 gets written to channel)
                           +----- previous prime is 2
After iteration 2:
Generate -4/5→ [ch] → Filter(2) → [ch1] → Filter(3) → [ch2] → main reads here, prints 5
                          ^--- 4 gets dropped    ^---- ch1 is 5, (5%2!=0, 5 gets written to channel)
                                                 +----- previous prime is 3
After iteration 3:
Generate → [ch] → Filter(2) → [ch1] → Filter(3) → [ch2] → Filter(5) → [ch3] → main reads here
  • NOTE: every newly generated number from Generate() has gone through ALL go routines ever created until it gets filtered out

up

down

reference

Graph View