Golf ini membutuhkan perhitungan faktorial untuk dibagi di antara beberapa utas atau proses.

Beberapa bahasa membuat ini lebih mudah untuk dikoordinasikan daripada yang lain, jadi itu adalah bahasa agnostik. Kode contoh tidak disediakan disediakan, tetapi Anda harus mengembangkan algoritma Anda sendiri.

Tujuan dari kontes ini adalah untuk melihat siapa yang dapat menghasilkan algoritma faktorial multicore terpendek (dalam byte, bukan detik) untuk menghitung N! yang diukur dengan suara ketika kontes ditutup. Seharusnya ada keuntungan multicore, jadi kami akan mengharuskan itu harus bekerja untuk N ~ 10.000. Pemilih harus memilih jika penulis gagal memberikan penjelasan yang valid tentang bagaimana ia menyebar pekerjaan di antara prosesor / core dan memilih berdasarkan pada keringkasan golf.

Untuk rasa ingin tahu, silakan kirim beberapa angka kinerja. Mungkin ada tradeoff kinerja vs golf di beberapa titik, pergi dengan golf selama memenuhi persyaratan. Saya ingin tahu ketika ini terjadi.

Anda dapat menggunakan perpustakaan integer tunggal inti tunggal yang tersedia secara normal. Misalnya, perl biasanya dipasang dengan bigint. Namun, perhatikan bahwa hanya memanggil sistem yang disediakan fungsi faktorial biasanya tidak akan membagi pekerjaan menjadi beberapa core.

Anda harus menerima dari STDIN atau ARGV input N dan output untuk STDOUT nilai N !. Anda secara opsional dapat menggunakan parameter input ke-2 untuk juga menyediakan jumlah prosesor / inti untuk program sehingga tidak melakukan apa yang akan Anda lihat di bawah :-) Atau Anda dapat mendesain secara eksplisit untuk 2, 4, apa pun yang Anda miliki.

Saya akan memposting contoh perl aneh saya sendiri di bawah ini, yang sebelumnya dikirimkan pada Stack Overflow di bawah Algoritma Faktorial dalam Berbagai Bahasa . Ini bukan golf. Banyak contoh lain diajukan, banyak dari mereka golf tetapi banyak yang tidak. Karena perizinan yang serupa, jangan ragu untuk menggunakan kode dalam contoh apa pun di tautan di atas sebagai titik awal.

Kinerja dalam contoh saya kurang bagus karena sejumlah alasan: ia menggunakan terlalu banyak proses, terlalu banyak konversi string / bigint. Seperti yang saya katakan itu adalah contoh yang sengaja aneh. Ini akan menghitung 5.000! di bawah 10 detik pada mesin 4 inti di sini. Namun, dua liner yang lebih jelas untuk / loop berikutnya dapat melakukan 5000! pada salah satu dari empat prosesor dalam 3.6s.

Anda pasti harus melakukan yang lebih baik dari ini:

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

Ketertarikan saya pada ini hanyalah (1) mengurangi kebosanan; dan (2) mempelajari sesuatu yang baru. Ini bukan masalah pekerjaan rumah atau penelitian bagi saya.

Semoga berhasil!

Mathematica

Fungsi paralel-mampu:

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

Di mana g adalah Identityatau Parallelizetergantung pada jenis proses yang diperlukan

Untuk tes pengaturan waktu, kami akan sedikit memodifikasi fungsi, sehingga mengembalikan waktu jam nyata.

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

Dan kami menguji kedua mode (dari 10 ^ 5 hingga 9 * 10 ^ 5): (hanya dua kernel di sini)

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

Hasil:

Haskell: 209 200 198 177 karakter

176 167 sumber + 33 10 flag kompiler

Solusi ini sangat konyol. Ini berlaku produk secara paralel dengan nilai jenis [[Integer]], di mana daftar bagian dalam paling banyak dua item. Setelah daftar luar turun ke paling banyak 2 daftar, kami meratakannya dan mengambil produk secara langsung. Dan ya, pemeriksa tipe membutuhkan sesuatu yang dijelaskan dengan Integer, jika tidak, ia tidak akan dikompilasi.

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

(Jangan ragu untuk membaca bagian tengah dari fantara concatdan ssebagai "sampai aku hati panjangnya")

Hal-hal tampak seperti mereka akan menjadi cukup baik sejak parMap dari Control.Parallel.Strategies membuatnya cukup mudah untuk mengolah ini ke beberapa utas. Namun, sepertinya GHC 7 membutuhkan 33 karakter kekalahan dalam opsi baris perintah dan lingkungan vars untuk benar-benar mengaktifkan runtime berulir untuk menggunakan beberapa core (yang saya sertakan dalam total). Kecuali saya kehilangan sesuatu, yang mungkin terjadi . ( Pembaruan : runtime GHC ulir tampaknya menggunakan utas N-1, dengan N adalah jumlah inti, jadi tidak perlu mengutak-atik opsi run time.)

Untuk mengkompilasi:

ghc -threaded prog.hs

