我如何生成依赖于其前辈的例程？

Question

Say for example that I want to populate this matrix:

| 0 | 0 | 0 | 0 |
| 0 | 1 | 2 | 3 |
| 0 | 2 | 3 | 4 |
| 0 | 3 | 4 | 5 |

Specifically, I want to populate it so that each cell follows the rule,

In english, a cell's value is one greater than the maximum of its top, left, and topleft neighbors' values.

Because each cell only has three dependencies (its top, left, and topleft neighbors), I can populate the cell at m[1][1] (the 1), and once that's populated, I can populate the cells marked 2 as all of their dependencies are already populated.

| 0 | 0 | 0 | 0 |          | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |   ---\   | 0 | 1 | 2 | 0 |
| 0 | 0 | 0 | 0 |   ---/   | 0 | 2 | 0 | 0 |
| 0 | 0 | 0 | 0 |          | 0 | 0 | 0 | 0 |

How can I spin up 1 go routine, then 2, then 3, then 4..., to populate each diagonal of this matrix? Perhaps more specifically, how can I wait on the neighbors to finish before beginning the dependent cell?

[EDIT]: Thanks for the comment, @Zippoxer! To clarify, I'm asking what the syntax is in Go to run a go-routine that depends on another finishing first. Because multiple new go-routines can start when just one go-routine finishes, it's not as simple as just calling things without concurrency!

Answer 1

Hopefully this is a contrived example, because this is definitely not the fastest solution, but maybe it's what you want.

Each cell runs in its own goroutine and has its own channel, roughly representing its dependencies. A cell knows its dependencies have all resolved once it's read three values from its channel. When a cell completes, it passes some value to the channels of all of its dependents.

import "sync"

type empty struct{}

func contrivedMathThing(i, j int) ([][]int) {

    var wg sync.WaitGroup
    wg.Add(i * j)

    // Make two-dimensional slices for the channels that the goroutines will
    // wait on, and for the results of each cell. Two dimensional slices are
    // more annoying to make, but I think make the example a bit more clear.
    chans := make([][]chan empty, i)
    results := make([][]int, i)
    for a := 0; a < i; a++ {
        chans[a] = make([]chan empty, j)
        results[a] = make([]int, j)
        for b := 0; b < j; b++ {
            chans[a][b] = make(chan empty, 3)
        }
    }

    for a := 0; a < i; a++ {
        for b := 0; b < j; b++ {
            go func(a, b int, waitc <-chan empty) {
                defer wg.Done()

                // Wait for all dependencies to complete
                <-waitc
                <-waitc
                <-waitc

                // Compute the result
                // Too lazy to write...

                // Save the result to the results array
                results[a][b] = result

                // Signal all dependents that one of their dependencies has
                // resolved
                if a < i - 1 {
                    chans[a + 1][b] <- empty{} 
                }
                if b < j - 1 {
                    chans[a][b + 1] <- empty{}
                }
                if a < i - 1 && b < j - 1 {
                    chans[a + 1][b + 1] <- empty{}
                }

            }(a, b, chans[a][b])
        }
    }

    // All cells in the first row and first column need to start out with two
    // of their dependencies satisfied.
    for a := 1; a < i; a++ {
        chans[a][0] <- empty{}
        chans[a][0] <- empty{}
    }
    for b := 1; b < j; b++ {
        chans[0][b] <- empty{}
        chans[0][b] <- empty{}
    }

    // Unblock the cell at [0][0] so this show can get started
    close(chans[0][0])

    wg.Wait()

    return results
}