Haskell -> F #: Tamiz de Turner

Question

Estaba leyendo en diferentes algoritmos de tamizado cuando me encontré con una especie de versión mejorada de la Tamiz de Eratóstenes llamada Tamiz de Euler. De acuerdo con Wikipedia hay una implementación de una versión ligeramente diferente de la idea (llamada Tamiz de Turner) en Haskell.

Ahora trato de entender qué es exactamente lo que hace el fragmento de código y creo que lo tengo, pero ahora quería traducir el código a F # y realmente no tengo idea de dónde empezar. Mi principal preocupación es que no parece haber una función para "sustraer" dos secuencias.

Aquí está el código:

import Data.OrdList (minus) 

primes = euler [2..] 
euler (p : xs) = p : euler (xs `minus` map (*p) (p : xs)) 

¿Cómo esta implementarse en C#? ¿Es posible?

Answer 1

Si quiere calcular la diferencia como combinaciones/diferencias de listas infinitas como Haskell, el tipo LazyList (que se encuentra dentro del paquete de alimentación F #) viene a la mente.

Se convierte en un código muy detallado, como la traducción a continuación:

#r "FSharp.PowerPack.dll" 

//A lazy stream of numbers, starting from x 
let rec numsFrom x = LazyList.consDelayed x (fun() -> numsFrom (x+1)) 

//subtracts L2 from L1, where L1 and L2 are both sorted(!) lazy lists 
let rec lazyDiff L1 L2 = 
    match L1,L2 with 
     | LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1<x2 -> 
      LazyList.consDelayed x1 (fun() -> lazyDiff xs1 L2) 
     | LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1=x2 -> 
      lazyDiff xs1 L2 
     | LazyList.Cons(x1,xs1),LazyList.Cons(x2,xs2) when x1>x2 -> 
      lazyDiff L1 xs2 
     | _ -> failwith "Should not occur with infinite lists!" 

let rec euler = function 
    | LazyList.Cons(p,xs) as LL -> 
     let remaining = lazyDiff xs (LazyList.map ((*) p) LL) 
     LazyList.consDelayed p (fun() -> euler remaining) 
    | _ -> failwith "Should be unpossible with infinite lists!" 

let primes = euler (numsFrom 2) 

con

> primes |> Seq.take 15 |> Seq.toList;; 
val it : int list = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47] 

Tenga en cuenta que he añadido dos failwith cláusulas para mantener el compilador de quejarse de un partido incompleto, incluso si sabemos que todas las listas en el cálculo son (perezosamente) infinitas.

Answer 2

Puede hacerlo con seq. Y como obtuvo menos hecho, euler es el mismo que en Haskell.

let rec minus xs ys = 
    seq { 
    match Seq.isEmpty xs, Seq.isEmpty ys with 
    | true,_ | _,true -> yield! xs 
    | _ -> 
     let x,y = Seq.head xs, Seq.head ys 
     let xs',ys' = Seq.skip 1 xs, Seq.skip 1 ys 
     match compare x y with 
     | 0 -> yield! minus xs' ys' 
     | 1 -> yield! minus xs ys' 
     | _ -> yield x; yield! minus xs' ys 
    } 

let rec euler s = 
    seq { 
    let p = Seq.head s 
    yield p 
    yield! minus (Seq.skip 1 s) (Seq.map ((*) p) s) |> euler 
    } 

let primes = Seq.initInfinite ((+) 2) |> euler 

Answer 3

Con secuencias, se obtiene mucho más competitivo, al persistir la secuencia:

let rec euler s = 
    seq { 
     let s = Seq.cache s 
     let p = Seq.head s 
     yield p 
     yield! minus (Seq.skip 1 s) (Seq.map ((*) p) s) |> euler 
    } 

Answer 4

En primer lugar, hay que decir que el tamiz de Euler para los números primos no es una "versión mejorada del tamiz de Eratóstenes "como su actuación en todos los sentidos es mucho peor que cualquier versión del Tamiz de Eratóstenes: Haskell Wiki on Prime Number algorithms - Euler

A continuación, debe decirse que el código de @cfem usando LazyList es una traducción fiel aunque prolija de la versión de Euler ' s tamiz que le diste, aunque le falta la ligera mejora de solo tamizar números impares según el enlace de arriba.

Cabe señalar que no hay ningún punto en la implementación del tamiz de Euler, ya que es más complejo y más lento que encontrar primos por Trial Division Optimized (TDO) que solo hacer divisiones por primos encontrados hasta el raíz cuadrada del número de candidato probado para primo según: Haskell Wiki on Prime Number algorithms - TDO.

