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

问题描述

浏览器，

我在这里做错了什么?它是否与列表、序列和数组以及限制的工作方式有关?

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

所以这里是设置:我正在尝试生成一些素数.我看到有十亿个素数的十亿个文本文件.问题不是为什么...问题是使用 python 的人如何在 这篇文章...下面的 F# 代码我做错了什么?

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 

在 FSI 中打开计时器后，我获得了 4.33 秒的 CPU 用于 100000 ......之后，一切都爆炸了.

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

推荐答案

您的筛选功能很慢，因为您试图过滤掉小于 top_number 的合数.使用 Eratosthenes 筛法，您只需要这样做直到 sqrt(top_number) 和剩余的数字本质上是素数.假设我们有top_number = 1,000,000，您的函数会进行78498 轮过滤(直到1,000,000 的素数数)，而原始筛选仅这样做168 次(直到 1,000 的素数数).

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

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

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.

结合以上建议:

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 秒内完成.

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

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