Факториал (Потоки)

[Portnov]

Ну, в данном случае Haskell (и некоторые ещё языки) хорош только тем, что у него длинная арифметика в стандартной библиотеке (по умолчанию то самое GMP). Тип Integer её и даёт. Ну и «зелёные потоки», в некотором смысле аналог pthreads, более легковесный.

[drBatty]

Ну, в данном случае Haskell (и некоторые ещё языки) хорош только тем, что у него длинная арифметика в стандартной библиотеке

да? тогда как раз для этой задачи. В С++ придётся делать/прикручивать длинную арифметику, плюс делать специальную очередь. Если в функциональных языках не надо делать арифметику, то их и надо использовать, ибо с очередями там всё прекрасно.

[sciko]

где код?

Вычмсление факториала:

Код: Выделить всё

fac n = product [1..n]

Типичная программа на Haskel:

Код: Выделить всё

q a b c=putStrLn $ b ++ [toEnum 10,'q','(']
  ++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']
main=q "q a b c=putStrLn $ b ++ [toEnum 10,'q','(']
++ show b ++ [','] ++ show c ++ [','] ++ show a ++ [')']"
  "def q(a,b,c):print b+chr(10)+'q('+repr(b)+','+repr(c)+','+repr(a)+')'"
  "def e(x) return 34.chr+x+34.chr end;def q(a,b,c) print
b+10.chr+'main=q '+e(b)+' '+e(c)+' '+e(a)+' '+10.chr end"

не думаю, что реализация длинной арифметики там будет более быстрой чем в C++.

Нет, конечно не будет. Но функциональные языки проще распараллеливать. Обычно это умеет сам копилятор/интерпритатор.

[drBatty]

Вычмсление факториала:

Но функциональные языки проще распараллеливать. Обычно это умеет сам копилятор/интерпритатор.

это всё ясно. А как с практикой? Кто быстрее вычислит факториал скажем 100500! ?

[eddy]

(пример из мана)
теперь можете писать свои проги прямо в шелле

Шустро-то как считает: набираю f(1000) - и бац! Уже посчитал. Правда на f(100500) подзадумался

[sciko]

А как с практикой?

На Haskell получить отлаженную программу получиться быстрее.

Кто быстрее вычислит факториал скажем 100500! ?

Затрудняюсь ответить. Думаю ответ нам даст эксперимент.

[drBatty]

Шустро-то как считает

дык это просто. попробуйте вот такую задачку:

$

factor 10050077791175843834

Думаю ответ нам даст эксперимент.

лень реализовывать быструю длинную арифметику.

[/dev/random]

лень реализовывать быструю длинную арифметику.

А зачем её реализовывать, если есть gmp?

[eddy]

дык это просто. попробуйте вот такую задачку:

Боюсь, и за 100 лет не посчитает

[/dev/random]

Боюсь, и за 100 лет не посчитает

И займёт ~ 67 экзабайт. Формула (синтаксис bc): (n*l(n) - n + l(n)/2 + l(2*3.14)/2)/l(256)

[drBatty]

А зачем её реализовывать, если есть gmp?

а я с ней никогда не работал...

Боюсь, и за 100 лет не посчитает

эх...

$

time -p factor 10050077791175843834 10050077791175843834: 2 7 717862699369703131 real 16.04 user 14.27 sys 0.02

16 сек. Это не факториал :)

[eddy]

16 сек. Это не факториал

Откуда ж я знал, что это - поиск простых делителей?
У меня:

Код: Выделить всё

time -p ./111
real 2.31
user 1.01
sys 1.29

cat 111
#!/bin/bash
for a in $(seq 1 1000)
    do factor 10050077791175843834 > /dev/null
done

Даже не знал, что в coreutils такая штука есть... Зачем - непонятно (для шифрования, что ли?).

[drBatty]

Даже не знал, что в coreutils такая штука есть... Зачем - непонятно (для шифрования, что ли?).

