Ce golf nécessite un calcul factoriel divisé en plusieurs threads ou processus.

Certaines langues facilitent la coordination que d'autres, c'est donc langagnostique. Un exemple de code non golfé est fourni, mais vous devez développer votre propre algorithme.

Le but du concours est de voir qui peut proposer l'algorithme factoriel multicœur le plus court (en octets, pas en secondes) pour calculer N! tel que mesuré par les votes à la fin du concours. Il devrait y avoir un avantage multicœur, nous allons donc exiger qu'il fonctionne pour N ~ 10 000. Les électeurs devraient voter contre si l'auteur ne fournit pas d'explication valable sur la façon dont il répartit le travail entre les processeurs / noyaux et voter en fonction de la concision du golf.

Par curiosité, veuillez publier quelques numéros de performance. Il peut y avoir un compromis performance / score de golf à un moment donné, optez pour le golf tant qu'il répond aux exigences. Je serais curieux de savoir quand cela se produit.

Vous pouvez utiliser des bibliothèques de gros nombres entiers à noyau unique normalement disponibles. Par exemple, perl est généralement installé avec bigint. Cependant, notez que le simple fait d'appeler une fonction factorielle fournie par le système ne divisera normalement pas le travail sur plusieurs cœurs.

Vous devez accepter de STDIN ou ARGV l'entrée N et la sortie vers STDOUT la valeur N !. Vous pouvez éventuellement utiliser un deuxième paramètre d'entrée pour fournir également le nombre de processeurs / cœurs au programme afin qu'il ne fasse pas ce que vous verrez ci-dessous :-) Ou vous pouvez concevoir explicitement pour 2, 4, tout ce dont vous disposez.

Je posterai mon propre exemple de perl oddball ci-dessous, précédemment soumis sur Stack Overflow sous Algorithmes factoriels dans différentes langues . Ce n'est pas du golf. De nombreux autres exemples ont été soumis, dont beaucoup de golf mais pas beaucoup. En raison de la licence de partage, n'hésitez pas à utiliser le code dans tous les exemples du lien ci-dessus comme point de départ.

La performance dans mon exemple est terne pour un certain nombre de raisons: elle utilise trop de processus, trop de conversion chaîne / bigint. Comme je l'ai dit, c'est un exemple intentionnellement étrange. Il en calculera 5000! en moins de 10 secondes sur une machine à 4 cœurs ici. Cependant, une doublure plus évidente pour la boucle suivante / peut faire 5000! sur l'un des quatre processeurs en 3.6s.

Vous devrez certainement faire mieux que cela:

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

Mon intérêt pour cela est simplement (1) de soulager l'ennui; et (2) apprendre quelque chose de nouveau. Ce n'est pas un problème de devoirs ou de recherche pour moi.

Bonne chance!

Mathematica

Une fonction parallèle:

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

Où g est Identityou Parallelizeselon le type de processus requis

Pour le test de synchronisation, nous allons légèrement modifier la fonction, afin qu'elle renvoie l'heure réelle de l'horloge.

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

Et nous testons les deux modes (de 10 ^ 5 à 9 * 10 ^ 5): (seulement deux noyaux ici)

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

Résultat:

Haskell: 209 200 198 177 caractères

176 167 source + 33 10 drapeau du compilateur

Cette solution est assez idiote. Il applique le produit en parallèle à une valeur de type [[Integer]], où les listes internes comportent au maximum deux éléments. Une fois que la liste externe est réduite à 2 listes au maximum, nous l'aplatissons et prenons le produit directement. Et oui, le vérificateur de type a besoin de quelque chose d'annoté avec Integer, sinon il ne compilera pas.

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

(N'hésitez pas à lire la partie médiane fentre concatet scomme "jusqu'à ce que j'aime la longueur")

Les choses semblaient être très bonnes, car le parMap de Control.Parallel.Strategies facilite la mise à jour de ces données sur plusieurs threads. Cependant, il semble que GHC 7 nécessite 33 caractères dans les options de ligne de commande et les variables d'environnement pour permettre au runtime threadé d'utiliser plusieurs cœurs (que j'ai inclus dans le total). A moins que je manque quelque chose, ce qui est certainement possible . ( Mise à jour : le runtime GHC threadé semble utiliser N-1 threads, où N est le nombre de cœurs, donc pas besoin de manipuler les options d'exécution.)

Compiler:

ghc -threaded prog.hs

Le temps d'exécution, cependant, était plutôt bon compte tenu du nombre ridicule d'évaluations parallèles déclenchées et que je n'ai pas compilé avec -O2. Pour 50000! sur un MacBook double cœur, j'obtiens:

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)

