素数查找算法的并行执行减慢了运行时间

Question

所以我在 go 中实现了以下素数查找算法。

1. 素数 = []

2. 假设所有数字都是素数（虚无真实）

3. 检查 = 2

4. 如果仍假定检查是素数，则将其附加到素数

5. 将小于或等于其最小因子的每个素数乘以检查，并消除假设素数的结果。

6. 将检查增加 1 并重复 4 到 6 直到检查 > 限制。

这是我的串行实现：

package main

import(

    "fmt"

    "time"

)

type numWithMinFactor struct {

    number int

    minfactor int

}

func pow(base int, power int) int{

    result := 1

    for i:=0;i<power;i++{

        result*=base

    }

    return result

}

func process(check numWithMinFactor,primes []int,top int,minFactors []numWithMinFactor){

    var n int

    for i:=0;primes[i]<=check.minfactor;i++{

        n = check.number*primes[i]

        if n>top{

            break;

        }

        minFactors[n] = numWithMinFactor{n,primes[i]}

        if i+1 == len(primes){

            break;

        }

    }

}

func findPrimes(top int) []int{

    primes := []int{}

    minFactors := make([]numWithMinFactor,top+2)

    check := 2

    for power:=1;check <= top;power++{

        if minFactors[check].number == 0{

            primes = append(primes,check)

            minFactors[check] = numWithMinFactor{check,check}

        }

        process(minFactors[check],primes,top,minFactors)

        check++

    }

    return primes

}

func main(){ 

    fmt.Println("Welcome to prime finder!")

    start := time.Now()

    fmt.Println(findPrimes(1000000))

    elapsed := time.Since(start)

    fmt.Println("Finding primes took %s", elapsed)

}

在我的电脑上，在大约 63 毫秒（主要是打印）内生成所有 <1,000,000 的素数和在 600 毫秒内生成 <10,000,000 的素数，运行效果很好。现在我认为没有一个数字检查使得 2^n < check <= 2^(n+1) 有因子 > 2^n 所以我可以在该范围内并行执行所有乘法和消除质数高达 2^n。

Answer 1

所以我最终得到了一个并行版本的代码，运行速度比串行版本略快。遵循@mh-cbon 的建议（见上文）。然而，这种实现相对于串行实现并没有带来巨大的改进（50ms 到 1000 万，而串行实现是 75ms）考虑到分配和写入 []int 0:10000000 需要 25ms，我对这些结果并不感到失望。正如@Volker 所说，“这些东西通常不受 CPU 的限制，而是受内存带宽的限制。”&nbsp;我相信这里就是这种情况。我仍然希望看到任何额外的改进，但是我对我在这里获得的东西有些满意。序列码运行高达 20 亿 19.4 秒并行代码运行高达 20 亿 11.1 秒初始化 []int{0:2Billion} 4.5 秒