LINUX.ORG.RU

Помогите переписать с Go на Haskell

 ,


1

3

Haskell не знаю, но очень хочется написать/получить аналог данной программы.

В чём суть проблемы: у меня серьёзное непонимание, почему все примеры на Haskell, которые я находил, грузили максимум 1 ядро процессора. Я и хочу проверить: можно ли загрузить несколько ядер процессора Haskell'ем, или его рантайм этого не умеет. (Маленькая тайна в том, что тестирую под оффтопиком и хочется узнать возможности рантайма именно здесь)

package main

import (
	"fmt"
	"sync"
)

func fib(n uint64) uint64 {
	if n == 0 || n == 1 {
		return 1
	}

	return fib(n - 1) + fib(n - 2)
}

func parfib(t int, n uint64) {
	var wg sync.WaitGroup
	wg.Add(t)

	for i := 0; i < t; i++ {
		go func(i int, n uint64) {
			defer wg.Done()
			fmt.Println(i, fib(n))
		}(i, n)
	}

	wg.Wait()
}

func main() {
	parfib(5, 42)
}

Код оптимизировать не надо, нужно именно «в лоб» переписать.

P.S. на golang я в общем то тоже писать не умею, эту программку написал за 5 минут чтения доков.

Deleted

Последнее исправление: cetjs2 (всего исправлений: 2)

«в лоб», так «в лоб»

import Data.Functor
import Data.Int
import Control.Concurrent.Async

fib :: Int64 -> Int64
fib 0 = 1
fib 1 = 1
fib n = fib (n-1) + fib (n-2)


parfib :: Int -> Int64 -> IO ()
parfib t n = void $ mapConcurrently (\i -> print (i, fib n)) [0..(t-1)]

main = parfib 8 40

собирать с -threaded и запускать с +RTS -N

qnikst ★★★★★
()
Ответ на: комментарий от qnikst

Пока я ковырял свою тупую портянку, qnikst уже всё сделал в две строчки.

Для протокола(может заодно кто поправит):

module Main where

import Control.Concurrent
import Control.Monad
import Data.Int

fib :: Int64 -> Int64
fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

pickles :: Int -> Int64 -> IO ()
pickles threads n = do
  mvars <- replicateM threads $ do
    mvar <- newEmptyMVar
    forkFinally (fib n `seq` return ()) (\_ -> putMVar mvar ())
    return mvar
  forM_ mvars takeMVar

main :: IO ()
main = pickles 5 62

nezamudich ★★
()
Ответ на: комментарий от yoghurt

попросили в лоб, значит в лоб, что я ещё думать буду? Вообще наверное надо через стратегии такое запускать, которые под капотом par, pseq, seq сделают, да и композиться такое может сильно лучше, т.к. будет через спарки считаться.

qnikst ★★★★★
()
Ответ на: комментарий от qnikst

Да, программа собралась и честно загрузила все 4 ядра. Пусть и работает на порядок, если не больше, чем такая же не оптимизированная программа на Go.

Тем не менее работает на 4-х ядрах.

Нашёл «ускоряющие» флаги компиляции:

ghc -O2 -optc-O2 -fvia-C -threaded A.hs -no-recomp --make
Работает очень шустро, много шустрее Go без оптимизаций, но грузит только одно ядро (тут время меньше двух секунд на выполнение, явно, но и компиляция быстрая, предподсчёта не было).

Точные данные сказать не могу (на винде нормального time нет), т.к. с t=5 и n=42 я Haskell на три минуты (без оптимизаций) не дождался, тогда как Go отрабатывал несколько секунд (10-15).

В общем, Haskell меня порадовал, что работает.

Deleted
()
Последнее исправление: merhalak (всего исправлений: 1)
Ответ на: комментарий от nezamudich

Твоя программа отработала с флагами компиляции и с запуском

ghc -O2 -fvia-C -threaded main.hs -no-recomp --make
main.exe +RTS -N4
Так же быстро, как и программа на Go. (и загрузила все ядра)

А если делать так:

ghc -threaded main.hs
main.exe +RTS -N4
То работает так же быстро, но грузит лишь 3 ядра из 4-х. Даже любопытно.

Deleted
()

Спасибо, ребят, за помощь.

Deleted
()
Ответ на: комментарий от Deleted

-fvia-C вроде как deprecated на registered архитектурах, в принципе его на -fllvm можно заменить, часто llvm дает более хороший результат, чем нативный кодогенератор. (Правда иногда llvm, который хочет ghc устаревший по сравнению с тем, что идёт с дистрами), -no-recomp не очень понятно зачем. Загрузка определяется типом RTS: -threaded - будет количество capabilities процессов (задается в рантайме через опции RTS -RTS -N, в non-theaded будет один активный процесс).

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

qnikst ★★★★★
()
Ответ на: комментарий от Deleted

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

qnikst ★★★★★
()
Ответ на: комментарий от qnikst

Я из любопытства. Давно хочу заставить себя сесть за Haskell. Нашёл литературу, видеоуроки. А собраться не могу.

Deleted
()
Ответ на: комментарий от Deleted

Это просто другой алгоритм. По сути мемоизирует все предварительно посчитанные числа, только в остроумной манере, давая линейную сложность. Странно, что ещё никто матрицы экспоненцировать не предложил(не умеют?), там сложность вообще логарифмическая.

nezamudich ★★
()
Ответ на: комментарий от nezamudich

Странно, что ещё никто матрицы экспоненцировать не предложил(не умеют?), там сложность вообще логарифмическая.

