F# problema parallelizzante quando si calcola numeri perfetti?

StackOverflow https://stackoverflow.com/questions/8368107

Domanda

Sto cercando di ottimizzare un piccolo programma che calcola i numeri perfetti da un determinato esponente.

Il programma funziona (quasi) perfettamente, ma quando apro il Task Manager, funziona ancora su un singolo thread. Ciò significa che devo fare qualcosa di sbagliato, ma la mia conoscenza di F# è ancora in una fase "iniziale".

Cercherò di mettere questa domanda il più chiaro possibile, ma se non riesco a farlo, per favore fatemelo sapere.

Un numero perfetto è un numero in cui la somma di tutti i suoi divisori (ad eccezione del numero stesso) è uguale al numero stesso (ad esempio 6 è perfetta, poiché la somma dei suoi divisori 1, 2 e 3 è 6).

Uso numeri primi per accelerare il calcolo, cioè non mi interessa elenchi (enormi) in cui tutti i divisori sono archiviati. Per fare ciò, uso la formula che Euclid si è rivelata corretta: (2* (potenza di num - 1))* (2* (potenza di Num - 1)) dove quest'ultimo è un primo mersenne. Ho usato un algoritmo molto veloce da StackOverflow (di @juliet) per determinare se un determinato numero è un primo.

Dato che ho letto diversi articoli (non ho ancora acquistato un buon libro, quindi una vergogna per me) su Internet, ho scoperto che le sequenze funzionano meglio delle liste. Ecco perché ho iniziato a creare una funzione che genera una sequenza di numeri perfetti:

   let perfectNumbersTwo (n : int) =  
    seq { for i in 1..n do 
           if (PowShift i) - 1I |> isPrime 
           then yield PowShift (i-1) * ((PowShift i)-1I)
        }

Il powshift di Helperfunction è implementato come segue:

    let inline PowShift (exp:int32) = 1I <<< exp ;;

Uso un operatore di bit shift, poiché la base di tutti i calcoli di potenza è da 2, quindi questo potrebbe essere un modo semplice. Ovviamente sono ancora grato per i contributi sulla domanda che ho posto su questo: F# Problemi di potere che accetta entrambi gli argomenti per essere bigint>F# Problemi di potere che accettano entrambi gli argomenti come bigint

La funzione ha creato Juliet (preso in prestito qui) è il seguente:

let isPrime ( n : bigint) = 
    let maxFactor = bigint(sqrt(float n))
    let rec loop testPrime tog =
        if testPrime > maxFactor then true
        elif n % testPrime = 0I then false
        else loop (testPrime + tog) (6I - tog)
    if n = 2I || n = 3I || n = 5I then true
    elif n <= 1I || n % 2I = 0I || n % 3I = 0I || n % 5I = 0I then false
    else loop 7I 4I;;

