Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / SS 2012 / Funktionale Programmierung / Übungen / Übung 05


Inhaltsbereich

Übung 05

Übungsblatt 05: Parallelität

Haskell source code icon 05Parallel.hs — Haskell source code, 6 KB (6744 bytes)

Dateiinhalt

-- | Functional Programming, course at LMU, summer term 2012
--   Andreas Abel and Steffen Jost
--
-- Exercise sheet 5, 2012-05-31
--
-- Due: Monday 04 June 2012 before the lecture

-- general
import Data.List
import Control.Monad

-- GpH:
import Control.Parallel
import Control.Parallel.Strategies
import Control.DeepSeq

-- Concurrent Haskell:
import Control.Concurrent

-- main = exercise1
main = exercise2
-- main = exercise3

{-
  Hinweise:
    Die Verwendung mehrerer Kerne läßt sich mit dem Interpreter (ghci) nur schlecht messen.
    Wählen Sie daher in Zeile 20-22 die richtige Main-Funktion aus,
    und kompilieren Sie dann Ihre Lösung mit ghc wie folgt:
        > ghc 05Parallel.hs -O2 -threaded -rtsopts

    und dann mit gewünschter Anzahl echter Threads ausführen:
        > time ./05Parallel +RTS -N4
        > time ./05Parallel +RTS -N3
        > time ./05Parallel +RTS -N2
        > time ./05Parallel +RTS -N1

    die Angabe unter "real" ist dann ein brauchbares Maß.
    Sie können auch genaure Messungen durchführen mit:
        > ./05Parallel +RTS -N4 -s


    Vergewissern Sie sich, dass auf Ihrem Rechner keine anderen Prozesse
    wesentliche Rechenkraft beanspruchen, da ansonsten die Messung
    mit "real" unbrauchbar ist.
    Vergewissern Sie sich auch, dass Ihr Haskell Programm so viele
    Prozessorkerne verwendet, wie Sie vorschreiben.
    Beide können Sie durch ausführen des Programms "htop" tun.


    Falls die Module Control.Parallel und Control.Parallel.Strategies nicht gefunden werden,
    so müssen Sie diese noch installieren:
        > cabal update
        > cabal install parallel

 -}


----------------------------------------------------------------------
-- Exercise 1
--
-- Betrachten Sie die Funktion pay, welche für einen gegebenen Betrag
-- und einer gegebenen Menge Münzen [(Münzgröße,Anzahl)] alle Möglichkeiten
-- ausgibt, diesen Betrag mit den Münzen zu bezahlen:
--   pay 10 [(3,3),(5,2),(1,2)] = [[(5,2)],[(1,2),(3,1),(5,1)],[(1,1),(3,3)]]
--
-- Das Ausführen der Funktion exercise1 dauert auf den Rechnern des
-- CIP-Pools knapp über einer Minute realer Zeit. Schreiben Sie die Funktion um,
-- so dass die gleiche Berechnung deutlich schneller erfolgt!
--
--
-- Hinweis:
--   Die CIP-Rechner haben 4 echte Kerne.
--   Selbst mit geringfügigen Änderungen am Programm kann die Berechnung
--   dort in weniger als 25 Sekunden durchgeführt werden.
--   Nicht parallele Lösungen unter 25 Sekunden werden auch akzeptiert,
--   wenn Sie erklären können, warum Ihre Veränderung mit
--   geringem Programmieraufwand durchgeführt werden können
--   (also z.B. durch Verwendung eines bekannten Programmierschemas).
----------------------------------------------------------------------

pay :: Integer -> [(Integer,Integer)] -> [[(Integer,Integer)]]
pay val coins = map count $ payL [] val coinsDescendingByValue where
  coinsDescendingByValue = sortBy (\a b -> invert $ compare (fst a) (fst b)) coins

-- | @payL acc val coins@ returns all possibilities to pay a remaining
--   amount of @val@ with @coins@ where @acc@ is a collection of
--   coins for the amount payed already (not part of @val@).
--   Each result is a list of coins.
payL :: [Integer] -> Integer -> [(Integer,Integer)] -> [[Integer]]
payL acc 0   coins = [acc]
payL acc _   []    = []
payL acc val ((c,qty):coins)
  | c > val   = discard
  | otherwise = use ++ discard
  where
    use     = payL (c:acc) (val - c) coins' -- use coin of value c
    discard = payL    acc   val      coins  -- ignore coin of value c
    coins' | qty == 1    = coins
           | otherwise   = (c,qty-1) : coins

