F# Parallelisierungsproblem bei Berechnung perfekter Zahlen?

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

Frage

Ich versuche, ein kleines Programm zu optimieren, das perfekte Zahlen aus einem bestimmten Exponenten berechnet.

Das Programm läuft (fast) perfekt, aber wenn ich den Task -Manager öffne, läuft es immer noch auf einem einzigen Thread. Das bedeutet, dass ich etwas falsch machen muss, aber mein Wissen über F# befindet sich immer noch in einer Beginnsphase.

Ich werde versuchen, diese Frage so klar wie möglich zu stellen, aber wenn ich dies nicht mache, lassen Sie es mich bitte wissen.

Eine perfekte Zahl ist eine Zahl, bei der die Summe aller Teilnehmer (mit Ausnahme der Zahl selbst) gleich der Zahl selbst ist (z. B. 6 ist perfekt, da die Summe der Divisors 1, 2 und 3 6 ist).

Ich verwende Primzahlen, um die Berechnung zu beschleunigen. Ich interessiere mich nicht für (riesige) Listen, in denen alle Divisors gespeichert werden. Dazu benutze ich die Formel, dass sich Euklid als korrekt erwies: (2* (Leistung von Num - 1))* (2* (Kraft von Num - 1)), wobei letzteres eine Mersenne -Primzahl ist. Ich habe einen sehr schnellen Algorithmus von Stackoverflow (von @juliet) verwendet, um festzustellen, ob eine bestimmte Zahl eine Prime ist.

Da ich im Internet mehrere Artikel gelesen habe (ich habe noch kein gutes Buch gekauft, also schäme ich mich), fand ich heraus, dass Sequenzen besser abschneiden als Listen. Deshalb habe ich zuerst eine Funktion erstellt, die eine Folge perfekter Zahlen erzeugt:

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

Die Helperfunction Powshift wird wie folgt implementiert:

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

Ich benutze einen Bit -Shift -Operator, da die Basis aller Leistungsberechnungen von 2 stammt, daher könnte dies ein einfacher Weg sein. Natürlich bin ich immer noch dankbar für die Beiträge zu der Frage, die ich dazu gestellt habe: F# Power -Probleme, die beide Argumente als Bigints> akzeptierenF# Machtprobleme, die beide Argumente als Bigints akzeptieren

Die Funktion, die Julia erstellt (hier geliehen) ist wie folgt:

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

Mit diesem Code dauert es ohne Parallele ungefähr 9 Minuten auf meinem Laptop, um die 9. perfekte Zahl zu finden (die aus 37 Ziffern besteht und mit Wert 31 für den Exponenten zu finden ist). Da mein Laptop eine CPU mit zwei Kernen hat und nur einer bei 50 Prozent (Volllast für einen Kern) läuft, kann ich die Berechnungen beschleunigen, indem ich die Ergebnisse parallel berechnet.

Also habe ich meine PerfectNumber -Funktion wie folgt geändert:

//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);
    }

Um diese Funktion aufzurufen, verwende ich eine kleine Helferfunktion, um sie auszuführen:

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

Wo das Ergebnis der asynchronisierten Berechnung ignoriert wird, da ich es in der PerfectNumbersasync -Funktion zeige.

Der obige Code kompiliert und er wird ausgeführt, verwendet jedoch immer noch nur einen Kern (obwohl er 10 Sekunden schneller ausgeführt wird, wenn die 9. perfekte Zahl berechnet wird). Ich befürchte, dass es etwas mit den Helferfunktionen powshift und iSprime tun muss, aber ich bin nicht sicher. Muss ich den Code dieser Helferfunktionen in den asynchronen Block von PerfectNumbersasync einsetzen? Es verbessert die Lesbarkeit nicht ...

Je mehr ich mit F#spiele, desto mehr lerne ich, diese Sprache zu schätzen, aber wie in diesem Fall brauche ich manchmal einige Experten :).

Vielen Dank im Voraus für das Lesen, ich hoffe nur, dass ich mich ein bisschen klar gemacht habe ...

