Haskell -> F #: Tamiz de Turner

Question

Yo estaba leyendo en diferentes algoritmos de cribado cuando me topé con una especie de versión mejorada de la criba de Eratóstenes llamado tamiz de Euler. De acuerdo con Wikipedia existe una implementación de una versión ligeramente diferente de la idea (llamado tamiz de Turner) en Haskell.

Ahora estoy tratando de entender qué es exactamente el fragmento de código dado hace y creo que ya lo tengo pero ahora quería traducir el código en C # y tienen realmente ni idea de por dónde empezar. Mi principal preocupación es que no parece ser una función de "Restar" 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 sería esto puede implementar en C #? ¿Es posible?

Answer 1

Si desea calcular cosas como Fusiones / diferencias de infinitas listas como Haskell, el tipo LazyList (que se encuentra dentro de la unidad de alimentación # F) viene a la mente.

Lo que lo hace muy detallado código, al igual que 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 cláusulas failwith para mantener el compilador de quejarse de un partido incompleto, aun cuando sabemos que todas las listas en el cálculo son infinitos (pereza).

Answer 2

Puede hacerlo con ss . Y ya que conseguimos menos hecho, Euler en sí es igual 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 de la criba de Eratóstenes", como su desempeño en todos los sentidos es mucho peor que cualquier versión de la criba de Eratóstenes: Haskell Wiki en algoritmos de los números primos - Euler

A continuación, hay que decir que el código de @ CFEM usando LazyList de es un fiel aunque verbosa traducción de la versión del tamiz de Euler que diste, aunque le falta el ligero incremento de solo el tamizado de números impares según el enlace anterior.

Debe tenerse en cuenta que en realidad no hay ningún punto en la aplicación del tamiz de Euler, ya que es más complejo y más lento que la búsqueda de números primos por División de prueba Optimized (TDO) que solamente haciendo divisiones por números primos que se encuentran hasta la plaza raíz del número candidato a primer prueba según: Haskell Wiki en algoritmos de los números primos - TDO .

Este Trial División Optimized (TDO) tamiz puede ser implementado en F # usando LazyList de (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 del puesto LazyList se basan en secuencias almacenadas en caché. Tanto el uso de un objeto interno que representa una copia en caché de los números primos encontrado hasta ahora, almacenado automáticamente en el caso de LazyList de, y por el Seq.cache en el caso de secuencias. O bien puede encontrar los primeros 100.000 números primos en unos dos segundos.

Ahora, el Euler tamiz puede tener el número de tamizado optimización extraño 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 el partido comparar simplificada, así que 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, hay que señalar que el tiempo para calcular el primer 1899a (16.381) es de aproximadamente 0,2 y 0,16 segundos para el primesTDO y primesTDOS, respectivamente, mientras que es aproximadamente 2,5 segundos utilizando esta primesE para un tremendo rendimiento para el Euler tamiz en más de diez veces el tiempo, incluso para esta pequeña gama. Además de desempeño terrible, primeE no puede ni siquiera primos Calcular para 3000 debido hacerlo aún peor utilización de la memoria, ya que registra un número cada vez mayor de las funciones de ejecución diferida con el aumento de los números primos encontrados.

Tenga en cuenta que hay que tener cuidado en la sincronización repetida de la código como está escrito desde el LazyList es un valor y se ha incorporado en la memorización de los elementos previamente encontrados, por lo tanto una segunda exploración idéntica se llevará a cerca de la hora cero; para fines de sincronización que podría ser mejor para hacer el PrimeE una función que en PrimeE () por lo que el trabajo comienza desde el principio cada vez.

En resumen, la ecuación de Euler tamiz implementar en cualquier lenguaje, incluyendo F # es más que un ejercicio intelectual interesante y no tiene ningún uso práctico, ya que es mucho más lento y la memoria cerdos mucho peor que casi cualquier otro tamiz razonablemente optimizado.