Für dieses Golfspiel muss eine Fakultätsberechnung auf mehrere Threads oder Prozesse aufgeteilt werden.

Einige Sprachen erleichtern die Koordinierung als andere, daher ist es lang agnostisch. Ungolfed-Beispielcode wird bereitgestellt, Sie sollten jedoch Ihren eigenen Algorithmus entwickeln.

Das Ziel des Wettbewerbs ist es, herauszufinden, wer den kürzesten (in Bytes, nicht in Sekunden) mehrkernigen faktoriellen Algorithmus zur Berechnung von N finden kann! gemessen in Stimmen, wenn der Wettbewerb endet. Es sollte einen Multicore-Vorteil geben, daher wird vorausgesetzt, dass er für N ~ 10.000 funktioniert. Die Wähler sollten abstimmen, wenn der Autor keine gültige Erklärung dafür abgibt, wie er die Arbeit unter den Prozessoren / Kernen verteilt, und auf der Grundlage der Golfpräzision abstimmen.

Bitte geben Sie aus Neugierde einige Leistungszahlen an. Es kann irgendwann zu einem Kompromiss zwischen Leistung und Golf-Score kommen. Spielen Sie Golf, solange dies den Anforderungen entspricht. Ich wäre gespannt, wann dies passiert.

Sie können normal verfügbare Single-Core-Big-Integer-Bibliotheken verwenden. Zum Beispiel wird Perl normalerweise mit bigint installiert. Beachten Sie jedoch, dass das Aufrufen einer vom System bereitgestellten Fakultätsfunktion die Arbeit normalerweise nicht auf mehrere Kerne aufteilt.

Sie müssen den Eingang N von STDIN oder ARGV akzeptieren und den Wert von N! An STDOUT ausgeben. Sie können optional einen zweiten Eingabeparameter verwenden, um auch die Anzahl der Prozessoren / Kerne für das Programm anzugeben, damit es nicht das tut, was Sie unten sehen werden :-) Oder Sie entwerfen explizit für 2, 4, was auch immer verfügbar ist.

Ich werde mein eigenes Oddball-Perl-Beispiel veröffentlichen, das zuvor für Stack Overflow unter Faktorielle Algorithmen in verschiedenen Sprachen eingereicht wurde . Es ist kein Golf. Zahlreiche andere Beispiele wurden eingereicht, viele davon Golf, aber viele nicht. Verwenden Sie den Code in den Beispielen im obigen Link als Ausgangspunkt, da es sich um Lizenzen handelt, die sich an Freigaben orientieren.

Die Leistung in meinem Beispiel ist aus mehreren Gründen mangelhaft: Sie verwendet zu viele Prozesse und zu viel String / Bigint-Konvertierung. Wie gesagt, es ist ein absichtlich komisches Beispiel. Es wird 5000 berechnen! in weniger als 10 Sekunden auf einem 4-Kern-Rechner hier. Ein offensichtlicherer Zwei-Liner für die nächste Schleife kann jedoch 5000 leisten! auf einem der vier Prozessoren in 3.6s.

Du musst es definitiv besser machen:

#!/usr/bin/perl -w                                                              
use strict;
use bigint;
die "usage: f.perl N (outputs N!)" unless ($ARGV[0] > 1);
print STDOUT &main::rangeProduct(1,$ARGV[0])."\n";
sub main::rangeProduct {
    my($l, $h) = @_;
    return $l    if ($l==$h);
    return $l*$h if ($l==($h-1));
    # arghhh - multiplying more than 2 numbers at a time is too much work       
    # find the midpoint and split the work up :-)                               
    my $m = int(($h+$l)/2);
    my $pid = open(my $KID, "-|");
      if ($pid){ # parent                                                       
        my $X = &main::rangeProduct($l,$m);
        my $Y = <$KID>;
        chomp($Y);
        close($KID);
        die "kid failed" unless defined $Y;
        return $X*$Y;
      } else {
        # kid                                                                   
        print STDOUT &main::rangeProduct($m+1,$h)."\n";
        exit(0);
    }
}

Mein Interesse daran ist einfach (1) Langeweile zu lindern; und (2) etwas Neues lernen. Dies ist für mich kein Problem mit Hausaufgaben oder Nachforschungen.

Viel Glück!

Mathematica

Eine parallele Funktion:

 f[n_, g_] := g[Product[N@i, {i, 1, n, 2}] Product[N@i, {i, 2, n, 2}]]

Wo g ist Identityoder Parallelizeje nach Art des Prozesses erforderlich

Für den Timing-Test werden wir die Funktion geringfügig modifizieren, sodass die tatsächliche Uhrzeit zurückgegeben wird.

f[n_, g_] := First@AbsoluteTiming[g[Product[N@i,{i,1,n,2}] Product[N@i,{i,2,n,2}]]]