Este Tamiz de división de prueba optimizada (TDO) se puede implementar en F # utilizando LazyList (con una referencia a FSharp.PowerPack.DLL) como:

let primesTDO() = 
    let rec oddprimes = 
    let rec oddprimesFrom n = 
     if oddprimes |> Seq.takeWhile (fun p -> p * p <= n) |> Seq.forall (fun p -> (n % p) <> 0) 
     then LazyList.consDelayed n (fun() -> oddprimesFrom (n + 2)) 
     else oddprimesFrom (n + 2) 
    LazyList.consDelayed 3 (fun() -> oddprimesFrom 5) 
    LazyList.consDelayed 2 (fun() -> oddprimes) 

Se puede implementar el uso de secuencias en la misma forma que:

let primesTDOS() = 
    let rec oddprimes = 
    let rec oddprimesFrom n = 
     if oddprimes |> Seq.takeWhile (fun p -> p * p <= n) |> Seq.forall (fun p -> (n % p) <> 0) 
     then seq { yield n; yield! oddprimesFrom (n + 2) } 
     else oddprimesFrom (n + 2) 
    seq { yield 3; yield! (oddprimesFrom 5) } |> Seq.cache 
    seq { yield 2; yield! oddprimes } 

La versión de secuencia es ligeramente más rápido que la versión LazyList porque evita cierta sobrecarga en llamar a través de desde LazyList de se basan en secuencias en caché. Ambos usan un objeto interno que representa una copia en caché de los números primos encontrados hasta el momento, automáticamente en caché en el caso de LazyList, y por el Seq.cache en el caso de las secuencias. Cualquiera puede encontrar los primeros 100,000 primos en aproximadamente dos segundos.

Ahora, el Euler tamiz puede tener el número impar de optimización de tamizado y expresarse utilizando LazyList de que el siguiente, con un caso fósforo eliminado debido a sabiendas de que los parámetros de la lista de entrada son infinitos y la comparan partido simplificado, así he añadido un operador '^' para hacer el código más legible:

let primesE = //uses LazyList's from referenced FSharp.PowerPack.dll version 4.0.0.1 
    let inline (^) a ll = LazyList.cons a (LazyList.delayed ll) //a consd function for readability 
    let rec eulers xs = 
    //subtracts ys from xs, where xs and ys are both sorted(!) infinite lazy lists 
    let rec (-) xs ys = 
     let x,xs',ys' = LazyList.head xs,LazyList.tail xs,LazyList.tail ys 
     match compare x (LazyList.head ys) with 
     | 0 -> xs' - ys' // x == y 
     | 1 -> xs - ys' // x > y 
     | _ -> x^(fun()->(xs' - ys)) // must be x < y 
    let p = LazyList.head xs 
    p^(fun() -> (((LazyList.tail xs) - (LazyList.map ((*) p) xs)) |> eulers)) 
    let rec everyothernumFrom x = x^(fun() -> (everyothernumFrom (x + 2))) 
    2^(fun() -> ((everyothernumFrom 3) |> eulers)) 

Sin embargo, debe tenerse en cuenta que el tiempo para calcular el primer 1899a (16381) es de aproximadamente 0,2 y 0,16 segundos para el primesTDO y primesTDOS, respectivamente, mientras que es alrededor de 2,5 segundos utilizando este primesE para un rendimiento terrible para el tamiz de Euler en más de diez veces el tiempo, incluso para este pequeño l rango Además de un rendimiento terrible, PrimeE ni siquiera puede calcular números primos a 3000 debido a la utilización de la memoria incluso peor, ya que registra un número cada vez mayor de funciones de ejecución diferida con el aumento de números primos encontrados.

Tenga en cuenta que debe tenerse cuidado en la sincronización repetida del código tal como está escrito, ya que LazyList es un valor y tiene una memorización incorporada de los elementos encontrados previamente, por lo que un segundo escaneo idéntico llevará casi tiempo cero; por motivos de tiempo, podría ser mejor hacer de PrimeE una función como en PrimeE() para que el trabajo comience desde el principio cada vez.

En resumen, el tamiz de Euler implementado en cualquier idioma, incluido F #, es solo un ejercicio intelectual interesante y no tiene uso práctico, ya que es mucho más lento y consume mucho más memoria que cualquier otro tamiz razonablemente optimizado.