Usando questo codice, senza parallelo, ci vogliono circa 9 minuti sul mio laptop per trovare il nono numero perfetto (che consiste in 37 cifre e può essere trovato con il valore 31 per l'esponente). Dato che il mio laptop ha una CPU con due core e solo uno è in esecuzione al 50 percento (carico completo per un nucleo), anche se potrei accelerare i calcoli calcolando i risultati paralleli.

Quindi ho cambiato la mia funzione perfetta come segue:

//Now the function again, but async for parallel computing
let perfectNumbersAsync ( n : int) =
    async {
        try
            for x in 1.. n do
                if PowShift x - 1I |> isPrime then
                    let result = PowShift (x-1) * ((PowShift x)-1I)
                    printfn "Found %A as a perfect number" result
        with
            | ex -> printfn "Error%s" (ex.Message);
    }

Per chiamare questa funzione, utilizzo una piccola funzione di supporto per eseguirla:

 let runPerfects n =
    [n]
        |> Seq.map perfectNumbersAsync
        |> Async.Parallel
        |> Async.RunSynchronously
        |> ignore

Laddove il risultato del calcolo dell'asincronizzazione viene ignorato, poiché lo sto mostrando all'interno della funzione perfettanumbersasync.

Il codice sopra compila e funziona, tuttavia utilizza ancora solo un core (sebbene funziona più velocemente quando si calcola il 9 ° numero perfetto). Temo che debba fare qualcosa con l'helper funzioni Powshift e isprime, ma non sono sicuro. Devo mettere il codice di queste funzioni di supporto all'interno del blocco asincrico di PerfectNumbersync? Non migliora la leggibilità ...

Più gioco con F#, più imparo ad apprezzare questa lingua, ma come in questo caso, ho bisogno di alcuni esperti a volte :).

Grazie in anticipo per aver letto questo, spero solo di avermi chiarito un po '...

Roberto.

È stato utile?

Soluzione

Il commento di @jeffrey sax è decisamente interessante, quindi ho impiegato del tempo per fare un piccolo esperimento. Il test Lucas-Lehmer è scritto come segue:

let lucasLehmer p =
    let m = (PowShift p) - 1I
    let rec loop i acc =
        if i = p-2 then acc
        else loop (i+1) ((acc*acc - 2I)%m)
    (loop 0 4I) = 0I

Con il test Lucas-Lehmer, posso ottenere i primi numeri perfetti molto velocemente:

let mersenne (i: int) =     
    if i = 2 || (isPrime (bigint i) && lucasLehmer i) then
        let p = PowShift i
        Some ((p/2I) * (p-1I))
    else None

let runPerfects n =
    seq [1..n]
        |> Seq.choose mersenne
        |> Seq.toArray

let m1 = runPerfects 2048;; // Real: 00:00:07.839, CPU: 00:00:07.878, GC gen0: 112, gen1: 2, gen2: 1

Il test Lucas-Lehmer aiuta a ridurre il tempo di controllo dei numeri primi. Invece di testare la divisibilità di 2^p-1 che prende O(sqrt(2^p-1)), usiamo il test di primalità che è al massimo O(p^3). Insieme a n = 2048, Sono in grado di trovare i primi 15 numeri di Mersenne in 7,83 secondi. Il 15 numero di Mersenne è quello con i = 1279 ed è composto da 770 cifre.

Ho provato a parallelizzare runPerfects usando il modulo pSeq in F# powerpack. PSEQ non preserva l'ordine della sequenza originale, quindi per essere onesti ho ordinato la sequenza di output. Poiché il test di primalità è abbastanza equilibrato tra gli indici, il risultato è piuttosto incoraggiante:

#r "FSharp.Powerpack.Parallel.Seq.dll"    
open Microsoft.FSharp.Collections

let runPerfectsPar n =
    seq [1..n]
        |> PSeq.choose mersenne
        |> PSeq.sort (* align with sequential version *)
        |> PSeq.toArray 

let m2 = runPerfectsPar 2048;; // Real: 00:00:02.288, CPU: 00:00:07.987, GC gen0: 115, gen1: 1, gen2: 0

Con lo stesso input, la versione parallela ha richiesto 2,28 secondi, equivalente a 3,4x SpeedUp sulla mia macchina quad-core. Credo che il risultato potrebbe essere migliorato ulteriormente se usi Parallel.For costruisci e partizione l'intervallo di input in modo sensato.

Altri suggerimenti

Un rapido commento su velocità e parallelibilità,

Tuo isPrime è o (sqrt (n)) e ogni n -successivo è circa 2 x grande come l'ultimo, quindi richiederà circa 1,5 x per calcolare, il che significa che il calcolo degli ultimi numeri richiederà molto più tempo

Ho fatto un po 'di hacking con i test per la primalità e alcune cose che ho trovato che sono utili sono:

  1. Per Big N, (stai testando numeri con 20 cifre), la densità primaria è in realtà piuttosto bassa, quindi farai molte divisioni in base a numeri compositi. Un approccio migliore è quello di precalcolare una tabella di numeri primi (usando un setaccio) fino a un limite massimo (probabilmente determinato dalla quantità di memoria). Si noti che è più probabile che tu trovi fattori con piccoli numeri. Una volta esaurito la memoria per la tua tabella, puoi testare il resto dei numeri con la tua funzione esistente, con un punto di partenza più ampio.

  2. Un altro approccio è utilizzare più thread nel controllo. Ad esempio, attualmente controlli x,x+4,x+6... come fattori. Essendo leggermente più intelligente, puoi fare il numero congruente a 1 mod 3 in 1 thread e i numeri congruenti a 2 mod 3 in un altro thread.

Il n. 2 è più semplice, ma il n. 1 è più efficace e fornisce il potenziale per eseguire il flusso di controllo con outofmemoryexceptions che possono sempre essere interessanti

MODIFICARE:Così ho implementato entrambe queste idee, trova 2305843008139952128 quasi istantaneamente, trovando 2658455991569831744654692615953842176 impiegando 7 minuti sul mio computer (Quad Core AMD 3200). Il più delle volte viene dedicato al controllo di 2^61 è primo, quindi un algoritmo migliore sarebbe probabilmente migliore per controllare i numeri primi: codice qui

let swatch = new System.Diagnostics.Stopwatch()
swatch.Start()
let inline PowShift (exp:int32) = 1I <<< exp ;;
let limit = 10000000 //go to a limit, makes table gen slow, but should pay off
printfn "making table"
//returns an array of all the primes up to limit
let table =
    let table = Array.create limit true //use bools in the table to save on memory
    let tlimit = int (sqrt (float limit)) //max test no for table, ints should be fine
    table.[1] <- false //special case
    [2..tlimit] 
    |> List.iter (fun t -> 
        if table.[t]  then //simple optimisation
            let mutable v = t*2
            while v < limit do
                table.[v] <- false
                v <- v + t)
    let out = Array.create (50847534) 0I //wolfram alpha provides pi(1 billion) - want to minimize memory
    let mutable idx = 0
    for x in [1..(limit-1)] do
        if table.[x] then
            out.[idx] <- bigint x
            idx <- idx + 1
    out |> Array.filter (fun t -> t <> 0I) //wolfram no is for 1 billion as limit, we use a smaller number
printfn "table made"

let rec isploop testprime incr max n=
    if testprime > max then true
    else if n % testprime = 0I then false
    else isploop (testprime + incr) incr max n

let isPrime ( n : bigint) = 
    //first test the table
    let maxFactor = bigint(sqrt(float n))
    match table |> Array.tryFind (fun t -> n % t = 0I && t <= maxFactor) with
    |Some(t) -> 
        false
    |None -> //now slow test
        //I have 4 cores so
        let bases = [|limit;limit+1;limit+3;limit+4|] //uses the fact that 10^x congruent to 1 mod 3
        //for 2 cores, drop last 2 terms above and change 6I to 3I
        match bases |> Array.map (fun t -> async {return isploop (bigint t) 6I maxFactor n}) |> Async.Parallel |> Async.RunSynchronously |> Array.tryFind (fun t -> t = false) with
        |Some(t) -> false
        |None -> true


let pcount = ref 0
let perfectNumbersTwo (n : int) =  
    seq { for i in 2..n do 
           if (isPrime (bigint i)) then
                if (PowShift i) - 1I |> isPrime then
                    pcount := !pcount + 1
                    if !pcount = 9 then
                        swatch.Stop()
                        printfn "total time %f seconds, %i:%i m:s"  (swatch.Elapsed.TotalSeconds) (swatch.Elapsed.Minutes) (swatch.Elapsed.Seconds)
                    yield PowShift (i-1) * ((PowShift i)-1I)
        } 


perfectNumbersTwo 62 |> Seq.iter (printfn "PERFECT: %A") //62 gives 9th number

printfn "done"
System.Console.Read() |> ignore
Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top