Und wir testen beide Modi (von 10 ^ 5 bis 9 * 10 ^ 5): (nur zwei Kernel hier)

ListLinePlot[{Table[f[i, Identity],    {i, 100000, 900000, 100000}], 
              Table[f[i, Parallelize], {i, 100000, 900000, 100000}]}]   

Ergebnis:

Haskell: 209 200 198 177 Zeichen

176 167 Quelle + 33 10 Compiler-Flag

Diese Lösung ist ziemlich dumm. Es wendet product parallel zu einem Wert vom Typ an [[Integer]], bei dem die inneren Listen höchstens zwei Elemente lang sind. Sobald die äußere Liste auf höchstens 2 Listen beschränkt ist, reduzieren wir sie und nehmen das Produkt direkt. Und ja, die Typprüfung benötigt einen Integer-Kommentar, sonst wird sie nicht kompiliert.

import Control.Parallel.Strategies
s(x:y:z)=[[x,y::Integer]]++s z;s x=[x]
p=product
f n=p$concat$(until((<3).length)$s.parMap rseq p)$s[1..n]
main=interact$show.f.read

(Fühlen Sie sich frei, den mittleren Teil von fzwischen concatund sals "bis ich das Herz der Länge" zu lesen )

Die Dinge schienen ziemlich gut zu werden, da parMap von Control.Parallel.Strategies es ziemlich einfach macht, dies auf mehrere Threads zu übertragen. Es sieht jedoch so aus, als ob GHC 7 satte 33 Zeichen in Befehlszeilenoptionen und Umgebungsvariablen erfordert, damit die Thread-Laufzeit tatsächlich mehrere Kerne verwenden kann (was ich in die Gesamtsumme aufgenommen habe). Es sei denn , ich bin etwas fehlt, das ist möglich , auf jeden Fall der Fall . ( Update : Die Thread-GHC-Laufzeit verwendet offenbar N-1-Threads, wobei N die Anzahl der Kerne ist, sodass Sie nicht mit den Laufzeitoptionen herumspielen müssen.)

Kompilieren:

ghc -threaded prog.hs

Die Laufzeit war jedoch ziemlich gut, wenn man bedenkt, dass eine lächerliche Anzahl paralleler Auswertungen ausgelöst wurde und ich nicht mit -O2 kompiliert habe. Für 50000! Auf einem Dual-Core-MacBook bekomme ich:

SPARKS: 50020 (29020 converted, 1925 pruned)

INIT  time    0.00s  (  0.00s elapsed)
MUT   time    0.20s  (  0.19s elapsed)
GC    time    0.12s  (  0.07s elapsed)
EXIT  time    0.00s  (  0.00s elapsed)
Total time    0.31s  (  0.27s elapsed)

Gesamtzeiten für einige verschiedene Werte, die erste Spalte ist die Golfparallele, die zweite ist die naive sequentielle Version:

          Parallel   Sequential
 10000!      0.03s        0.04s
 50000!      0.27s        0.78s
100000!      0.74s        3.08s
500000!      7.04s       86.51s

Als Referenz ist die naive sequentielle Version diese (die mit -O2 kompiliert wurde):

factorial :: Integer -> Integer
factorial n = product [1..n]
main = interact $ show.factorial.read

Ruby - 111 + 56 = 167 Zeichen

Dies ist ein Skript mit zwei Dateien, die Hauptdatei ( fact.rb):

c,n=*$*.map(&:to_i)
p=(0...c).map{|k|IO.popen("ruby f2.rb #{k} #{c} #{n}")}
p p.map{|l|l.read.to_i}.inject(:*)

die extra Datei ( f2.rb):

c,h,n=*$*.map(&:to_i)
p (c*n/h+1..(c+1)*n/h).inject(:*)

Nimmt einfach die Anzahl der Prozesse und die zu berechnende Anzahl als Argumente und teilt die Arbeit in Bereiche auf, die jeder Prozess einzeln berechnen kann. Dann multipliziert man die Ergebnisse am Ende.

Dies zeigt wirklich, wie viel langsamer Rubinius zu YARV ist:

Rubinius:

time ruby fact.rb 5 5000 #=> 61.84s

Ruby1.9.2:

time ruby fact.rb 5 50000 #=> 3.09s

(Beachten Sie das Extra 0)

Java, 523 519 434 430 429 Zeichen

import java.math.*;public class G extends Thread{BigInteger o,i,r=BigInteger.ONE,h;G g;G(BigInteger O,int
I,int n){o=O;i=new BigInteger(""+I);if(n>1)g=new G(O.subtract(r),I,n-1);h=n==I?i:r;start();}public void
run(){while(o.signum()>0){r=r.multiply(o);o=o.subtract(i);}try{g.join();r=r.multiply(g.r);}catch(Exception
e){}if(h==i)System.out.println(r);}public static void main(String[] args){new G(new BigInteger(args[0]),4,4);}}

