Ytdyklly

I am still fairly new to go, and would appreciate any tips on style, best practices, etc, but am especially interested to know if this non-recursive cartesian product implementation can be made significantly faster (eg, when the number of results in the result set is on the order of 1e9).

I've played around with adding more goroutines, but parallelism doesn't seem to help much, if at all. I may be missing a much better approach though.

https://play.golang.org/p/H-M6CbmeFoV

package main



import (

    "fmt"

)



// Given a mixed base, returns a function that:

//

// Increments a number, represented as a slice of digits, defined

// in that base.  For example, if our base is 2 3 2, we'll count

// like this:

//

// 0 0 0 ; 0 0 1; 0 1 0; 0 1 1; 0 2 0; 0 2 1;

// 1 0 0 ; 1 0 1; 1 1 0; 1 1 1; 1 2 0; 1 2 1;

func mixedBaseInc(bases int) func(*int) {



    return func(digits *int) {

        ret := *digits

        i := len(ret) - 1

        for {

            base := bases[i]

            ret[i] = (ret[i] + 1) % base

            noCarry := ret[i] != 0



            if noCarry || i == 0 {

                return

            }

            i--

        }

    }

}



func pick(indexes int, params interface{}) interface{} {

    ret := make(interface{}, len(params))

    for i, x := range indexes {

        ret[i] = params[i][x]

    }

    return ret

}



func XProd(params ...interface{}) chan interface{} {

    var paramLens, digits int

    numElms := 1

    c := make(chan interface{})



    for _, x := range params {

        paramLens = append(paramLens, len(x))

        numElms *= len(x)

        digits = append(digits, 0)

    }



    inc := mixedBaseInc(paramLens)



    go func() {

        defer close(c)

        for i := 0; i < numElms; i++ {

            c <- pick(digits, params)

            inc(&digits)

        }

    }()



    return c

}



func main() {

    for x := range XProd(interface{}{1, 2, 3}, interface{}{4, 5}) {

        fmt.Println(x)

    }

}

I think you should replace mixedBaseInc with a generator that returns the combinations of indexes. That would simplify XProd by taking out numElms and the construction of digits.

That gives you the option to parallelise XProd by instantiating more instances of the goroutine that outputs the product vectors (because the closure no longer binds digits). If that is the bottleneck then that improves throughput.

However it depends on the program where this is used; if most of the work is done by the consumer of the output vectors then the best speed-up is for the consumer to consume in a way that can be parallelised.

An alternative approach is to build the output vectors one element at a time — https://github.com/schwarmco/go-cartesian-product/blob/master/cartesian.go for example . That solution has pros and cons and it's a bit more complicated to increase its parallelism, but it might be much better on some inputs (perhaps if there are a large number of small input sets to the product).