计算模逆、

Question

我想计算模运算中素数的逆元素。为了加快速度，我启动了几个 goroutine，它们试图在一定范围内找到元素。当第一个找到元素时，它将它发送到主 goroutine，此时我想终止程序。所以我调用close了主 goroutine，但我不知道 goroutines 是否会完成它们的执行（我猜不会）。于是出现了几个问题：1）这是一种糟糕的风格，我应该有类似的东西吗WaitGroup？2）是否有更惯用的方法来进行此计算？package mainimport "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

有没有更惯用的方法来进行这种计算？

您实际上不需要循环来计算它。

如果你使用GCD 函数（标准库的一部分），你会得到返回的数字 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)

}

Answer 2

这是一种糟糕的风格，我应该有类似的东西吗WaitGroup？

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

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

1. 当在别处找到计算结果时，向生成的 goroutines 发出停止计算的信号。

2. 确保同步进程在返回之前等待 goroutines 停止。如果它们正确响应#1 中的信号，这不是强制性的，但如果您不等待，则无法保证它们在父 goroutine 继续之前已终止。

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

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

---

传达停止工作的要求

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

使用特殊渠道

通过关闭为此目的保留的特殊“关闭”通道向子 goroutine 发出信号。这利用了通道公理：

来自关闭通道的接收立即返回零值

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

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。这将与 goroutine 的关闭竞争，但我们应该假设它不会正确执行其整理行为。第 2 点解决了解决此问题的方法。

使用上下文

该context包提供了创建可以取消的上下文的选项。取消时，上下文Done()方法公开的通道将关闭，这标志着从 goroutine 返回的时间。

这种方法与之前的方法大致相同，除了更简洁的封装和上下文的可用性以传递给 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 在返回之前退出。

等待（或“加入”）子协程停止

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

sync.WaitGroup可以用来实现这个要求。文档很全面。等待组是一个计数器，它应该Add在启动 goroutine 时使用它的方法递增，并Done在 goroutine 完成时使用它的方法递减。代码可以通过调用其方法等待计数器归零Wait，该方法会阻塞直到条件为真。对 的所有调用都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()

}

有没有更惯用的方法来进行这种计算？

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