代码之家 › 专栏 › 技术社区 › Mariy

计算模逆

goroutine go algorithm

Mariy · 技术社区 · 7 年前

为了加快速度,我开始了一些goroutine,试图在一定范围内找到元素。当第一个找到元素时,它将它发送到主goroutine,此时我想终止程序。所以我打电话来 close

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

2 回复 | 直到 7 年前

Cosmic Ossifrage 7 年前

这是一个坏的风格,我应该有一个类似的吗 WaitGroup

等待组解决不同的问题。

把后面收拾得干干净净 ,您可能需要执行以下组合操作:

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

在执行此任务然后退出的示例程序中,严格来说不需要执行这两种操作。作为 this comment 表示您的程序 main

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

传达停止工作的要求

有几种方法可以传达这一点。我不认为这是一个详尽的清单! _{(请务必在评论中建议其他通用方法,或建议对帖子进行编辑。)}

使用特殊频道

axiom :

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

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

使用上下文

这个 context Done()

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

这与另一个案例的bug相同,因为方法不会等到子goroutines退出后再返回。

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

sync.WaitGroup 可用于实现此要求。这个 documentation 是全面的。等待组是一个计数器,应该使用它的 Add Done 方法。代码可以通过调用其 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 一个错误修复。

Peter de Rivaz 7 年前

有没有更惯用的方法来做这个计算?

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

如果你使用 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)
}