Die beiden 4en in der letzten Zeile geben die Anzahl der zu verwendenden Threads an.

50000! Getestet mit dem folgenden Framework (ungolfed version der Originalversion und mit ein paar weniger Bad Practices - obwohl es immer noch reichlich ist) ergibt das (auf meinem 4-Core Linux Rechner) mal

7685ms
2338ms
1361ms
1093ms
7724ms

Beachten Sie, dass ich den Test aus Fairnessgründen mit einem Thread wiederholt habe, da sich das JIT möglicherweise erwärmt hat.

import java.math.*;

public class ForkingFactorials extends Thread { // Bad practice!
    private BigInteger off, inc;
    private volatile BigInteger res;

    private ForkingFactorials(int off, int inc) {
        this.off = new BigInteger(Integer.toString(off));
        this.inc = new BigInteger(Integer.toString(inc));
    }

    public void run() {
        BigInteger p = new BigInteger("1");
        while (off.signum() > 0) {
            p = p.multiply(off);
            off = off.subtract(inc);
        }
        res = p;
    }

    public static void main(String[] args) throws Exception {
        int n = Integer.parseInt(args[0]);
        System.out.println(f(n, 1));
        System.out.println(f(n, 2));
        System.out.println(f(n, 3));
        System.out.println(f(n, 4));
        System.out.println(f(n, 1));
    }

    private static BigInteger f(int n, int numThreads) throws Exception {
        long now = System.currentTimeMillis();
        ForkingFactorials[] th = new ForkingFactorials[numThreads];
        for (int i = 0; i < n && i < numThreads; i++) {
            th[i] = new ForkingFactorials(n-i, numThreads);
            th[i].start();
        }
        BigInteger f = new BigInteger("1");
        for (int i = 0; i < n && i < numThreads; i++) {
            th[i].join();
            f = f.multiply(th[i].res);
        }
        long t = System.currentTimeMillis() - now;
        System.err.println("Took " + t + "ms");
        return f;
    }
}

Java mit Bigint ist nicht die richtige Sprache zum Golfen (schau dir an, was ich tun muss, um die elenden Dinge zu konstruieren, denn der Konstruktor, der lange dauert, ist privat), aber hey.

Aus dem ungolfed Code sollte völlig ersichtlich sein, wie sich die Arbeit aufteilt: Jeder Thread multipliziert eine Äquivalenzklasse mit der Anzahl der Threads. Der entscheidende Punkt ist, dass jeder Thread ungefähr den gleichen Arbeitsaufwand leistet.

CSharp - 206 215 Zeichen

using System;using System.Numerics;using System.Threading.Tasks;class a{static void Main(){var n=int.Parse(Console.ReadLine());var r=new BigInteger(1);Parallel.For(1,n+1,i=>{lock(this)r*=i;});Console.WriteLine(r);}}

Teilt die Berechnung mit der Funktionalität C # Parallel.For () auf.

Bearbeiten; Passwortsperre

Ausführungszeiten:

n = 10,000, time: 59ms.
n = 20,000, time: 50ms.
n = 30,000, time: 38ms.
n = 40,000, time: 100ms.
n = 50,000, time: 139ms.
n = 60,000, time: 164ms.
n = 70,000, time: 222ms.
n = 80,000, time: 266ms.
n = 90,000, time: 401ms.
n = 100,000, time: 424ms.
n = 110,000, time: 501ms.
n = 120,000, time: 583ms.
n = 130,000, time: 659ms.
n = 140,000, time: 832ms.
n = 150,000, time: 1143ms.
n = 160,000, time: 804ms.
n = 170,000, time: 653ms.
n = 180,000, time: 1031ms.
n = 190,000, time: 1034ms.
n = 200,000, time: 1765ms.
n = 210,000, time: 1059ms.
n = 220,000, time: 1214ms.
n = 230,000, time: 1362ms.
n = 240,000, time: 2737ms.
n = 250,000, time: 1761ms.
n = 260,000, time: 1823ms.
n = 270,000, time: 3357ms.
n = 280,000, time: 2110ms.

Perl, 140

Übernimmt Nvon der Standardeingabe.

use bigint;$m=<>;open A,'>',
undef;$i=$p=fork&&1;$n=++$i;
{$i+=2;$n*=$i,redo if$i<=$m}
if($p){wait;seek A,0,0;$_=<A
>;print$n*$_}else{print A$n}

Eigenschaften:

