Этот гольф требует, чтобы факторный расчет был разделен между несколькими потоками или процессами.

В некоторых языках это легче координировать, чем в других, поэтому это не зависит от языка. Приведен пример кода без правил, но вы должны разработать свой собственный алгоритм.

Цель конкурса - выяснить, кто может предложить самый короткий (в байтах, а не секундах) многоядерный факториальный алгоритм для вычисления N! по результатам голосования после закрытия конкурса. Должно быть многоядерное преимущество, поэтому нам потребуется, чтобы оно работало за N ~ 10000. Избиратели должны проголосовать, если автор не предоставит достоверного объяснения того, как это распределяет работу между процессорами / ядрами, и голосовать на основе лаконичности гольфа.

Для любопытства, пожалуйста, оставьте некоторые номера производительности. В какой-то момент может быть компромисс между игрой в гольф и игрой в гольф, если она соответствует требованиям. Мне было бы интересно узнать, когда это произойдет.

Вы можете использовать обычно доступные одноядерные библиотеки больших целых чисел. Например, perl обычно устанавливается вместе с bigint. Однако обратите внимание, что простой вызов предоставляемой системой факториальной функции обычно не распределяет работу между несколькими ядрами.

Вы должны принять от STDIN или ARGV вход N и вывести STDOUT значение N !. При желании вы можете использовать второй входной параметр, чтобы также указать количество процессоров / ядер для программы, чтобы она не выполняла то, что вы увидите ниже :-) Или вы можете явно указать 2, 4, что у вас есть.

Ниже я опубликую свой собственный пример Perl, который ранее был представлен в Переполнении стека в разделе Факторные алгоритмы на разных языках . Это не гольф. Было представлено множество других примеров, многие из них - гольф, но многие нет. Из-за общего лицензирования, не стесняйтесь использовать код в любых примерах по ссылке выше в качестве отправной точки.

Производительность в моем примере невелика по ряду причин: она использует слишком много процессов, слишком много преобразования строк / больших чисел. Как я уже сказал, это намеренно странный пример. Это будет рассчитывать 5000! менее чем за 10 секунд на 4-ядерном компьютере здесь. Тем не менее, более очевидные два цикла для / следующего цикла могут сделать 5000! на одном из четырех процессоров в 3.6s.

Вам определенно придется сделать лучше, чем это:

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

Мой интерес к этому просто (1) облегчение скуки; и (2) узнать что-то новое. Для меня это не домашняя работа или исследование.

Удачи!

Mathematica

Параллельно-способная функция:

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

Где г Identityили в Parallelizeзависимости от типа требуемого процесса

Для теста синхронизации мы немного изменим функцию, чтобы она возвращала реальное время.

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

И мы тестируем оба режима (от 10 ^ 5 до 9 * 10 ^ 5): (здесь только два ядра)

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

Результат:

Haskell: 209 200 198 177 символов

176 167 источник + 33 10 флаг компилятора

Это решение довольно глупо. Продукт применяется параллельно со значением типа [[Integer]], где внутренние списки имеют длину не более двух элементов. Как только внешний список становится максимум 2 списками, мы выравниваем его и получаем продукт напрямую. И да, для проверки типов нужно что-то, помеченное Integer, иначе оно не скомпилируется.

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

(Не стесняйтесь читать среднюю часть fмежду concatи sкак "до тех пор, пока я сердце длиной")

Казалось, что все будет довольно хорошо, так как parMap из Control.Parallel.Strategies позволяет довольно легко распределить это по нескольким потокам. Тем не менее, похоже, что GHC 7 требует колоссальных 33 символов в параметрах командной строки и переменных среды, чтобы фактически позволить многопоточному времени выполнения использовать несколько ядер (которые я включил в общую сумму). Если я что-то упустил, что, безусловно, возможно . ( Обновление : среда выполнения GHC с резьбой, по-видимому, использует потоки N-1, где N - количество ядер, поэтому не нужно возиться с параметрами времени выполнения.)

Компилировать:

ghc -threaded prog.hs

Время выполнения, однако, было довольно хорошим, учитывая, что было запущено нелепое количество параллельных оценок, и что я не компилировал с -O2. За 50000! на двухъядерном MacBook я получаю:

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)

