F#低效序列处理：埃氏筛法Seq.skip操作性能问题排查

Hey there! Let's break down why your sieve implementation drags its feet when using Seq.skip on large inputs, and fix it up.

The Root of the Slowdown #

You’re spot-on about Seq.tail being the culprit. F# sequences are lazily evaluated—so primes 1000000 doesn’t do any actual work when you first call it, it just creates a blueprint for generating primes. But when you run Seq.skip 1000, the runtime has to compute every prime up to the 1001st one to skip the first 1000.

The problem with your removeFirstPrime function is that every Seq.tail call creates a brand new sequence that re-runs all previous filtering steps from scratch. For example, to get the 1000th prime, the code has to re-apply filters from the first prime (2) all the way through the 999th prime—every single time it generates the next element. That’s a ton of redundant computation, which is why it’s taking so long.

Let's Fix It #

Here are two solid solutions, depending on whether you want to stick with sequences or switch to a more efficient data structure.

Solution 1: Use an Array for Blazing-Fast Classic Sieve

Arrays are eager and support random access, making them perfect for the Sieve of Eratosthenes. This implementation precomputes all primes upfront, so Seq.skip (or Array.skip) will be near-instant:

let primesLessThan n =
    if n < 2 then
        [||]
    else
        // Initialize sieve: index = number, value = whether it's prime
        let sieve = Array.create n true
        sieve.[0] <- false
        sieve.[1] <- false
        
        // Mark non-primes
        for i in 2 .. int (sqrt(float n)) do
            if sieve.[i] then
                // Start at i*i, mark every multiple of i as non-prime
                for j in i*i .. i .. n-1 do
                    sieve.[j] <- false
        
        // Extract primes from the sieve
        sieve
        |> Array.mapi (fun idx isPrime -> if isPrime then Some idx else None)
        |> Array.choose id

To use it with skipping:

// Direct array skip (fastest)
primesLessThan 1000000 |> Array.skip 1000

// Convert to sequence if you need lazy behavior later
primesLessThan 1000000 |> Seq.ofArray |> Seq.skip 1000

Solution 2: Optimized Sequence-Based Sieve (If You Need Laziness)

If you really want to keep using sequences, avoid redundant filtering by tracking sieve state as you go. We’ll use a Map to track which multiples to exclude instead of re-filtering the entire sequence:

let primesLessThan n =
    let rec sieve candidates filters =
        match candidates with
        | [] -> []
        | x::xs ->
            match Map.tryFind x filters with
            | None ->
                // x is prime—add all its multiples to the filter map
                let newFilters = 
                    seq { x*x .. x .. n }
                    |> Seq.fold (fun map multiple ->
                        let existingDivisors = map.TryFind(multiple) |> Option.defaultValue []
                        map |> Map.add multiple (x :: existingDivisors)) filters
                x :: sieve xs newFilters
            | Some divisors ->
                // x is composite—update filters to track next multiples of its divisors
                let newFilters =
                    divisors
                    |> List.fold (fun map divisor ->
                        let nextMultiple = x + divisor
                        let existing = map.TryFind(nextMultiple) |> Option.defaultValue []
                        map |> Map.add nextMultiple (divisor :: existing))
                        (filters |> Map.remove x)
                sieve xs newFilters
    
    // Start with all numbers from 2 to n, empty filter map
    sieve [2 .. n] Map.empty
    |> Seq.ofList

Each number is processed only once here, so Seq.skip 1000 won’t re-run all previous steps—it generates primes in order without redundant work.

Key Takeaway #

Lazy sequences are great for many tasks, but they’re not the best fit for the Sieve of Eratosthenes unless you explicitly track state to avoid re-computation. For large inputs, the array-based approach is almost always the way to go—it’s O(n log log n) time and uses memory efficiently.

内容的提问来源于stack exchange，提问作者Patrick Stevens