-- | Take a list and turn it into a sorted enumeration of the elements
--   with their multiplicities.
count :: (Ord a, Num n) => [a] -> [(a, n)]
count xs = [(head ks, fromIntegral $ length ks) | ks <- group $ sort xs]

invert :: Ordering -> Ordering
invert EQ = EQ
invert LT = GT
invert GT = LT

exercise1 = do
  let value = 2345
  let coins = [(33,50),(23,25),(11,25),(5,25),(3,25),(1,25)]
  putStrLn $  "Berechne die Möglichkeiten den Wert " ++ (show value) ++ " mit den Münzen & Scheinen " ++ (show coins) ++ " darzustellen:"
  let poss  = pay value coins
  -- mapM_ (putStrLn . show) $ poss
  putStrLn $ "Es gibt " ++ (show $ length poss) ++ " Möglichkeiten den Wert " ++ (show value) ++ " mit den Münzen & Scheinen " ++ (show coins) ++ " darzustellen!"


----------------------------------------------------------------------
-- Exercise 2
--
-- In der Vorlesung wurden GpH Strategien vorgestellt.
-- Reimplementieren Sie Quicksort unter Verwendung von
-- Strategien aus Control.Parallel.Strategies!
--
-- Testen und vergleichen Sie exercise2 mit mindestens 3 verschiedenen
-- Auswerte-Strategien! Welche ist die Beste und warum?
--
-- Hinweis:
--   Die Laufzeit mit einem Kern sollte im CIP-Pool ca. 1 Minuten sein.
----------------------------------------------------------------------

quicksort1 :: [Integer] -> [Integer]
quicksort1 []       = []
quicksort1  (x:xs)  = result
  where
    result = losort ++ (x:hisort)
    losort = quicksort1 [y|y <- xs, y < x]
    hisort = quicksort1 [y|y <- xs, y >= x]

quicksortP :: [Integer] -> [Integer]
quicksortP xs = undefined

exercise2 = do
  putStrLn "Berechnung gestartet."
  let list1  = [1,7..3000] ++ (reverse [1..45678]) ++ [2,4..3000]
  let qlist1 = quicksort1 list1
  let len1   = seq (rnf qlist1) (length list1)
  let list2  = concat $ permutations $ [1..6]
  let qlist2 = quicksort1 list2
  let len2   = seq (rnf qlist2) (length list2)
  putStrLn $ "Berechnung von Quicksort mit Liste der Länge " ++ (show len1) ++ ":"
  --   putStrLn $ show $ take 33 $ drop 22222 $ quicksortP list1
  putStrLn $ "Berechnung von Quicksort mit Liste der Länge " ++ (show len2) ++ ":"
  --   putStrLn $ show $ take 33 $ drop 22222 $ quicksortP list2
  putStrLn $ "Done."


----------------------------------------------------------------------
-- Exercise 3
--
--  Wiederholen Sie Aufgabe 1, aber dieses Mal ohne Verwendung von GpH,
--  dafür mit expliziter Nebenläufigkeit durch forkIO!
--
----------------------------------------------------------------------

payT :: Integer -> [(Integer,Integer)] -> IO [[(Integer,Integer)]]
payT = undefined

exercise3 = do
  putStrLn "Berechnung gestartet."
  let value = 2345
  let coins = [(33,50),(23,25),(11,25),(5,25),(3,25),(1,25)]
  putStrLn $  "Berechne die Möglichkeiten den Wert " ++ (show value) ++ " mit den Münzen & Scheinen " ++ (show coins) ++ " darzustellen:"
  poss <- payT value coins
  -- mapM_ (putStrLn . show) $ poss
  putStrLn $ "Es gibt " ++ (show $ length poss) ++ " Möglichkeiten den Wert " ++ (show value) ++ " mit den Münzen & Scheinen " ++ (show coins) ++ " darzustellen!"

Artikelaktionen


Funktionsleiste