当在F#中生成素数时，为什么会出现“色母筛"?在这个特定的实施中这么慢? [英] When Generating Primes in F#, why is the "Sieve of Erosthenes" so slow in this particular implementatIon?

问题描述

IE，

我在这里做错了什么?是否必须使用列表，序列和数组以及限制的工作方式?

所以这是设置:我正在尝试生成一些素数.我看到有十亿个素数的十亿个文本文件.问题不是为什么...问题是使用python的人如何在

在FSI中启用计时器后，我得到100,000个CPU的价值为4.33秒...在那之后，这一切都爆了.

解决方案

您的筛选功能很慢，因为您尝试筛选出top_number以下的复合数字.使用Eratosthenes筛网，您只需要这样做，直到sqrt(top_number)和其余数字本质上为质数为止.假设我们有top_number = 1,000,000，则您的函数执行78498次过滤(直到1,000,000的素数)，而原始筛只进行168次(直到1,000的素数).

您可以避免生成除2以外的偶数，这些数从一开始就不能是素数.此外，sieve和sieve_prime可以合并为递归函数.您可以使用轻量级的List.filter而不是List.choose.

结合以上建议:

let sieve_primes top_number = 
    let numbers = [ yield 2
                    for i in 3..2..top_number -> i ]
    let rec sieve ns = 
        match ns with
        | [] -> []
        | x::xs when x*x > top_number -> ns
        | x::xs -> x::sieve (List.filter(fun y -> y%x <> 0) xs)
    sieve numbers 

在我的机器上，更新的版本非常快，对于top_number = 1,000,000，它的更新时间为0.6秒.

IE,

What am I doing wrong here? Does it have to to with lists, sequences and arrays and the way the limitations work?

So here is the setup: I'm trying to generate some primes. I see that there are a billion text files of a billion primes. The question isn't why...the question is how are the guys using python calculating all of the primes below 1,000,000 in milliseconds on this post...and what am I doing wrong with the following F# code?

let sieve_primes2 top_number = 
    let numbers = [ for i in 2 .. top_number do yield i ]
    let sieve (n:int list) = 
        match n with
        | [x] -> x,[]
        | hd :: tl -> hd, List.choose(fun x -> if x%hd = 0 then None else Some(x)) tl
        | _ -> failwith "Pernicious list error."
    let rec sieve_prime (p:int list) (n:int list) =  
        match (sieve n) with
        | i,[] -> i::p
        | i,n'  -> sieve_prime (i::p) n'
    sieve_prime [1;0] numbers 

With the timer on in FSI, I get 4.33 seconds worth of CPU for 100000... after that, it all just blows up.

解决方案

Your sieve function is slow because you tried to filter out composite numbers up to top_number. With Sieve of Eratosthenes, you only need to do so until sqrt(top_number) and remaining numbers are inherently prime. Suppose we havetop_number = 1,000,000, your function does 78498 rounds of filtering (the number of primes until 1,000,000) while the original sieve only does so 168 times (the number of primes until 1,000).

You can avoid generating even numbers except 2 which cannot be prime from the beginning. Moreover, sieve and sieve_prime can be merged into a recursive function. And you could use lightweight List.filter instead of List.choose.

Incorporating above suggestions:

let sieve_primes top_number = 
    let numbers = [ yield 2
                    for i in 3..2..top_number -> i ]
    let rec sieve ns = 
        match ns with
        | [] -> []
        | x::xs when x*x > top_number -> ns
        | x::xs -> x::sieve (List.filter(fun y -> y%x <> 0) xs)
    sieve numbers 

In my machine, the updated version is very fast and it completes within 0.6s for top_number = 1,000,000.

这篇关于当在F#中生成素数时，为什么会出现“色母筛"?在这个特定的实施中这么慢?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！