нет... оно большие числа не умеет :-(
а в шифровании такие мелкие ключи 20 лет никто не юзает. Просто иногда программерам надо. Некоторые константы должны удовлетворять заданным требованиям, например не делится на определённые множители. Ну например простейший генератор ПСП... Не наворачивать-же каждый раз программку. К тому-же, это довольно сложная задача, ибо тривиальный вариант работает жутко долго.

real 2.31

кстати по теме - проверьте пожалуйста, оно все ваши ядра задействует?

[Crazy]

не думаю, что реализация длинной арифметики там будет более быстрой чем в C++.

Нет, конечно не будет. Но функциональные языки проще распараллеливать. Обычно это умеет сам копилятор/интерпритатор.

Почему же?

[eddy]

кстати по теме - проверьте пожалуйста, оно все ваши ядра задействует?

Нагрузка в top'е примерно симметричная, как для отдельного процесса нагрузку на ядра посмотреть - не знаю.
И да, я на работе сижу, у меня здесь слабый компьютер (2 ядра всего). Рядом стоит шестиядерный, но не могу проверить - кулер жду...

[drBatty]

Нагрузка в top'е примерно симметричная

я это к тому, что задача из той-же серии - множество арифметики. Потому вопрос ТС можно решить так: посмотреть, как это сделали другие. Мне лень, а ему интересно.

[/dev/random]

Нагрузка в top'е примерно симметричная, как для отдельного процесса нагрузку на ядра посмотреть - не знаю.

"Симметричная" она может быть просто потому, что ядро (системы) бросает процесс с одного ядра (процессора) на другое. Такое бывает. Если распараллелено нормально, то все ядра должны быть заняты на 100%, а не просто симметрично.

[BratSinot]

нет. я предлагаю список, в котором будут числа. а процессы будут брать эти числа из списка, и вставлять туда результаты. числа будут громадными, потому время их обработки будет огромным, и всеми накладными расходами можно смело пренебречь. Ессно в списке будут указатели на числа, и процессы будут брать и отдавать указатели, ибо даже 100! не влезет ни в какие типы даных. Вот 100! == 93326215443944152681699238856266700490715968264381621468592963895217599993229915
608941463976156518286253697920827223758251185210916864000000000000000000000000

В GMP число ограничено только количеством оперативной памяти.
P.S. Ну и конечно аппаратными ограничениями.
P.S.S. Я вполне успешно считаю факториалы от 1 до 100000.

[drBatty]

Я вполне успешно считаю факториалы от 1 до 100000.

вопрос не про количество. вопрос про стоимость накладных операций. Я полагаю, что их стоимость ничтожна по сравнению с умножением.

[Crazy]

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

Ведь можно решить без этого списка.
Код на Erlang

Код: Выделить всё

-module(pfact).
-export([pfact/2, pfactorial/5]).

pfact(N, Threads)->
    if
    N < Threads ->
        fact(N);
    true ->
        load_threads(1, N, Threads),
        message_loop(1,Threads)
    end.

fact(0) ->
    1;
fact(N) ->
    fact(N-1)*N.

load_threads(C, N, Threads) ->
    if
    C=<Threads ->
        spawn(?MODULE, pfactorial, [C, N, Threads, self(),1]),
        load_threads(C+1, N, Threads);
    true -> ok
    end.

pfactorial(C,N,Threads, PID, Result) ->
    if
    C+Threads =< N ->
        pfactorial(C+Threads, N, Threads, PID, Result*C);
    true ->
        PID!{result, Result*C}
    end.


message_loop(Result, Threads) when Threads>0 ->
    receive
    {result, Res} ->
        message_loop(Result*Res, Threads - 1)
    end;
message_loop(Result, 0) ->
    Result.

[BratSinot]

Кстати, а GCC сам не распаралеливает? А то у меня процессор с двумя ядрами и HT, а прога загружает на все 100%.

[drBatty]

Ведь можно решить без этого списка.
Код на Erlang

тут нет списков?

[/dev/random]

Кстати, а GCC сам не распаралеливает? А то у меня процессор с двумя ядрами и HT, а прога загружает на все 100%.

Разные мониторы по-разному обозначают максимум. У одних "процесс занимает все ядра" - это 100%, у других - N*100% (N - число ядер). Т.е., например, для двухъядерника - 200%.

[Portnov]

Про автоматическое распараллеливание ходит много мифов :) GCC делает не совсем распараллеливание — а так называемую векторизацию, в тех случаях, которые может определить. Ну, например, цикл из 10 одинаковых умножений будет скомпилирован в несколько SIMD-инструкций (mmx, sse, whatever). На современных процах такие конструкции выполняются параллельно. Распараллеливание в смысле создания нескольких потоков ОС, каждый из которых будет считать свою часть задачи, в случае императивных языков очень сложно. Я не слышал что-то об успехах в этой области.

В случае функциональных языков всё лучше, но в основном теоретически. Автоматическое распараллеливание в них находится на стадии написания докторских диссертаций. Когда-нибудь оно, наверное, будет. А пока — более-менее вручную. Благо, в том же Хаскеле есть довольно удобные средства. Начиная от forkIO и заканчивая всякими Control.Parallel.Strategies.parmap.

[Crazy]

Ведь можно решить без этого списка.
Код на Erlang

тут нет списков?

Очереди появляются при обработке сообщений от процессов.
Сам же алгоритм на C++

Код: Выделить всё

    size_t N;
    cin>>N;
    size_t Threads;
    cin>>Threads;

    size_t fact = 1;
    for(size_t t = 1; t<=Threads; ++t)
    {
        size_t result=1;
        for(size_t k=t; k<=N; k+=Threads)
        {
            result*=k;
        }
        fact*=result;
    }

    cout<<fact<<std::endl;
    return 0;

Он создает такие последовательности:

Первый поток: 1*5*9*13
Второй поток : 2*6*10*14
Третий поток: 3*7*11*15
Четвертый поток:4*8*12*16

[Crazy]

Распараллеливание в смысле создания нескольких потоков ОС, каждый из которых будет считать свою часть задачи, в случае императивных языков очень сложно. Я не слышал что-то об успехах в этой области.

OpenTS, хотя тут пишешь на параллельном языке параллельную программу.
Теорема Бернштейна-Рассела-Нариньяни, для не параллельных императивных языков ставит крест.

[BratSinot]

Кстати, а GCC сам не распаралеливает? А то у меня процессор с двумя ядрами и HT, а прога загружает на все 100%.

Разные мониторы по-разному обозначают максимум. У одних "процесс занимает все ядра" - это 100%, у других - N*100% (N - число ядер). Т.е., например, для двухъядерника - 200%.

time

[/dev/random]

time

И какие результаты он выдал? Если программа действительно распараллелена, то real должен быть _гораздо меньше_, чем user+sys.

[sciko]

OpenTS, хотя тут пишешь на параллельном языке параллельную программу.

Слишком громко сказано. Реально в С++ тупо помечаются чистые функции. То есть смесь процедурного и функционального языков. По мне так лучше писать сразу на функциональном языке чтобы потом не получить внезапно недетерминированность или побочный эффект.

Кроме того опенсорсных реализаций этого дела нет, а использовать в таких проектах блобы чревато поисками приключений на одно место.

[Crazy]

Слишком громко сказано. Реально в С++ тупо помечаются чистые функции. А чистые функции То есть смесь процедурного и функционального языков. По мне так лучше писать сразу на функциональном языке чтобы потом не получить внезапно недетерминированность или побочный эффект.

Что бы внезапно не получить недетерминированность, надо теорию вычислительных процессов знать.