Mein ursprüngliches Ziel beim Schreiben war es, den kleinstmöglichen Platzbedarf zu haben. Ich kann mit Zuversicht sagen, dass dieses Ziel erreicht wurde. Dies führt leider zu einer recht langsamen Implementierung. Das Generieren aller Primzahlen unter 2 Millionen dauert auf einem 3 GHz-Intel-Chip ungefähr 8 Sekunden.

Gibt es überhaupt eine Möglichkeit, die Ausführungszeit dieses Codes zu verbessern, ohne den geringen Speicherbedarf zu beeinträchtigen? Oder gehe ich das falsch an, wenn ich es vom funktionalen Standpunkt aus betrachte?

CODE

/// 6.5s for max = 2,000,000
let generatePrimeNumbers max =    
    let rec generate number numberSequence =
        if number * number > max then numberSequence else
        let filteredNumbers = numberSequence |> Seq.filter (fun v -> v = number || v % number <> 0L)
        let newNumberSequence = seq { for i in filteredNumbers -> i }
        let newNumber = newNumberSequence |> Seq.find (fun x -> x > number)
        generate newNumber newNumberSequence                
    generate 2L (seq { for i in 2L..max -> i })

Aktualisieren

Ich habe den Algorithmus optimiert und es geschafft, 2 Sekunden zu sparen, aber den Speicherverbrauch zu verdoppeln.

/// 5.2s for max = 2,000,000
let generatePrimeNumbers max =    
    let rec generate number numberSequence =
        if number * number > max then numberSequence else
        let filteredNumbers = numberSequence |> Seq.filter (fun v -> v = number || v % number <> 0L) |> Seq.toArray |> Array.toSeq
        let newNumber = filteredNumbers |> Seq.find (fun v -> v > number)
        generate newNumber filteredNumbers                
    generate 2L (seq { for i in 2L..max -> i })

Aktualisieren

Anscheinend habe ich einen alten Compiler verwendet. Mit der neuesten Version dauert mein ursprünglicher Algorithmus 6,5s anstatt 8s. Das ist eine ziemliche Verbesserung.