计算 mod 逆

Question

我想计算模运算中素数的逆元素。为了加快速度，我启动了几个 goroutine，它们试图在一定范围内找到元素。当第一个找到元素时，它将它发送到主 goroutine，此时我想终止程序。所以我在主 goroutine 中调用 close，但我不知道 goroutines 是否会完成它们的执行（我猜不会）。于是出现了几个问题：

1) 这种风格不好吗，我应该有类似 WaitGroup 的东西吗？

2) 是否有更惯用的方法来进行此计算？

package main

import "fmt"

const (
    Procs = 8
    P     = 1000099
    Base  = 1<<31 - 1
)

func compute(start, end uint64, finished chan struct{}, output chan uint64) {
    for i := start; i < end; i++ {
        select {
        case <-finished:
            return
        default:
            break
        }
        if i*P%Base == 1 {
            output <- i
        }
    }
}

func main() {
    finished := make(chan struct{})
    output := make(chan uint64)

    for i := uint64(0); i < Procs; i++ {
        start := i * (Base / Procs)
        end := (i + 1) * (Base / Procs)
        go compute(start, end, finished, output)
    }

    fmt.Println(<-output)
    close(finished)
}

Answer 1

Is this a bad style, should I have something like a WaitGroup?

等待组解决了不同的问题。

一般来说，要在这里成为负责任的 go 公民并确保您的代码运行 并自行整理 ，您可能需要组合执行以下操作：

当在别处找到计算结果时，向派生的 goroutines 发出停止计算的信号。
确保同步进程在 returning 之前等待 goroutines 停止。如果他们正确响应#1 中的信号，这不是强制性的，但如果你不等待，将无法保证他们在父 goroutine 继续之前已经终止。

在您执行此任务然后退出的示例程序中，绝对没有必要执行任何一项操作。正如所示，您的程序的 main 方法在找到令人满意的答案后终止，此时程序将结束，所有 goroutine 将立即终止，操作系统将整理所有消耗的资源。等待 goroutines 停止是不必要的。

但是，如果您将此代码打包到一个库中或者它成为一个长运行 "inverse prime calculation" 服务的一部分，那么最好整理您生成的 goroutine 以避免浪费周期不必要地。此外，一般来说，您可能还有其他场景，其中 goroutines 存储状态，持有外部资源的句柄，或持有内部对象的句柄，如果没有妥善整理，您就有泄漏的风险 - 最好适当关闭这些。

传达停止工作的要求

有几种方法可以传达这一点。我不认为这是一个详尽的清单！ _{（请在评论中建议其他通用方法或通过对 post 提出编辑建议。）}

使用特殊渠道

通过关闭为此目的保留的特殊 "shutdown" 通道向子 goroutines 发出信号。这利用了通道 axiom:

A receive from a closed channel returns the zero value immediately

从关闭通道接收后，goroutine 应立即安排整理任何本地状态和 return 函数。您之前的问题有实现此功能的示例代码；该模式的一个版本是：

func myGoRoutine(shutdownChan <-chan struct{}) {
    select {
    case <-shutdownChan:
        // tidy up behaviour goes here
        return
    // You may choose to listen on other channels here to implement
    // the primary behaviour of the goroutine.
    }
}

func main() {
    shutdownChan := make(chan struct{})
    go myGoRoutine(shutdownChan)

    // some time later
    close(shutdownChan)
}

在这种情况下，关闭逻辑被浪费了，因为 main() 方法将在调用 close 后立即 return。这将与 goroutine 的关闭竞争，但我们应该假设它不会正确执行其整理行为。第 2 点解决了解决此问题的方法。

使用上下文

context 包提供了创建可以取消的上下文的选项。取消时，上下文的 Done() 方法公开的通道将关闭，这表明 goroutine 到 return 的时间。

此方法与之前的方法大致相同，除了更简洁的封装和上下文的可用性以传递给 goroutine 中的下游调用以在需要时取消嵌套调用。示例：

func myGoRoutine(ctx context.Context) {
    select {
    case <-ctx.Done():
        // tidy up behaviour goes here
        return
    // Put real behaviour for the goroutine here.
    }
}

func main() {
    // Get a context (or use an existing one if you are provided with one
    // outside a `main` method:
    ctx := context.Background()

    // Create a derived context with a cancellation method
    ctx, cancel := context.WithCancel(ctx)

    go myGoRoutine(ctx)

    // Later, when ready to quit
    cancel()
}

这与另一种情况有相同的错误，因为 main 方法不会等待子 goroutines 在 returning 之前退出。

正在等待（或 "join"ing）子 goroutines 停止

上述示例中关闭关闭通道或关闭上下文的代码不会等待子 goroutine 停止工作再继续。这在某些情况下可能是可以接受的，而在其他情况下，您可能需要保证 goroutines 在继续之前已经停止。

sync.WaitGroup可以用来实现这个需求。 documentation 是全面的。等待组是一个计数器，它应该在启动 goroutine 时使用其 Add 方法递增，并在 goroutine 完成时使用其 Done 方法递减。代码可以通过调用其 Wait 方法等待计数器 return 归零，该方法会阻塞直到条件为真。所有对 Add 的调用都必须在对 Wait.

的调用之前发生

示例代码：

func main() {
    var wg sync.WaitGroup

    // Increment the WaitGroup with the number of goroutines we're
    // spawning.
    wg.Add(1)

    // It is common to wrap a goroutine in a function which performs
    // the decrement on the WaitGroup once the called function returns
    // to avoid passing references of this control logic to the
    // downstream consumer.
    go func() {
        // TODO: implement a method to communicate shutdown.
        callMyFunction()
        wg.Done()
    }()

    // Indicate shutdown, e.g. by closing a channel or cancelling a
    // context.

    // Wait for goroutines to stop
    wg.Wait()
}

Is there a more idiomatic way to do this computation?

通过以您定义的方式使用 goroutine，此算法当然可以并行化。由于工作是 CPU-bound，goroutines 对可用 CPUs 数量的限制是有意义的（在机器上没有其他工作的情况下）从可用计算资源中受益。

有关错误修复，请参阅 peterSO's answer。

Answer 2

Is there a more idiomatic way to do this computation?

你实际上不需要循环来计算这个。

如果您使用 GCD function（标准库的一部分），您会得到返回的数字 x 和 y，这样：

x*P+y*Base=1

这意味着 x 是您想要的答案（因为 x*P = 1 modulo Base）：

package main

import (
    "fmt"
    "math/big"
)

const (
    P    = 1000099
    Base = 1<<31 - 1
)

func main() {
    bigP := big.NewInt(P)
    bigBase := big.NewInt(Base)
    // Compute inverse of bigP modulo bigBase
    bigGcd := big.NewInt(0)
    bigX := big.NewInt(0)
    bigGcd.GCD(bigX,nil,bigP,bigBase)
    // x*bigP+y*bigBase=1 
    // => x*bigP = 1 modulo bigBase
    fmt.Println(bigX)
}

计算 mod 逆

Computing mod inverse

algorithm

go

goroutine

传达停止工作的要求

使用特殊渠道

使用上下文

正在等待（或 "join"ing）子 goroutines 停止