Esse golfe exige que um cálculo fatorial seja dividido entre vários segmentos ou processos.

Alguns idiomas facilitam a coordenação do que outros, por isso é agnóstico. Um código de exemplo não-fornecido é fornecido, mas você deve desenvolver seu próprio algoritmo.

O objetivo do concurso é ver quem consegue criar o algoritmo fatorial multicore mais curto (em bytes, não em segundos) para calcular o N! medido pelos votos quando o concurso é encerrado. Deveria haver uma vantagem multicore, portanto, exigiremos que funcione para N ~ 10.000. Os eleitores devem votar se o autor não fornecer uma explicação válida de como ele distribui o trabalho entre processadores / núcleos e votar com base na concisão do golfe.

Por curiosidade, publique alguns números de desempenho. Em algum momento, pode haver uma troca entre desempenho e pontuação do golfe, vá com o golfe desde que atenda aos requisitos. Eu ficaria curioso para saber quando isso ocorre.

Você pode usar bibliotecas inteiras grandes de núcleo único normalmente disponíveis. Por exemplo, o perl geralmente é instalado com o bigint. No entanto, observe que simplesmente chamar uma função fatorial fornecida pelo sistema normalmente não dividirá o trabalho em vários núcleos.

Você deve aceitar de STDIN ou ARGV a entrada N e a saída para STDOUT o valor de N !. Opcionalmente, você pode usar um segundo parâmetro de entrada para também fornecer o número de processadores / núcleos para o programa, para que ele não faça o que você verá abaixo :-) Ou você pode criar explicitamente para 2, 4, o que você tiver disponível.

Vou postar meu próprio exemplo de oddball perl abaixo, enviado anteriormente no Stack Overflow em Algoritmos fatoriais em diferentes idiomas . Não é golfe. Vários outros exemplos foram apresentados, muitos deles golfe, mas muitos não. Por causa do licenciamento compartilhado, fique à vontade para usar o código em qualquer exemplo no link acima como ponto de partida.

O desempenho no meu exemplo é pouco claro por várias razões: ele usa muitos processos, muita conversão de string / bigint. Como eu disse, é um exemplo intencionalmente estranho. Ele calculará 5000! em menos de 10 segundos em uma máquina de 4 núcleos aqui. No entanto, um forro mais óbvio de dois for / next loop pode fazer 5000! em um dos quatro processadores no 3.6s.

Você definitivamente terá que fazer melhor do que isso:

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

Meu interesse nisso é simplesmente (1) aliviar o tédio; e (2) aprender algo novo. Este não é um problema de lição de casa ou de pesquisa para mim.

Boa sorte!

Mathematica

Uma função com capacidade paralela:

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

Onde g é Identityou Parallelizedepende do tipo de processo necessário

Para o teste de temporização, modificaremos ligeiramente a função, para que ela retorne a hora do relógio real.

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

E testamos os dois modos (de 10 ^ 5 a 9 * 10 ^ 5): (apenas dois kernels aqui)

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

Resultado:

Haskell: 209 200 198 177 chars

176 167 fonte + 33 10 sinalizador do compilador

Essa solução é bem boba. Aplica o produto em paralelo a um valor do tipo [[Integer]], onde as listas internas têm no máximo dois itens. Quando a lista externa estiver reduzida a, no máximo, 2 listas, a aplainamos e levamos o produto diretamente. E sim, o verificador de tipos precisa de algo anotado com Inteiro, caso contrário, não será compilado.

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

(Sinta-se à vontade para ler a parte do meio fentre concate scomo "até que eu tenha o comprimento")

As coisas pareciam estar indo muito bem, já que o parMap, do Control.Parallel.Strategies, facilita bastante o farm para vários segmentos. No entanto, parece que o GHC 7 requer 33 caracteres impressionantes em opções de linha de comando e variáveis ​​de ambiente para realmente permitir que o tempo de execução encadeado use vários núcleos (que eu incluí no total). A menos que esteja faltando alguma coisa, o que é possível definitivamente é o caso . ( Atualização : o tempo de execução do GHC encadeado parece usar encadeamentos N-1, onde N é o número de núcleos, portanto, não é necessário mexer nas opções de tempo de execução.)

Compilar:

ghc -threaded prog.hs