Числа Фибоначчи тоже можно с логарифмической сложностью считать.

iVS ★★★★★
()
Ответ на: комментарий от iVS

интересно так:

А что в этом интересного? банальная свертка. И твой агоритм как-раз таки, не распараллелится толком, точней, распараллеливание не даст прироста, так как предыдущее каждое из вычислений зависит от предыдущего.

callbackhell
()
Ответ на: комментарий от callbackhell

Ты странный какой-то. Если каждый раз пересчитывать числа Фибоначчи (без мемоизации), то алгоритм отлично распараллеливается. Только сложность вычислений экспоненциальная. В предложенном мной варианте — линейная, можно сделать и логарифмическую. Параллельность там не будет и в помине, но кого это волнует, когда асимптотика такая?

iVS ★★★★★
()
Ответ на: комментарий от iVS

Числа Фибоначчи тоже можно с логарифмической сложностью считать.

Ты так говоришь, будто мой пост был не про числа Фибоначчи.

nezamudich ★★
()
Ответ на: комментарий от iVS

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

callbackhell
()
Ответ на: комментарий от nezamudich

А есть подход с матрицами? Можешь ссылку дать? А то я по рабоче-крестьянски думал выражать числа F(2m+1) и F(2m) через F(m+1) и F(m). Тогда можно подсчитать только F(2^k), F(2^k+1) (для степеней двойки), после чего n разложить на сумму степеней двойки и подсчитать F(n). Сложность O(log n).

iVS ★★★★★
()
Ответ на: комментарий от nezamudich

А, фактически то же самое. Нужно возводить матрицы в степени двойки, а потом n раскладывать в сумму степеней двойки.

iVS ★★★★★
()
Ответ на: комментарий от iVS

Я помню, как ты алгоритмически просто реализовал крестики и нолики на хаскеле, а я в том же треде, алгоритмически просто реализовал их же на JS, вместе с гуем, блекджеком и шлюхами, в 3 раза короче. Алгоритмическая хрень в хаскеле кончается ровно там, где кончается алгоритмический сахарок, знаем, проходили. Просто посчитать факториал, фибоначчи, а вот крестики и нолики — уже не просто, LOL

callbackhell
()
Ответ на: комментарий от iVS

А, фактически то же самое.

Да, только тривиальнее реализовывать:

$ ghci
GHCi, version 7.10.3: http://www.haskell.org/ghc/  :? for help
Prelude> :m + Data.Matrix
Prelude Data.Matrix> let fib n = getElem 1 2 $ fromLists [[0, 1], [1, 1]] ^ n
Prelude Data.Matrix> fib 6
8
Prelude Data.Matrix> fib 40
102334155
nezamudich ★★
()
Ответ на: комментарий от nezamudich

Вот первое я понял. А второе - это как?

Deleted
()
Ответ на: комментарий от stevejobs

Видеоуроки Москвина.

https://www.youtube.com/playlist?list=PLlb7e2G7aSpRDR44HMNqDHYgrAOPp7QLr

https://stepic.org/course/Функциональное-программирование-на-языке-Haskell-75...

И вот эта книга (куплена на сайте издательства, как раз):

http://www.piter.com/collection/alternativnye-tehnologii-i-servernye-yazyki-p...

Deleted
()
Последнее исправление: merhalak (всего исправлений: 2)
Ответ на: комментарий от stevejobs

чо за литература и видеоуроки? что наиболее годное?

https://compscicenter.ru/courses/func-prog/2015-spring/

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

aiive
()
Ответ на: комментарий от nezamudich

Ты переложил заботу об эффективности алгоритма на вшитое возведение в степень. Что немного нечестно, так будет честнее:

import Data.Matrix

squaredMatrixes :: [Matrix Int]
squaredMatrixes = fromLists [[0, 1], [1, 1]] :
                  map (\x -> multStd x x) squaredMatrixes

intToBin :: Int -> [Bool]
intToBin 0 = [False]
intToBin 1 = [True]
intToBin n = odd n : intToBin (n `div` 2)

fib :: Int -> Int
fib n = getElem 1 2 $ foldr (multStd . snd) (identity 2) $
        filter fst $ zip (intToBin n) squaredMatrixes
iVS ★★★★★
()
Ответ на: комментарий от iVS

Почему тогда вообще import Data.Matrix? Почему не самому бы поморочиться матричным произведением? Почему zip, filter, foldr и пр не раскрыты? Негодую!

nezamudich ★★
()
Ответ на: комментарий от nezamudich

Мы начинали с асимптотики, что она может быть логарифмическая. Прошу держаться в русле данного вопроса. Кол-во матриц для перемножения — это log n. Хотя, конечно, в увеличением чисел, входящих в матрицу, перемножение матриц должно замедляться. Поэтому не совсем логарифмическая зависимость. Еще, я не уверен, насколько хорошо проходит трюк с мемоизацией в вычислении ф-ции fib. Возможно, стоило для правильной мемоизации добавить энергичных вычислений.

iVS ★★★★★
()
Ответ на: комментарий от iVS

Мы начинали с асимптотики, что она может быть логарифмическая. Прошу держаться в русле данного вопроса. Кол-во матриц для перемножения — это log n.

То есть решение, в котором возведение в целую степень не закатывается вручную, не считается?

https://en.wikipedia.org/wiki/Exponentiation_by_squaring

nezamudich ★★
()
Ответ на: комментарий от nezamudich

То есть решение, в котором возведение в целую степень не закатывается вручную, не считается?

Где я такое сказал?

iVS ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.