Ten golf wymaga obliczeń czynnikowych podzielonych na wiele wątków lub procesów.

Niektóre języki ułatwiają koordynację niż inne, więc jest to język agnostyczny. Podano przykładowy kod bez golfa, ale należy opracować własny algorytm.

Celem konkursu jest sprawdzenie, kto może wymyślić najkrótszy (w bajtach, nie sekundach) wielordzeniowy algorytm czynnikowy do obliczania N! mierzona liczbą głosów po zakończeniu konkursu. Powinna istnieć wielordzeniowa przewaga, więc będziemy musieli działać dla N ~ 10 000. Głosujący powinni głosować za odrzuceniem, jeśli autor nie dostarczy prawidłowego wyjaśnienia, w jaki sposób rozkłada pracę na procesory / rdzenie i głosuje w oparciu o zwięzłość golfa.

Dla ciekawości proszę zamieścić kilka numerów wyników. W pewnym momencie może wystąpić kompromis między wynikami a golfem, idź z golfem, o ile spełnia on wymagania. Byłbym ciekawy, kiedy to nastąpi.

Możesz użyć normalnie dostępnych pojedynczych bibliotek dużych liczb całkowitych. Na przykład, Perl jest zwykle instalowany z bigintem. Należy jednak pamiętać, że zwykłe wywołanie funkcji systemowej udostępnianej przez system zwykle nie dzieli pracy na wiele rdzeni.

Musisz zaakceptować ze STDIN lub ARGV wejście N i wyjście do STDOUT wartości N !. Opcjonalnie możesz użyć drugiego parametru wejściowego, aby podać liczbę procesorów / rdzeni do programu, więc nie robi to, co zobaczysz poniżej :-) Lub możesz zaprojektować jawnie dla 2, 4, cokolwiek masz dostępne.

Poniżej opublikuję własny przykład perlowego nieparzystego, poprzednio przesłany na Przepełnienie stosu w ramach algorytmów czynnikowych w różnych językach . To nie jest golf. Przedstawiono wiele innych przykładów, wiele z nich to golf, ale wiele nie. Ze względu na licencje podobne do akcji, możesz użyć kodu we wszystkich przykładach w powyższym linku jako punkcie wyjścia.

Wydajność w moim przykładzie jest słaba z wielu powodów: używa zbyt wielu procesów, zbyt dużej konwersji łańcucha / biginta. Jak powiedziałem, jest to celowo nieparzysty przykład. Obliczy 5000! w niecałe 10 sekund na 4-rdzeniowej maszynie tutaj. Jednak bardziej oczywista dwuwarstwowa pętla dla / następnej pętli może zrobić 5000! na jednym z czterech procesorów w 3.6s.

Na pewno będziesz musiał zrobić to lepiej:

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

Moim zainteresowaniem jest po prostu (1) łagodzenie nudy; i (2) uczenie się czegoś nowego. To nie jest dla mnie zadanie domowe ani badawcze.

Powodzenia!

Matematyka

Funkcja równoległa:

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

Gdzie g jest Identitylub Parallelizezależy od wymaganego rodzaju procesu

W przypadku testu synchronizacji nieznacznie zmodyfikujemy funkcję, aby zwracała rzeczywisty czas zegara.

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

Testujemy oba tryby (od 10 ^ 5 do 9 * 10 ^ 5): (tylko dwa jądra tutaj)

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

Wynik:

Haskell: 209 200 198 177 znaków

176 167 źródło + 33 10 flaga kompilatora

To rozwiązanie jest dość głupie. Stosuje produkt równolegle do wartości typu [[Integer]], gdzie wewnętrzne listy mają najwyżej dwa elementy. Gdy lista zewnętrzna spadnie maksymalnie do dwóch list, spłaszczamy ją i zabieramy produkt bezpośrednio. I tak, moduł sprawdzania typu potrzebuje czegoś z dopiskiem Integer, w przeciwnym razie nie zostanie skompilowany.

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

(Zapraszam do przeczytania środkowej części fpomiędzy concati sjako „dopóki nie docenię długości”)

Wyglądało na to, że będą całkiem niezłe, ponieważ parMap od Control.Parallel.Strategies sprawia, że ​​dość łatwo jest rozdzielić je na wiele wątków. Wygląda jednak na to, że GHC 7 wymaga ogromnych 33 znaków w opcjach wiersza poleceń i zmiennych środowiskowych, aby faktycznie umożliwić wątkowemu środowisku wykonawczemu korzystanie z wielu rdzeni (które zawarłem w sumie). Chyba że coś mi umknie, co jest zdecydowanie możliwe . ( Aktualizacja : wątkowe środowisko wykonawcze GHC wydaje się używać wątków N-1, gdzie N jest liczbą rdzeni, więc nie ma potrzeby manipulowania opcjami czasu wykonywania).

Kompilować:

ghc -threaded prog.hs

Środowisko wykonawcze było jednak całkiem dobre, biorąc pod uwagę, że wywołano absurdalną liczbę równoległych ocen i że nie skompilowałem z opcją -O2. Za 50000! na dwurdzeniowym MacBooku otrzymuję:

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)

