哈喽！今天心血来潮给大家带来了《求逆模》，想必大家应该对Golang都不陌生吧，那么阅读本文就都不会很困难，以下内容主要涉及到，若是你正在学习Golang，千万别错过这篇文章~希望能帮助到你！

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

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)
}

解决方案

这是一种不好的风格吗？我应该有类似 waitgroup 的东西吗？

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

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

1. 当在其他地方找到计算结果时，向生成的 goroutine 发出信号以停止计算。
2. 确保同步进程在返回之前等待 goroutine 停止。如果它们正确响应 #1 中的信号，则这不是强制性的，但如果您不等待，则无法保证它们在父 goroutine 继续之前已终止。

在您的示例程序中，执行此任务然后退出，完全不需要执行任何操作。正如 this comment 所示，程序的 main 方法在找到满意的答案后终止，此时程序将结束，所有 goroutine 将立即终止，操作系统将清理所有消耗的资源。等待 goroutine 停止是不必要的。

但是，如果您将此代码打包到一个库中，或者它成为长时间运行的“逆素数计算”服务的一部分，则需要整理您生成的 goroutine 以避免不必要地浪费周期。此外，一般来说，您可能会遇到其他情况，其中 goroutine 存储状态、保存外部资源的句柄或保存内部对象的句柄，如果不正确清理，这些对象可能会泄漏 – 最好正确关闭这些内容。

传达停止工作的要求

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

使用特殊通道

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

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

从关闭通道接收到消息后，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 方法在返回之前不会等待子 goroutine 退出。

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

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

sync.waitgroup可以用来实现这个需求。 documentation很全面。等待组是一个计数器，应该在启动 goroutine 时使用其 add 方法递增，并在 goroutine 完成时使用其 done 方法递减。代码可以通过调用其 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()
}

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

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

请参阅 peterSO's answer 以获取错误修复。

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

如果您使用 GCD function（标准库的一部分），您将得到返回的数字 x 和 y，如下所示：

x*p+y*base=1

这意味着 x 是您想要的答案（因为 x*p = 1 模基数）：

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)
}

今天关于《求逆模》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！