• Rechenteilung: Gleicht auf der einen Seite und Gewinnchancen auf der anderen Seite aus (alles, was komplexer ist, würde eine Menge Zeichen erfordern, um die Rechenlast angemessen auszugleichen.
• IPC mit einer freigegebenen anonymen Datei.

Benchmark:

• 10000! wird in 2.3s gegabelt, 3.4s ungegabelt gedruckt
• 100000! ist gedruckt in 5'08.8 gegabelt, 7'07.9 ungegabelt

Scala ( 345 266 244 232 214 Zeichen)

Schauspieler verwenden:

object F extends App{import actors.Actor._;var(t,c,r)=(args(1).toInt,self,1:BigInt);val n=args(0).toInt min t;for(i<-0 to n-1)actor{c!(i*t/n+1 to(i+1)*t/n).product};for(i<-1 to n)receive{case m:Int=>r*=m};print(r)}

Bearbeiten - Verweise auf entfernt System.currentTimeMillis(), ausgeklammert a(1).toInt, geändert von List.rangenachx to y

Edit 2 - Änderte die whileSchleife in a for, änderte die linke Falte in eine BigIntListenfunktion, die dasselbe tut und sich auf implizite Typkonvertierungen stützt, sodass der 6- Zeichen-Typ nur einmal erscheint, und änderte println zu print

Edit 3 - Erfahren Sie, wie Sie mehrere Deklarationen in Scala erstellen können

Edit 4 - verschiedene Optimierungen, die ich gelernt habe, seit ich das erste Mal gemacht habe

Ungolfed-Version:

import actors.Actor._
object ForkingFactorials extends App
{
    var (target,caller,result)=(args(1).toInt,self,1:BigInt)
    val numthreads=args(0).toInt min target
    for(i<-0 to numthreads-1)
        actor
        {
            caller ! (i*target/numthreads+1 to(i+1)*target/numthreads+1).product
        }
    for(i<-1 to numthreads)
        receive
        {
            case m:Int=>result*=m
        }
    print(result)
}

Scala-2.9.0 170

object P extends App{
def d(n:Int,c:Int)=(for(i<-1 to c)yield(i to n by c)).par
println((BigInt(1)/: d(args(0).toInt,args(1).toInt).map(x=>(BigInt(1)/: x)(_*_)))(_*_))}

ungolfed:

object ParallelFactorials extends App
{
  def distribute (n: Int, cores: Int) = {
    val factorgroup = for (i <- 1 to cores) 
      yield (i to n by cores)
    factorgroup.par
  }

  val parallellist = distribute (args(0).toInt, args(1).toInt)

  println ((BigInt (1) /: parallellist.map (x => (BigInt(1) /: x) (_ * _)))(_ * _))

}

Die Fakultät von 10 wird für 4 Kerne berechnet, indem 4 Listen generiert werden:

• 1 5 9
• 2 6 10
• 3 7
• 4 8

die parallel multipliziert werden. Es hätte einen einfacheren Ansatz für die Verteilung der Zahlen gegeben:

 (1 to n).sliding ((n/cores), (n/cores) 

• 1 2 3
• 4 5 6
• 7 8 9
• 10

Aber die Verteilung wäre nicht so gut - die kleineren Zahlen würden alle in derselben Liste enden, die höchsten in einer anderen, was zu einer längeren Berechnung in der letzten Liste führen würde (für hohe Ns wäre der letzte Thread nicht fast leer , enthalten aber mindestens (N / Kerne) -Kernelemente.

Scala in Version 2.9 enthält parallele Sammlungen, die den parallelen Aufruf selbst handhaben.

Erlang - 295 Zeichen.

Das erste, was ich jemals in Erlang geschrieben habe, also wäre ich nicht überrascht, wenn jemand dies leicht halbieren könnte:

-module(f).
-export([m/2,f/4]).
m(N,C)->g(N,C,C,[]).
r([],B)->B;
r(A,B)->receive{F,V}->r(lists:delete(F,A),V*B)end.
s(H,L)->spawn(f,f,[self(),H,L,1]).
g(N,1,H,A)->r([s(N div H,1)|A],1);
g(N,C,H,A)->g(N,C-1,H,[s(N*C div H,N*(C-1) div H)|A]).
f(P,H,H,A)->P!{self(),A};
f(P,H,L,A)->f(P,H-1,L,A*H).

Verwendet dasselbe Threading-Modell wie mein früherer Ruby-Eintrag: Teilt den Bereich in Unterbereiche auf und multipliziert die Bereiche in separaten Threads und multipliziert dann die Ergebnisse zurück in den Haupt-Thread.

Ich konnte nicht herausfinden, wie ich escript zum Laufen bringen kann, also speichere f.erlund öffne erl und starte:

c(f).
f:m(NUM_TO_CALC, NUM_OF_PROCESSES).

mit entsprechenden Substitutionen.

Auf meinem MacBook Air (Dual-Core) wurden für 50000 in 2 Prozessen ungefähr 8 Sekunden und für 1 Prozess 10 Sekunden erreicht.

Hinweis: Nur bemerkt, dass es einfriert, wenn Sie versuchen, mehr Prozesse als die Zahl zu faktorisieren.