Este golf requiere un cálculo factorial que se divida entre múltiples hilos o procesos.

Algunos idiomas hacen que esto sea más fácil de coordinar que otros, por lo que es un lenguaje agnóstico. Se proporciona un código de ejemplo no protegido, pero debe desarrollar su propio algoritmo.

El objetivo del concurso es ver quién puede encontrar el algoritmo factorial multinúcleo más corto (en bytes, no segundos) para calcular N! medido por los votos cuando se cierra el concurso. Debería haber una ventaja multinúcleo, por lo que necesitaremos que funcione para N ~ 10,000. Los votantes deben votar si el autor no proporciona una explicación válida de cómo distribuye el trabajo entre los procesadores / núcleos y votar en base a la concisión del golf.

Por curiosidad, publique algunos números de rendimiento. Puede haber una compensación entre el rendimiento y el puntaje de golf en algún momento, vaya con el golf siempre que cumpla con los requisitos. Me gustaría saber cuándo ocurre esto.

Puede utilizar bibliotecas de gran número de núcleos individuales normalmente disponibles. Por ejemplo, perl generalmente se instala con bigint. Sin embargo, tenga en cuenta que simplemente llamar a una función factorial proporcionada por el sistema normalmente no dividirá el trabajo en múltiples núcleos.

Debe aceptar de STDIN o ARGV la entrada N y la salida a STDOUT el valor de N !. Opcionalmente, puede usar un segundo parámetro de entrada para proporcionar también el número de procesadores / núcleos al programa para que no haga lo que verá a continuación :-) O puede diseñar explícitamente para 2, 4, lo que tenga disponible.

Publicaré mi propio ejemplo de perl Oddball a continuación, presentado previamente en Stack Overflow en Algoritmos factoriales en diferentes idiomas . No es golf. Se presentaron muchos otros ejemplos, muchos de ellos de golf pero muchos no. Debido a las licencias compartidas, siéntase libre de usar el código en cualquier ejemplo en el enlace anterior como punto de partida.

El rendimiento en mi ejemplo es mediocre por varias razones: utiliza demasiados procesos, demasiada conversión de cadenas / bigint. Como dije, es un ejemplo intencionalmente extraño. ¡Calculará 5000! en menos de 10 segundos en una máquina de 4 núcleos aquí. Sin embargo, ¡un dos forro más obvio para / próximo ciclo puede hacer 5000! en uno de los cuatro procesadores en 3.6s.

Definitivamente tendrás que hacerlo mejor que esto:

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

Mi interés en esto es simplemente (1) aliviar el aburrimiento; y (2) aprender algo nuevo. Este no es un problema de tarea o investigación para mí.

¡Buena suerte!

Mathematica

Una función con capacidad paralela:

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

Donde g es Identityo Parallelizedependiendo del tipo de proceso requerido

Para la prueba de tiempo, modificaremos ligeramente la función, por lo que devuelve la hora real del reloj.

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

Y probamos ambos modos (desde 10 ^ 5 hasta 9 * 10 ^ 5): (solo dos núcleos aquí)

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

Resultado:

Haskell: 209 200 198 177 caracteres

176 167 fuente + 33 10 compilador flag

Esta solución es bastante tonta. Aplica el producto en paralelo a un valor de tipo [[Integer]], donde las listas internas tienen como máximo dos elementos. Una vez que la lista externa se reduce a un máximo de 2 listas, la aplanamos y tomamos el producto directamente. Y sí, el verificador de tipo necesita algo anotado con Integer, de lo contrario no se compilará.

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

(Siéntase libre de leer la parte media de fentre concaty scomo "hasta que me guste la longitud")

Parecía que iban a estar bastante bien, ya que parMap de Control.Parallel.Strategies hace que sea bastante fácil explotar esto en múltiples subprocesos. Sin embargo, parece que GHC 7 requiere 33 caracteres en las opciones de línea de comando y variables de entorno para permitir que el tiempo de ejecución enhebrado use múltiples núcleos (que incluí en el total). A menos que me falte algo, lo que definitivamente es posible . ( Actualización : el tiempo de ejecución de GHC roscado parece usar subprocesos N-1, donde N es el número de núcleos, por lo que no es necesario jugar con las opciones de tiempo de ejecución).

Compilar:

ghc -threaded prog.hs

