计算模逆、

Question

我想计算模运算中素数的逆元素。为了加快速度，我启动了几个 goroutine，它们试图在一定范围内找到元素。当第一个找到元素时，它将它发送到主 goroutine，此时我想终止程序。所以我调用close了主 goroutine，但我不知道 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

有没有更惯用的方法来进行这种计算？您实际上不需要循环来计算它。如果你使用GCD 函数（标准库的一部分），你会得到返回的数字 x 和 y，这样：x*P+y*Base=1这意味着 x 是您想要的答案（因为 x*P = 1 modulo Base）：package mainimport (    "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 公民并确保您的代码运行并在其背后进行整理，您可能需要结合执行以下操作：当在别处找到计算结果时，向生成的 goroutines 发出停止计算的信号。确保同步进程在返回之前等待 goroutines 停止。如果它们正确响应#1 中的信号，这不是强制性的，但如果您不等待，则无法保证它们在父 goroutine 继续之前已终止。在执行此任务然后退出的示例程序中，绝对不需要执行任何操作。正如这条评论所指出的，您的程序的main方法在找到满意的答案后终止，此时程序将结束，所有 goroutine 将立即终止，并且操作系统将整理所有消耗的资源。等待 goroutines 停止是不必要的。但是，如果您将这段代码打包到一个库中，或者它成为长期运行的“反素数计算”服务的一部分，那么最好整理您生成的 goroutine 以避免不必要地浪费周期。此外，一般来说，您可能还有其他场景，其中 goroutines 存储状态、持有外部资源的句柄或持有内部对象的句柄，如果没有妥善整理，您就有泄漏的风险——最好适当地关闭这些。传达停止工作的要求有几种方法可以传达这一点。我不认为这是一个详尽的清单！（请在评论中或通过对帖子提出编辑建议来建议其他通用方法。）使用特殊渠道通过关闭为此目的保留的特殊“关闭”通道向子 goroutine 发出信号。这利用了通道公理：来自关闭通道的接收立即返回零值从关闭通道接收后，goroutine 应立即安排整理任何本地状态并从函数返回。您之前的问题有实现此功能的示例代码；该模式的一个版本是：func myGoRoutine(shutdownChan <-chan struct{}) {&nbsp; &nbsp; select {&nbsp; &nbsp; case <-shutdownChan:&nbsp; &nbsp; &nbsp; &nbsp; // tidy up behaviour goes here&nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; // You may choose to listen on other channels here to implement&nbsp; &nbsp; // the primary behaviour of the goroutine.&nbsp; &nbsp; }}func main() {&nbsp; &nbsp; shutdownChan := make(chan struct{})&nbsp; &nbsp; go myGoRoutine(shutdownChan)&nbsp; &nbsp; // some time later&nbsp; &nbsp; close(shutdownChan)}在这种情况下，关闭逻辑被浪费了，因为该main()方法将在调用后立即返回close。这将与 goroutine 的关闭竞争，但我们应该假设它不会正确执行其整理行为。第 2 点解决了解决此问题的方法。使用上下文该context包提供了创建可以取消的上下文的选项。取消时，上下文Done()方法公开的通道将关闭，这标志着从 goroutine 返回的时间。这种方法与之前的方法大致相同，除了更简洁的封装和上下文的可用性以传递给 goroutine 中的下游调用以在需要时取消嵌套调用。例子：func myGoRoutine(ctx context.Context) {&nbsp; &nbsp; select {&nbsp; &nbsp; case <-ctx.Done():&nbsp; &nbsp; &nbsp; &nbsp; // tidy up behaviour goes here&nbsp; &nbsp; &nbsp; &nbsp; return&nbsp; &nbsp; // Put real behaviour for the goroutine here.&nbsp; &nbsp; }}func main() {&nbsp; &nbsp; // Get a context (or use an existing one if you are provided with one&nbsp; &nbsp; // outside a `main` method:&nbsp; &nbsp; ctx := context.Background()&nbsp; &nbsp; // Create a derived context with a cancellation method&nbsp; &nbsp; ctx, cancel := context.WithCancel(ctx)&nbsp; &nbsp; go myGoRoutine(ctx)&nbsp; &nbsp; // Later, when ready to quit&nbsp; &nbsp; cancel()}这与另一种情况有相同的错误，因为该main方法不会等待子 goroutines 在返回之前退出。等待（或“加入”）子协程停止上面示例中关闭关闭通道或关闭上下文的代码不会等待子 goroutine 停止工作再继续。这在某些情况下可能是可以接受的，而在其他情况下，您可能需要保证 goroutines 在继续之前已经停止。sync.WaitGroup可以用来实现这个要求。文档很全面。等待组是一个计数器，它应该Add在启动 goroutine 时使用它的方法递增，并Done在 goroutine 完成时使用它的方法递减。代码可以通过调用其方法等待计数器归零Wait，该方法会阻塞直到条件为真。对 的所有调用都Add必须在对 的调用之前发生Wait。示例代码：func main() {&nbsp; &nbsp; var wg sync.WaitGroup&nbsp; &nbsp; // Increment the WaitGroup with the number of goroutines we're&nbsp; &nbsp; // spawning.&nbsp; &nbsp; wg.Add(1)&nbsp; &nbsp; // It is common to wrap a goroutine in a function which performs&nbsp; &nbsp; // the decrement on the WaitGroup once the called function returns&nbsp; &nbsp; // to avoid passing references of this control logic to the&nbsp; &nbsp; // downstream consumer.&nbsp; &nbsp; go func() {&nbsp; &nbsp; &nbsp; &nbsp; // TODO: implement a method to communicate shutdown.&nbsp; &nbsp; &nbsp; &nbsp; callMyFunction()&nbsp; &nbsp; &nbsp; &nbsp; wg.Done()&nbsp; &nbsp; }()&nbsp; &nbsp; // Indicate shutdown, e.g. by closing a channel or cancelling a&nbsp; &nbsp; // context.&nbsp; &nbsp; // Wait for goroutines to stop&nbsp; &nbsp; wg.Wait()}有没有更惯用的方法来进行这种计算？通过以您定义的方式使用 goroutines，该算法当然可以并行化。由于工作受 CPU 限制，goroutines 对可用 CPU 数量的限制是有意义的（在机器上没有其他工作的情况下）以从可用计算资源中获益。