Haskell -> F #: di Turner Sieve

Question

ho letto su diversi algoritmi di setacciatura, quando sono incappato in una sorta di versione migliorata del crivello di Eratostene chiamato Sieve di Eulero. Secondo Wikipedia v'è un'implementazione di una versione leggermente diversa di questa idea (chiamato di Turner Sieve) in Haskell.

Ora sto cercando di capire che cosa esattamente il frammento di codice dato fa e credo di aver capito, ma ora ho voluto tradurre il codice in C # e ho davvero nessuna idea da dove cominciare. La mia preoccupazione principale è che non sembra essere una funzione di "Sottrarre" due sequenze.

Ecco il codice:

import Data.OrdList (minus)

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

Come potrebbe questo essere implementato in F #? E 'anche possibile?

Answer 1

Se si desidera calcolare le cose come Unisce / differenze di liste infinite come Haskell fa, il tipo lazylist (che si trova all'interno del gruppo di alimentazione F #) viene in mente.

Si fa per codice molto prolisso, come la traduzione di seguito:

#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]

Si noti che ho aggiunto due clausole failwith per mantenere il compilatore da lamentarsi delle partite incompleta, anche se sappiamo che tutte le liste nel calcolo sono (pigramente) infinita.

Answer 2

È possibile farlo con ss . E come hai meno fatto, Euler è di per sé stesso che in 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 sequenze, si ottiene molto di più competitivo persistendo la sequenza:

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

In primo luogo, va detto che il vaglio di Eulero per numeri primi non è una "versione migliorata del crivello di Eratostene", come le sue prestazioni in tutti i sensi è molto peggio di qualsiasi versione del crivello di Eratostene: Haskell Wiki su algoritmi Prime Number - Euler

Avanti, va detto che la @ di CFEM codice utilizzando lazylist di un fedele, anche se di traduzione verbose della versione del vaglio di Eulero che ti ha dato, anche se manca il lieve miglioramento di soli setacciatura numeri dispari come per il link qui sopra.

Si dovrebbe notare che non c'è davvero alcun punto nella realizzazione del vaglio di Eulero, in quanto è più complesso e più lento di trovare numeri primi da Trial Division Optimized (TDO) da solo facendo le divisioni con numeri primi trovati fino alla piazza radice del candidato numero testato per primo secondo: Haskell Wiki su algoritmi Prime Number - TDO .

Questo Trial Division Optimized (TDO) setaccio può essere implementato in C # utilizzando di lazylist (con un riferimento al FSharp.PowerPack.dll) come:

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)

Può essere implementato utilizzando sequenze nella stessa forma come:

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 versione sequenza è leggermente più veloce rispetto alla versione lazylist perché evita un certo overhead nel chiamare attraverso dal lazylist si basano su sequenze nella cache. Entrambi utilizzano un oggetto interno che rappresenta una copia memorizzata nella cache dei numeri primi trovato finora, cache automaticamente nel caso di lazylist di, e dal Seq.cache nel caso di sequenze. O possono trovare i primi 100.000 numeri primi in circa due secondi.

Ora, la Euler setaccio può avere il numero dispari setacciatura ottimizzazione e espressi ricorrendo lazylist di come il seguente, con una partita in caso eliminato a causa sapendo che i parametri della lista di ingresso sono infinite e la partita confrontano semplificata, così ho aggiunto un operatore '^' per rendere il codice più leggibile:

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))

Tuttavia, si deve notare che il tempo per calcolare il primo 1899i (16381) è di circa 0,2 e 0,16 secondi per l'primesTDO e primesTDOS, rispettivamente, mentre si tratta di circa 2,5 secondi con questo primesE per una prestazione terribile per l'Euler setaccio a oltre dieci volte il tempo anche per questo piccolo intervallo. Oltre alle prestazioni terribile, primeE non può nemmeno calcolare i numeri primi a 3000 a causa fare utilizzo della memoria anche peggio in quanto registra un numero rapidamente crescente di funzioni esecuzione differita con l'aumentare trovato numeri primi.

Si noti che si deve fare attenzione nel ripetuta temporizzazione del codice riportato in quanto il lazylist è un valore e è dotato di memorizzazione precedentemente trovato elementi, quindi una seconda scansione identica prenderà vicino al tempo zero; per scopi di temporizzazione potrebbe essere meglio fare la PrimeE una funzione come in PrimeE () quindi il lavoro inizia dall'inizio ogni volta.

In sintesi, il setaccio di Eulero implementato in tutte le lingue tra cui F # è solo un esercizio intellettuale interessante e non ha alcuna utilità pratica in quanto è molto più lento e la memoria maiali molto peggio di quasi tutti gli altri setaccio ragionevolmente ottimizzato.