F# Parallelisierungsproblem bei Berechnung perfekter Zahlen?
-
27-10-2019 - |
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.
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:
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.
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