Całkowity czas dla kilku różnych wartości, pierwsza kolumna jest równoległą do golfa, druga to naiwna sekwencyjna wersja:

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

Dla odniesienia, naiwna sekwencyjna wersja to (skompilowana z -O2):

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

Rubinowy - 111 + 56 = 167 znaków

To jest skrypt dwóch plików, główny plik ( 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(:*)

dodatkowy plik ( f2.rb):

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

Po prostu bierze liczbę procesów i liczbę do obliczenia jako argumenty i dzieli pracę na zakresy, które każdy proces może obliczyć indywidualnie. Następnie mnoży wyniki na końcu.

To naprawdę pokazuje, o ile wolniej Rubinius jest w stosunku do YARV:

Rubinius:

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

Ruby 1.9.2:

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

(Uwaga dodatkowa 0)

Java, 523 519 434 430 429 znaków

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

Dwie 4 w ostatniej linii to liczba wątków do użycia.

50000! przetestowane w następującym frameworku (wersja niegolfowana oryginalnej wersji i garstka mniej złych praktyk - choć wciąż jest ich dużo) daje (na moim 4-rdzeniowym komputerze z Linuksem) czasy

7685ms
2338ms
1361ms
1093ms
7724ms

Zauważ, że powtórzyłem test z jednym wątkiem dla uczciwości, ponieważ jit mógł się rozgrzać.

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 z bigintami nie jest właściwym językiem do gry w golfa (spójrz na to, co muszę zrobić, aby skonstruować nieszczęśliwe rzeczy, ponieważ konstruktor, który zajmuje dużo czasu, jest prywatny), ale hej.

Z nierozwiniętego kodu powinno być całkowicie oczywiste, w jaki sposób dzieli pracę: każdy wątek pomnaża modulo klasy równoważności przez liczbę wątków. Kluczową kwestią jest to, że każdy wątek wykonuje mniej więcej taką samą ilość pracy.

CSharp - 206 215 znaków

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

Dzieli obliczenia za pomocą funkcji C # Parallel.For ().

Edytować; Zapomniałem blokady

Czasy wykonania:

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

Pobiera Nze standardowego wejścia.

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}

Funkcje:

• podział obliczeń: wyrównuje z jednej strony, a szanse z drugiej (cokolwiek bardziej złożonego niż to wymagałoby wielu znaków, aby odpowiednio zrównoważyć obciążenie obliczeń.
• IPC za pomocą udostępnionego anonimowego pliku.

Reper:

• dziesięć tysięcy! jest drukowany z rozwidleniem 2,3s, odkorkowany 3,4s
• 100000! jest wydrukowany w 5'08.8 rozwidlony, 7'07.9 odkorkowany

Scala ( 345 266 244 232 214 znaków)

Za pomocą aktorów:

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

Edytuj - usunięto odniesienia do System.currentTimeMillis(), rozebrano a(1).toInt, zmieniono z List.rangenax to y

Edycja 2 - zmieniłem whilepętlę na a for, zmieniłem lewą zakładkę na funkcję listy, która robi to samo, opierając się na niejawnych konwersjach typu, więc BigInttyp 6 znaków pojawia się tylko raz, zmieniłem println na drukowanie

Edycja 3 - dowiedz się, jak zrobić wiele deklaracji w Scali

Edycja 4 - różne optymalizacje, których nauczyłem się, odkąd to zrobiłem

Wersja bez golfa:

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

bez golfa:

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

}

Silnia 10 jest obliczana na 4 rdzeniach poprzez wygenerowanie 4 list:

• 1 5 9
• 2 6 10
• 3 7
• 48

które są mnożone równolegle. Byłoby prostsze podejście do podziału liczb:

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

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

Ale rozkład nie byłby tak dobry - wszystkie mniejsze liczby kończyłyby się na tej samej liście, najwyższe na innej, co prowadziłoby do dłuższych obliczeń na ostatniej liście (w przypadku wysokich wartości N ostatni wątek nie byłby prawie pusty , ale przynajmniej zawierają elementy rdzeni (N / rdzenie).

Scala w wersji 2.9 zawiera równoległe kolekcje, które same obsługują równoległe wywołanie.

Erlang - 295 znaków.

Pierwsza rzecz, jaką kiedykolwiek napisałem w Erlangu, więc nie zdziwiłbym się, gdyby ktoś mógł z łatwością zmniejszyć o połowę:

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

Używa tego samego modelu wątków, co mój poprzedni wpis Ruby: dzieli zakres na podzakres i mnoży zakresy w osobnych wątkach, a następnie mnoży wyniki z powrotem w głównym wątku.

Nie byłem w stanie dowiedzieć się, jak uruchomić skrypt, więc po prostu zapisz jako f.erli otwórz erl i uruchom:

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

z odpowiednimi zamianami.

Mam około 8 sekund za 50000 w 2 procesach i 10 sekund za 1 proces na moim MacBooku Air (dwurdzeniowy).

Uwaga: Właśnie zauważyłem, że zawiesza się, jeśli spróbujesz wykonać więcej procesów niż liczba, aby dokonać podziału na czynniki.