O tempo de execução, no entanto, foi muito bom, considerando o número ridículo de avaliações paralelas sendo desencadeadas e que eu não compilei com -O2. Para 50000! em um MacBook dual-core, recebo:

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)

Tempo total para alguns valores diferentes, a primeira coluna é o paralelo de golfe, a segunda é a versão seqüencial ingênua:

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

Para referência, a versão seqüencial ingênua é esta (que foi compilada com -O2):

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

Ruby - 111 + 56 = 167 caracteres

Este é um script de dois arquivos, o arquivo 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(:*)

o arquivo extra ( f2.rb):

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

Simplesmente pega o número de processos e o número a serem calculados como args e divide o trabalho em intervalos que cada processo pode calcular individualmente. Em seguida, multiplica os resultados no final.

Isso realmente mostra o quanto o Rubinius é mais lento para o YARV:

Rubinius:

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

Ruby1.9.2:

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

(Observe o extra 0)

Java, 52351944430309 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);}}

Os dois 4s na linha final são o número de threads a serem usados.

50000! testado com a seguinte estrutura (versão simples da versão original e com poucas práticas ruins - embora ainda haja bastante) dá (na minha máquina Linux de quatro núcleos) vezes

7685ms
2338ms
1361ms
1093ms
7724ms

Observe que eu repeti o teste com uma única thread para garantir a justificativa, porque o jit pode ter esquentado.

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 com bigints não é a linguagem certa para o golfe (veja o que tenho que fazer apenas para construir coisas ruins, porque o construtor que demora muito é privado), mas ei.

Deveria ser completamente óbvio, a partir do código não-destruído, como ele divide o trabalho: cada thread multiplica uma classe de equivalência modulo pelo número de threads. O ponto principal é que cada thread realiza aproximadamente a mesma quantidade de trabalho.

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 o cálculo com a funcionalidade C # Parallel.For ().

Editar; Esqueceu o bloqueio

Tempos de execução:

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 Nda entrada padrão.

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}

Recursos:

• divisão de computação: equilibra um lado e as probabilidades do outro (qualquer coisa mais complexa do que isso precisaria de muitos caracteres para equilibrar a carga de cálculo adequadamente.
• IPC usando um arquivo anônimo compartilhado.

Referência:

• 10000! é impresso em 2.3s bifurcado, 3.4s não bifurcado
• 100000! é impresso em 5'08.8 bifurcado, 7'07.9 não bifurcado

Scala ( 345 266 244 232 214 caracteres)

Usando atores:

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 - referências removidas System.currentTimeMillis(), fatoradas a(1).toInt, alteradas de List.rangeparax to y

Editar 2 - alterou o whileloop para a for, alterou a dobra esquerda para uma função de lista que faz a mesma coisa, contando com conversões implícitas de tipo, para que o BigInttipo de 6 caracteres apareça apenas uma vez, alterou println para imprimir

Edit 3 - descobriu como fazer múltiplas declarações no Scala

Edição 4 - várias otimizações que aprendi desde que fiz isso pela primeira vez

Versão não destruída:

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

}

O fatorial de 10 é calculado em 4 núcleos, gerando 4 listas:

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

que são multiplicados em paralelo. Teria havido uma abordagem mais simples para distribuir os números:

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

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

Mas a distribuição não seria tão boa - os números menores terminariam na mesma lista, os mais altos em outro, levando ao cálculo mais longo da última lista (para Ns altos, o último encadeamento não estaria quase vazio , mas pelo menos contém elementos (N / núcleos) -cores.

O Scala na versão 2.9 contém coleções paralelas, que tratam da chamada paralela.

Erlang - 295 caracteres.

A primeira coisa que escrevi em Erlang para não me surpreender se alguém pudesse facilmente reduzir pela metade:

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

Usa o mesmo modelo de encadeamento que minha entrada anterior do Ruby: divide o intervalo em sub-intervalo e multiplica os intervalos juntos em threads separados e multiplica os resultados novamente no thread principal.

Eu não consegui descobrir como fazer o escript funcionar, então salve como f.erle abra erl e execute:

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

com substituições apropriadas.

Consegui cerca de 8s para 50000 em 2 processos e 10s para 1 processo, no meu MacBook Air (núcleo duplo).

Nota: Apenas observe que ele congela se você tentar mais processos do que o número para fatorar.