Temps total pour quelques valeurs différentes, la première colonne est le parallèle joué, la seconde est la version séquentielle naïve:

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

Pour référence, la version séquentielle naïve est celle-ci (qui a été compilée avec -O2):

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

Rubis - 111 + 56 = 167 caractères

Il s'agit d'un script à deux fichiers, le fichier principal ( 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(:*)

le fichier supplémentaire ( f2.rb):

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

Prend simplement le nombre de processus et le nombre à calculer sous forme d'arguments et divise le travail en plages que chaque processus peut calculer individuellement. Multiplie ensuite les résultats à la fin.

Cela montre vraiment à quel point Rubinius est plus lent pour YARV:

Rubinius:

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

Ruby1.9.2:

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

(Notez l'extra 0)

Java, 523 519 434 430 429 caractères

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

Les deux 4 de la dernière ligne correspondent au nombre de threads à utiliser.

50000! testé avec le framework suivant (version non golfée de la version originale et avec un peu moins de mauvaises pratiques - bien qu'il en ait encore beaucoup) donne (sur ma machine Linux à 4 cœurs) des temps

7685ms
2338ms
1361ms
1093ms
7724ms

Notez que j'ai répété le test avec un fil pour l'équité car le jit s'est peut-être réchauffé.

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 avec bigints n'est pas le bon langage pour jouer au golf (regardez ce que je dois faire juste pour construire les choses misérables, car le constructeur qui prend beaucoup de temps est privé), mais bon.

Il devrait être complètement évident d'après le code non golfé comment il décompose le travail: chaque thread multiplie une classe d'équivalence modulo le nombre de threads. Le point clé est que chaque thread effectue à peu près la même quantité de travail.

CSharp - 206 215 caractères

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

Divise le calcul avec la fonctionnalité C # Parallel.For ().

Éditer; Verrou oublié

Délais d'exécution:

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

Prend Nde l'entrée standard.

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}

Fonctionnalités:

• partage de calcul: égal d'un côté et cotes de l'autre (quelque chose de plus complexe que cela nécessiterait beaucoup de caractères pour équilibrer la charge de calcul de manière appropriée.
• IPC utilisant un fichier anonyme partagé.

Référence:

• 10000! est imprimé en 2.3s fourchu, 3.4s inaperçu
• 100000! est imprimé en 5'08.8 fourchu, 7'07.9 sans encart

Scala ( 345 266 244 232 214 caractères)

Utilisation d'acteurs:

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

Modifier - suppression des références à System.currentTimeMillis(), factorisé a(1).toInt, changé de List.rangeàx to y

Edit 2 - a changé la whileboucle en a for, a changé le pli gauche en une fonction de liste qui fait la même chose, en s'appuyant sur des conversions de type implicites de sorte que le BigInttype à 6 caractères n'apparaît qu'une seule fois, a changé println pour imprimer

Edit 3 - a découvert comment faire plusieurs déclarations dans Scala

Edit 4 - diverses optimisations que j'ai apprises depuis que j'ai fait cela

Version non golfée:

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)(_*_)))(_*_))}

non golfé:

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) (_ * _)))(_ * _))

}

La factorielle de 10 est calculée sur 4 cœurs en générant 4 listes:

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

qui se multiplient en parallèle. Il y aurait eu une approche plus simple pour distribuer les chiffres:

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

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

Mais la distribution ne serait pas si bonne - les plus petits nombres finiraient tous dans la même liste, le plus élevé dans une autre, conduisant au calcul plus long dans la dernière liste (pour les N élevés, le dernier thread ne serait pas presque vide , mais contiennent au moins des éléments (N / cores) -cores.

Scala dans la version 2.9 contient des collections parallèles, qui gèrent elles-mêmes l'invocation parallèle.

Erlang - 295 caractères.

Première chose que j'ai jamais écrite à Erlang, donc je ne serais pas surpris si quelqu'un pouvait facilement diviser par deux ceci:

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

Utilise le même modèle de thread que mon entrée Ruby précédente: divise la plage en sous-plage et multiplie les plages ensemble dans des threads séparés, puis multiplie les résultats dans le thread principal.

Je n'ai pas réussi à comprendre comment faire fonctionner escript, alors enregistrez simplement f.erlet ouvrez erl et exécutez:

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

avec des substitutions appropriées.

J'ai obtenu environ 8 secondes pour 50000 en 2 processus et 10 secondes pour 1 processus, sur mon MacBook Air (double cœur).

Remarque: je viens de remarquer qu'il se fige si vous essayez plus de processus que le nombre à factoriser.