Общее количество раз для нескольких различных значений: первый столбец - параллель гольфа, второй - наивный последовательный вариант:

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

Для справки, наивная последовательная версия - это (которая была скомпилирована с -O2):

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

Рубин - 111 + 56 = 167 символов

Это двухфайловый скрипт, основной файл ( 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(:*)

дополнительный файл ( f2.rb):

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

Просто берет число процессов и число для вычисления в виде аргументов и разбивает работу на диапазоны, которые каждый процесс может рассчитать индивидуально. Затем умножает результаты в конце.

Это действительно показывает, насколько медленнее Рубиниус для YARV:

Rubinius:

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

Ruby1.9.2:

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

(Обратите внимание на дополнительное 0)

Ява, 523 519 434 430 429 символов

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

Две 4 в последней строке - количество потоков, которые нужно использовать.

50000! протестировано на следующей платформе (без первоначальной версии исходной версии и с небольшим количеством плохих практик - хотя ее еще много) дает (на моей 4-ядерной машине с Linux) время

7685ms
2338ms
1361ms
1093ms
7724ms

Обратите внимание, что я повторил тест с одним потоком для справедливости, потому что джит, возможно, нагрелся.

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 с bigints - это не тот язык, на котором можно играть в гольф (посмотрите, что я должен сделать, просто чтобы создать жалкие вещи, потому что конструктор, который занимает много времени, является приватным), но эй.

Из неопрятного кода должно быть совершенно очевидно, как он разбивает работу: каждый поток умножает класс эквивалентности по модулю количества потоков. Ключевым моментом является то, что каждый поток выполняет примерно одинаковый объем работы.

CSharp - 206 215 символов

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

Делит вычисления с помощью функции C # Parallel.For ().

Редактировать; Забыл замок

Время выполнения:

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

Берет Nиз стандартного ввода.

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}

Функции:

• разделение вычислений: четность с одной стороны и шансы с другой (что-либо более сложное, чем это, потребует большого количества символов, чтобы соответствующим образом сбалансировать вычислительную нагрузку.
• IPC использует общий анонимный файл.

Ориентир:

• 10000! печатается в разветвленных 2.3s, разветвленных в 3.4s
• +100000! печатается в 5'08.8 раздвоенным, 7'07,9 раздвоенным

Scala ( 345 266 244 232 214 символов)

Используя Актеров:

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

Изменить - удалены ссылки на System.currentTimeMillis(), вычеркнуты a(1).toInt, изменены с List.rangeнаx to y

Редактировать 2 - изменил whileцикл на a for, изменил левый сгиб на функцию списка, которая делает то же самое, полагаясь на неявные преобразования типов, так что BigIntтип 6 символов появляется только один раз, изменил println для печати

Edit 3 - узнал, как сделать несколько объявлений в Scala

Редактировать 4 - различные оптимизации, которые я изучил с тех пор, как впервые сделал это

Безголовая версия:

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

}

Факториал 10 вычисляется на 4 ядрах путем создания 4 списков:

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

которые умножаются параллельно. Был бы более простой подход к распределению чисел:

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

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

Но распределение не будет таким хорошим - все меньшие числа будут заканчиваться в одном и том же списке, а самые высокие - в другом, что приведет к более длинным вычислениям в последнем списке (для больших N последний поток не будет почти пустым). , но, по крайней мере, содержат (N / core) -ядерные элементы.

Scala в версии 2.9 содержит параллельные коллекции, которые сами обрабатывают параллельный вызов.

Эрланг - 295 символов.

Первое, что я когда-либо писал на Эрланге, поэтому я не удивлюсь, если кто-то сможет вдвое сократить это:

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

Использует ту же модель потоков, что и в моей предыдущей записи Ruby: разбивает диапазон на поддиапазоны и умножает диапазоны вместе в отдельных потоках, а затем умножает результаты обратно в основной поток.

Я не смог понять, как заставить работать скрипт, поэтому просто сохраните как, f.erlоткройте erl и запустите:

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

с соответствующими заменами.

На моем MacBook Air (двухъядерный) я получил около 8 секунд за 50000 за 2 процесса и 10 секунд за 1 процесс.

Примечание: только что заметил, что он зависает, если вы пытаетесь факторизовать больше процессов, чем число.