Runtime, bagaimanapun, cukup bagus mengingat jumlah evaluasi paralel yang dipicu dan saya tidak mengkompilasi dengan -O2. Untuk 50000! pada MacBook dual-core, saya mendapatkan:

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)

Total waktu untuk beberapa nilai yang berbeda, kolom pertama adalah paralel golf, yang kedua adalah versi sekuensial naif:

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

Sebagai referensi, versi sekuensial naif adalah ini (yang dikompilasi dengan -O2):

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

Ruby - 111 + 56 = 167 karakter

Ini adalah skrip dua file, file utama ( 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(:*)

file tambahan ( f2.rb):

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

Cukup mengambil jumlah proses dan angka untuk menghitung sebagai arg dan membagi pekerjaan menjadi rentang yang setiap proses dapat menghitung secara individual. Kemudian gandakan hasilnya di akhir.

Ini benar-benar menunjukkan seberapa lambat Rubinius bagi YARV:

Rubinius:

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

Ruby1.9.2:

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

(Perhatikan ekstra 0)

Java, 523 519 434 430 429 karakter

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

Dua 4s di baris terakhir adalah jumlah utas yang digunakan.

50000! diuji dengan kerangka kerja berikut (versi ungolfed dari versi asli dan dengan beberapa praktik buruk lebih sedikit - meskipun masih banyak) memberikan (pada mesin Linux 4-core saya) kali

7685ms
2338ms
1361ms
1093ms
7724ms

Perhatikan bahwa saya mengulangi pengujian dengan satu utas untuk keadilan karena jit mungkin telah memanas.

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 dengan bigints bukan bahasa yang tepat untuk bermain golf (lihat apa yang harus saya lakukan hanya untuk membangun hal-hal yang buruk, karena konstruktor yang memakan waktu lama bersifat pribadi), tapi hei.

Seharusnya benar-benar jelas dari kode yang tidak di-serigala bagaimana memecah pekerjaan: setiap thread mengalikan kelas kesetaraan modulo jumlah thread. Poin kuncinya adalah bahwa setiap utas melakukan kurang lebih jumlah pekerjaan yang sama.

CSharp - 206 215 karakter

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

Pisahkan perhitungan dengan fungsionalitas C # Parallel.For ().

Edit; Lupa kunci

Waktu eksekusi:

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

Diambil Ndari input standar.

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}

Fitur:

• split komputasi: genap di satu sisi dan peluang di sisi lain (apa pun yang lebih kompleks dari itu akan membutuhkan banyak karakter untuk menyeimbangkan beban perhitungan dengan tepat.
• IPC menggunakan file anonim bersama.

Benchmark:

• 10000! dicetak dalam bentuk 2.3s forked, 3.4s unforked
• 100000! dicetak dalam 5'08.8 bercabang, 7'07.9 tanpa hiasan

Scala ( 345 266 244 232 214 karakter)

Menggunakan Aktor:

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

Edit - dihapus referensi untuk System.currentTimeMillis(), faktor keluar a(1).toInt, diubah dari List.rangemenjadix to y

Sunting 2 - mengubah whileloop menjadi a for, mengubah flip kiri ke fungsi daftar yang melakukan hal yang sama, bergantung pada konversi tipe implisit sehingga tipe 6 char BigInthanya muncul sekali, diubah println untuk mencetak

Sunting 3 - menemukan cara melakukan beberapa deklarasi di Scala

Sunting 4 - berbagai optimasi yang saya pelajari sejak pertama kali saya melakukan ini

Versi tidak disatukan:

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

}

Faktorial 10 dihitung pada 4 core dengan menghasilkan 4 Daftar:

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

yang dikalikan secara paralel. Akan ada pendekatan yang lebih sederhana untuk mendistribusikan angka-angka:

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

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

Tetapi distribusinya tidak akan sebagus itu - angka yang lebih kecil semuanya akan berakhir di daftar yang sama, tertinggi di yang lain, yang mengarah ke perhitungan yang lebih panjang di daftar terakhir (untuk Ns tinggi, utas terakhir tidak akan hampir kosong. , tetapi setidaknya mengandung (N / core) elemen -cores.

Scala dalam versi 2.9 berisi Koleksi paralel, yang menangani pemanggilan paralel sendiri.

Erlang - 295 karakter.

Hal pertama yang pernah saya tulis di Erlang jadi saya tidak akan terkejut jika seseorang dapat dengan mudah membagi dua ini:

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

Menggunakan model threading yang sama dengan entri Ruby saya sebelumnya: membagi rentang menjadi sub-rentang dan mengalikan rentang bersama-sama di utas terpisah lalu mengalikan hasilnya kembali di utas utama.

Saya tidak dapat menemukan cara agar escript berfungsi jadi simpan saja f.erldan buka erl dan jalankan:

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

dengan substitusi yang tepat.

Dapatkan sekitar 8 untuk 50000 dalam 2 proses dan 10 untuk 1 proses, di MacBook Air saya (dual-core).

Catatan: Perhatikan saja macet jika Anda mencoba lebih banyak proses daripada nomor untuk memfaktorkanisasi.