Robert.

War es hilfreich?

Lösung

@Jeffrey Saxs Kommentar ist definitiv interessant, also habe ich mir einige Zeit genommen, um ein kleines Experiment zu machen. Der Lucas-Lehmer-Test ist wie folgt geschrieben:

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

Mit dem Lucas-Lehmer-Test kann ich die ersten perfekten Zahlen sehr schnell bekommen:

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

Der Lucas-Lehmer-Test trägt dazu bei, die zeitliche Überprüfung der Primzahlen zu verkürzen. Anstatt die Spaltbarkeit von 2^p-1 zu testen, die nimmt O(sqrt(2^p-1)), Wir verwenden den Primalitätstest, der höchstens ist O(p^3). Mit n = 2048, Ich kann die ersten 15 Mersenne -Zahlen in 7,83 Sekunden finden. Die 15. Mersenne -Nummer ist die mit i = 1279 und es besteht aus 770 Ziffern.

Ich habe versucht, parallelisieren runPerfects Verwenden des PSQ -Moduls in F# Powerpack. PSEQ bewahrt die Reihenfolge der ursprünglichen Sequenz nicht bei. Um fair zu sein, habe ich die Ausgangssequenz sortiert. Da der Primalitätstest zwischen den Indizes ein Gleichgewicht zwischen Indizes ist, ist das Ergebnis ziemlich ermutigend:

#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

Bei der gleichen Eingabe dauerte die parallele Version 2,28 Sekunden, was der 3,4-fachen Geschwindigkeit auf meiner Quad-Core-Maschine entspricht. Ich glaube, das Ergebnis könnte weiter verbessert werden, wenn Sie verwenden Parallel.For Konstruktieren Sie den Eingangsbereich vernünftig.

Andere Tipps

Ein kurzer Kommentar zu Geschwindigkeit und Parallelisierbarkeit,

Dein isPrime IS O (SQRT (n)), und jedes hintere Abfolge ist ungefähr 2 x so groß wie das letzte. Daher dauert also ca. 1,5 x so lange, um zu berechnen, was bedeutet, dass die Berechnung der letzten Zahlen viel länger dauert

Ich habe ein paar Hacking mit Tests auf Primalität gemacht, und einige Dinge, die ich gefunden habe, die nützlich sind, sind:

  1. Für Big N (Sie testen Zahlen mit 20 Ziffern), ist die Primdichte tatsächlich ziemlich niedrig, sodass Sie eine Menge Abteilungen durch zusammengesetzte Zahlen durchführen. Ein besserer Ansatz besteht darin, eine PRIME -Tabelle (unter Verwendung eines Siebs) bis zu einer maximalen Grenze (wahrscheinlich durch Speichermenge bestimmt) zu pegeln. Beachten Sie, dass Sie am wahrscheinlichsten Faktoren mit kleinen Zahlen finden. Sobald Sie den Speicher für Ihre Tabelle mehr haben, können Sie den Rest der Zahlen mit Ihrer vorhandenen Funktion mit einem größeren Ausgangspunkt testen.

  2. Ein anderer Ansatz ist die Verwendung mehrerer Threads in der Überprüfung. Zum Beispiel überprüfen Sie derzeit x,x+4,x+6... als Faktoren. Wenn Sie etwas klüger sind, können Sie die Nummer zu 1 Mod 3 in 1 Thread und die Zahlen zu 2 Mod 3 in einem anderen Thread durchführen.

Nr. 2 ist am einfachsten, aber Nr. 1 ist effektiver und bietet Potenzial für den Kontrollfluss ohne OutofMemoryExceptions, die immer interessant sein können

BEARBEITEN:Also habe ich beide Ideen implementiert, es findet fast sofort 2305843008139952128 und findet 2658455991569831744654692615953842176 auf meinem Computer (Quad -Core -AMD 3200). Die meiste Zeit wird es für die Überprüfung von 2^61 für die Prime für die Überprüfung des Besseres für die Überprüfung der Primzahlen: Code hier wahrscheinlich besser sein

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
Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top