Estoy implementando dos versiones de Eratosthenes's Sieve, la primera es imperativa:
let primesUntilArray n = let isqrt x = let mutable root = 0UL let mutable p = 1UL <<< 31 while p > 0UL do while x < (root + p) * (root + p) do p <- p >>> 1 root <- root + p p <- p >>> 1 root let isPrime = Array.create (int <| n + 1) true let bound = int <| isqrt (uint64 n) let mutable i = 2 while i <= bound do if isPrime.[i] then let mutable j = i * i while j <= n do isPrime.[j] <- false j <- j + i i <- i + 1 let mutable primes = [] let mutable i = 2 while i <= n do if isPrime.[i] then primes <- i :: primes i <- i + 1 List.rev primesmientras que el segundo es funcional (con la secuencia de F#):
let primesUntilSequence n = let rec pickPrimes s = let sieveWith p = Seq.filter (fun n -> n < p * p || n % p <> 0) let p = Seq.head s seq { yield p yield! pickPrimes (sieveWith p (Seq.tail s)) } Seq.initInfinite (fun i -> i + 2) |> pickPrimes |> Seq.takeWhile (fun p -> p <= n) |> Seq.toList La complejidad temporal de ambos es de O(n log log n) , pero el rendimiento de la versión que utiliza la secuencia es muy malo, por ejemplo
> primesUntilArray 9000 |> List.length |> printfn "%d";; 1117 Real: 00:00:00.004, CPU: 00:00:00.000, GC Gen0: 1, Gen1: 0, Gen2: 0 val it: unit = () > primesUntilSequence 9000 |> List.length |> printfn "%d";; 1117 Real: 00:00:15.388, CPU: 00:00:15.375, GC Gen0: 592, Gen1: 64, Gen2: 0 val it: unit = ()Eso significa unas 4000 veces más lento en generar primos hasta 9000. ¿Cómo puedo mejorar el rendimiento del segundo?
Gracias a todos. La siguiente es una versión ligeramente modificada de la solución de @Tomas Petricek
let primesUntilList n = let rec pickPrimes ps xs = let sieveWith p = List.filter (fun n -> n < p * p || n % p <> 0) match xs with | p :: xs' -> if p * p > n then (List.rev xs) @ ps else pickPrimes (p :: ps) (sieveWith p xs') | _ -> ps List.rev <| pickPrimes [] [ 2..n ]Esta versión basada en listas sigue siendo aproximadamente dos veces menos eficiente que el uso de arreglos, pero mucho mejor que mi versión inicial basada en secuencias.
El problema con su versión basada en secuencias es que deconstruir una secuencia usando Seq.head y Seq.tail de forma recursiva es muy ineficiente. La secuencia devuelta por Seq.tail itera la secuencia original, pero omite el primer elemento. Esto significa que al aplicar Seq.tail de forma recursiva, está creando más y más secuencias (supongo que esto es O (N ^ 2)) que necesita iterar.
Esto se vuelve mucho más eficiente si usa una lista, donde la coincidencia de patrones con x::xs simplemente toma una referencia a la siguiente celda de contras:
let primesUntilList n = let rec pickPrimes s = let sieveWith p = List.filter (fun n -> n < p * p || n % p <> 0) match s with | [] -> [] | p::ps -> p :: pickPrimes (sieveWith p ps) [ 2 .. n ] |> pickPrimesEsto sigue siendo menos eficiente que la versión basada en matrices (y creo que eso es de esperar), pero no funciona tan mal como la versión basada en secuencias.
Seq.cache es útil cuando desea evaluar una secuencia varias veces (que es efectivamente lo que está haciendo Seq.tail ). Puede colocarlo en su código original de esta manera:
let primesUntilSequence n = let rec pickPrimes s = let sieveWith p = Seq.filter (fun n -> n < p * p || n % p <> 0) let s = Seq.cache s // *** cache the sequence *** let p = Seq.head s seq { yield p yield! pickPrimes (sieveWith p (Seq.tail s)) } Seq.initInfinite (fun i -> i + 2) |> pickPrimes |> Seq.takeWhile (fun p -> p <= n) |> Seq.toList En mi caja, primesUntilSequence 9000 ahora se ejecuta en aproximadamente un cuarto de segundo.
Cuando se trata de problemas de rendimiento de secuencias, puede ser útil trabajar con ellos de forma imperativa dentro de las expresiones de secuencia. En resumen, traiga su propio enumerador.
Esto sigue siendo terriblemente ineficiente, en comparación con los enfoques de array y list . Al menos, tiene control total sobre la asignación de los recursos que requieren las secuencias anidadas.
type IEnumerator<'a> = System.Collections.Generic.IEnumerator<'a> let primesUntilIterator n = let sieveWith p (en : IEnumerator<_>) = seq{ while en.MoveNext() do let n = en.Current if n < p * p || n % p <> 0 then yield n } let rec pickPrimes (s : seq<_>) = seq{ use en = s.GetEnumerator() if en.MoveNext() then let p = en.Current yield p yield! pickPrimes (sieveWith p en) } { 2..n } |> pickPrimes