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

Question

所以我在 go 中实现了以下素数查找算法。素数 = []假设所有数字都是素数（虚无真实）检查 = 2如果仍假定检查是素数，则将其附加到素数将小于或等于其最小因子的每个素数乘以检查，并消除假设素数的结果。将检查增加 1 并重复 4 到 6 直到检查 > 限制。这是我的串行实现：package mainimport(    "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 的限制，而是受内存带宽的限制。” 我相信这里就是这种情况。

我仍然希望看到任何额外的改进，但是我对我在这里获得的东西有些满意。

• 序列码运行高达 20 亿 19.4 秒

• 并行代码运行高达 20 亿 11.1 秒

• 初始化 []int{0:2Billion} 4.5 秒