Sin embargo, el tiempo de ejecución fue bastante bueno teniendo en cuenta la cantidad ridícula de evaluaciones paralelas que se generaron y que no compilé con -O2. ¡Por 50000! en una MacBook de doble núcleo, obtengo:

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)

Tiempos totales para algunos valores diferentes, la primera columna es el paralelo golfizado, la segunda es la versión secuencial ingenua:

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

Como referencia, la versión secuencial ingenua es esta (que se compiló con -O2):

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

Ruby - 111 + 56 = 167 caracteres

Este es un script de dos archivos, el archivo 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(:*)

el archivo extra ( f2.rb):

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

Simplemente toma el número de procesos y el número para calcular como argumentos y divide el trabajo en rangos que cada proceso puede calcular individualmente. Luego multiplica los resultados al final.

Esto realmente muestra cuánto más lento es Rubinius para YARV:

Rubinio:

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

Ruby1.9.2:

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

(Tenga en cuenta el extra 0)

Java, 523 519 434 430 429 caracteres

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

Los dos 4 en la línea final son el número de hilos a usar.

50000! probado con el siguiente marco (versión no protegida de la versión original y con un puñado menos de malas prácticas, aunque todavía tiene muchas) da (en mi máquina Linux de 4 núcleos) veces

7685ms
2338ms
1361ms
1093ms
7724ms

Tenga en cuenta que repetí la prueba con un hilo de imparcialidad porque el jit podría haberse calentado.

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 con bigints no es el lenguaje adecuado para jugar al golf (mira lo que tengo que hacer solo para construir las cosas miserables, porque el constructor que lleva mucho tiempo es privado), pero bueno.

Debería ser completamente obvio a partir del código no protegido cómo divide el trabajo: cada subproceso multiplica un módulo de clase de equivalencia por el número de subprocesos. El punto clave es que cada hilo hace aproximadamente la misma cantidad de trabajo.

CSharp - 206 215 caracteres

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

Divide el cálculo con la funcionalidad C # Parallel.For ().

Editar; Olvidé la cerradura

Tiempos de ejecución:

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

Toma Nde entrada estándar.

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}

caracteristicas:

• división de cómputo: iguala en un lado y probabilidades en el otro (cualquier cosa más compleja que eso necesitaría muchos caracteres para equilibrar la carga de cómputo adecuadamente.
• IPC utilizando un archivo anónimo compartido.

Punto de referencia:

• 10000! se imprime en 2.3s bifurcado, 3.4s sin bifurcación
• 100000! se imprime en 5'08.8 bifurcado, 7'07.9 sin bifurcación

Scala ( 345 266 244 232 214 caracteres)

Usando actores:

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

Editar: referencias eliminadas System.currentTimeMillis(), eliminadas a(1).toInt, cambiadas de List.rangeax to y

Editar 2: cambió el whilebucle a a for, cambió el pliegue izquierdo a una función de lista que hace lo mismo, confiando en las conversiones de tipo implícitas para que el BigInttipo de 6 caracteres aparezca solo una vez, cambió println para imprimir

Edición 3: descubrió cómo hacer varias declaraciones en Scala

Edición 4: varias optimizaciones que he aprendido desde que hice esto por primera vez

Versión sin golf:

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

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

}

El factorial de 10 se calcula en 4 núcleos generando 4 listas:

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

que se multiplican en paralelo Hubiera sido un enfoque más simple para distribuir los números:

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

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

Pero la distribución no sería tan buena: los números más pequeños terminarían en la misma lista, los más altos en otra, lo que llevaría a un cálculo más largo en la última lista (para N altas, el último hilo no estaría casi vacío) , pero al menos contienen elementos (N / núcleos) -cores.

Scala en la versión 2.9 contiene colecciones paralelas, que manejan la invocación paralela ellos mismos.

Erlang - 295 caracteres.

Lo primero que he escrito en Erlang, así que no me sorprendería si alguien pudiera reducir a la mitad esto fácilmente:

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

Utiliza el mismo modelo de subprocesos que mi entrada anterior de Ruby: divide el rango en subrangos y multiplica los rangos en hilos separados y luego multiplica los resultados en el hilo principal.

No pude descubrir cómo hacer que el escript funcione, así que solo guarde como f.erly abra erl y ejecute:

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

con sustituciones apropiadas.

Obtuve alrededor de 8 segundos para 50000 en 2 procesos y 10 segundos para 1 proceso, en mi MacBook Air (doble núcleo).

Nota: Acabo de notar que se congela si intenta más procesos que el número para factorizar.