计算mod逆

问题描述 投票：1回答：2

我想在模运算中计算素数的逆元素。为了加快速度，我开始尝试在某个范围内找到元素的几个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)
}
algorithm go goroutine
2个回答
0
投票

这是一个糟糕的风格，我应该像WaitGroup？

等待组解决了另一个问题。

一般而言，要成为负责任的公民并确保您的代码运行并整理自己，您可能需要组合：

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

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

但是，如果您将此代码包装到库中或者它成为长期运行的“反向素数计算”服务的一部分，则需要整理您生成的goroutine以避免不必要地浪费周期。此外，一般情况下，您可能还有其他场景，其中goroutines存储状态，保持外部资源的句柄，或者保留内部对象的句柄，如果没有正确整理，您可能会泄漏 - 需要正确关闭它们。

Communicating the requirement to stop working

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

使用特殊频道

通过关闭为此目的保留的特殊“关闭”通道来通知子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返回的时间。

这种方法与前一种方法大致相同，除了neater封装和上下文的可用性，以传递到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退出。

Waiting (or "join"ing) for child goroutines to stop

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

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。

1
投票

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

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

如果你使用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)
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.