24_b_1, 24_b_2: Add solution

3 files changed, 236 insertions, 2 deletions

diff --git a/README.md b/README.md
index d2eb948..4444c05 100644
--- a/README.md
+++ b/README.md
@@ -189,8 +189,8 @@ are prefixed with 'Module_'.
 | 23_a_3         | yes    |      | |
 | **_24_a_1_**   | yes    | 542  | 24. Concurrent and multicore programming |
 | 24_a_2         | yes    |      | |
-| **_24_b_1_**   |        | 551  | |
-| 24_b_2         |        |      | |
+| **_24_b_1_**   | yes    | 551  | |
+| 24_b_2         | yes, in 24_b_1  |      | |
 | **_26_a_1_**   |        | 610  | 26. Advanced library design: building a Bloom filter |
 | 26_a_2         |        |      | |
 
diff --git a/ch24/24_b_1.hs b/ch24/24_b_1.hs
new file mode 100644
index 0000000..aa783c6
--- /dev/null
+++ b/ch24/24_b_1.hs
@@ -0,0 +1,178 @@
+-- 1. It can be difficult to determine when to switch from parSort2 to sort. An
+--    alternative approach to the one we outline above would be to decide based
+--    on the length of a sublist. Rewrite parList2 so that it switches to sort
+--    if the list contains more than some number of elements.
+--
+-- 2. Measure the performance of the length-based approach, and compare with the
+--    depth approach. Which gives better performance results?
+
+
+-- There is most probably a typo in the assignment. The
+--   "if the list contains more than"
+-- should be
+--   "if the list contains less than".
+--
+-- parSort2 switches to sort if the level is deeper than a specified level. The
+-- deeper the level is, the shorter the sublist is. It makes sense to use the
+-- sequential sort for a short list because the overhead of creating threads
+-- would be too high in proportion to just sequentially sorting the list.
+--
+-- partList2 should do that too (switching to sort if the list is shorter than
+-- the threshold), it should just decide based on the length of a sublist.
+
+
+-- Comparing performance of algorithms is not easy, especially for average cases
+-- of inputs. Thus, instead of in-depth analysis and comparison I will just do a
+-- few measurements and based on that I will set a general result. For the
+-- comparison to make more sense, both of the implementations will run on the
+-- same random input.
+
+
+{-- From examples/examples/ch24/SortMain.hs and modified --}
+module Main where
+
+import Data.Time.Clock (diffUTCTime, getCurrentTime, NominalDiffTime)
+import System.Environment (getArgs)
+import System.Random (StdGen, getStdGen, randoms)
+
+import Sorting
+
+import Control.Parallel (par, pseq)
+
+randomInts :: Int -> StdGen -> [Int]
+randomInts k g = let result = take k (randoms g)
+                 in force result `seq` result
+
+main = do
+  args <- getArgs
+  let (inputSize, paramSort, paramList, avgRuns) =
+        case args of
+          (c:ps:pl:a:_) -> (read c, read ps, read pl, read a)
+          _ -> error "Missing arguments"
+  input <- randomInts inputSize `fmap` getStdGen
+  putStrLn $ "We have " ++ show (length input) ++ " elements to sort."
+
+  s <- timedAvg (parSort2 paramSort) input avgRuns
+  putStrLn $ show s
+
+  t <- timedAvg (parList2 paramList inputSize) input avgRuns
+  putStrLn $ show t
+
+timedAvg :: ([Int] -> [Int]) -> [Int] -> Int -> IO NominalDiffTime
+timedAvg sortFunc input runCount = do
+  times <- mapM (\_ -> timed sortFunc input) [1..runCount]
+  return $ (sum times) / (fromIntegral (length times))
+
+timed :: ([Int] -> [Int]) -> [Int] -> IO NominalDiffTime
+timed sortFunc input = do
+  start <- getCurrentTime
+  let sorted = sortFunc input
+  putStr $ "Sorted all " ++ show (length sorted) ++ " in "
+  end <- getCurrentTime
+  let diff = end `diffUTCTime` start
+  putStrLn $ show diff
+  return $ diff
+{-- End of code from examples --}
+
+parList2 :: (Ord a) => Int -> Int -> [a] -> [a]
+parList2 l min list@(x:xs)
+  | l < min   = sort list
+  | otherwise = force greater `par` (force lesser `pseq`
+                                      (lesser ++ x:greater))
+  where
+        le      = [y | y <- xs, y <  x]
+        gr      = [y | y <- xs, y >= x]
+        leLen   = length le
+        grLen   = length gr
+        lesser  = parList2 leLen min le
+        greater = parList2 grLen min gr
+parList2 _ _ _ = []
+
+
+-- Choice of pivot for Quicksort is very important. In the parSort2
+-- implementation from the examples, the pivot is the first item in a list to
+-- sort.
+--
+-- This means, a sorted list is the worst case. For ascending order, the
+-- 'lesser' array will always contain no elements, the 'greater' list will
+-- always contain all the elements. Thus, the sorting will be slowest (time
+-- complexity O(n^2)). Similarly for descending order.
+--
+-- The best case is when the first item in the list is the middle value, it
+-- means, when half of the items in the list are smaller and half of them bigger
+-- than the middle value. This results in a balanced split of the sorted list
+-- and the sorting depth will be log(n) (time complexity O(n log(n))).
+
+
+-- My hypothesis was that for the best case, parSort2 and parList2 would perform
+-- similarly because a depth limit for parSort2 can be converted into a list
+-- length limit for parList2, so both would be switching to the sequential
+-- 'sort' at the same time.
+--
+-- The closest the input list would be to the worst case, the more difference
+-- would there be. parList2 would perform much better thanks to fewer
+-- applications of 'par'.
+--
+-- After running a few worst case experiments I found out that the quadratic
+-- time complexity by far outweighs the speedup gained from reducing
+-- applications of 'par', so I used only average/random inputs.
+
+
+-- I compiled the source with
+--   stack ghc -- -threaded 24_b_1.hs
+
+-- My computer has 4 cores. The command I used for running the sort was
+--   ./24_b_1 +RTS -N4 -RTS <INPUT_SIZE> <PARSORT_PARAM> <PARLIST_PARAM> <AVG_RUNS>
+--
+-- where INPUT_SIZE is number of elements of the list to sort, PARSORT_PARAM is
+-- the parameter to parSort2 (the threshold depth), PARLIST_PARAM is the
+-- parameter to parList2 (the threshold length), and AVG_RUNS is number of runs
+-- of each sort implementation for computing the average sorting time.
+
+-- The input sizes tested were 4 000 000 and 400 000 elements. The testing was
+-- automated using a shell script. I set the parameters by computing binary
+-- logarithm from the size of the input. This is the max. depth of a balanced
+-- binary tree, it means, max. depth for a best case list. In the result tables
+-- below this computed parameter is in parentheses. Then I tested lower and a
+-- few greater parameter values. For parSort2 the value is the depth, for
+-- parList2 it is a length of a sublist + 1 (because of 'l < min' in the
+-- implementation I wanted the switch to the sequential sort to happen also at
+-- the threshold value).
+
+-- The results for input size 4 000 000:
+--
+-- PARSORT_PARAM  PARLIST_PARAM   parSort2_time   parList2_time  is_parList2_faster
+--            26       67108865  16.1435506608s  16.5742411336s
+--            24       16777217  17.2344045572s  15.0797320632s  yes
+--          (22)      (4194305)  16.747620797s   17.9526976908s
+--            20        1048577  15.8036009976s  14.9289581244s  yes
+--            18         262145  14.9604795514s  15.0083064052s
+--            16          65537  13.5984633668s  14.8022182528s
+--            14          16385  15.8516987842s  17.8260459492s
+--            12           4097  15.4590705512s  15.6482811018s
+--            10           1025  13.8612868966s  14.5261572668s
+--             8            257  13.1958234944s  14.6600659704s
+--             6             65  15.4553144422s  14.8244605894s  yes
+--             4             17  13.5678723824s  15.7817085602s
+--             2              5  14.6244923772s  15.7249399864s
+--             0              2  15.7628948616s  15.7540970314s  yes
+
+-- The results for input size 400 000:
+--
+-- PARSORT_PARAM  PARLIST_PARAM  parSort2_time  parList2_time  is_parList2_faster
+--            26       67108865  0.808638032s   0.8980840812s
+--            24       16777217  0.9464536416s  1.0021756256s
+--          (22)      (4194305)  0.9558710392s  1.0741807468s
+--            20        1048577  0.764964904s   0.9638306786s
+--            18         262145  1.0843675078s  1.1163900494s
+--            16          65537  0.92859031s    0.96355397s
+--            14          16385  0.9129570608s  1.0464927062s
+--            12           4097  1.1209530828s  1.1124485972s  yes
+--            10           1025  0.8144274202s  0.987780161s
+--             8            257  1.0196146734s  1.0743890808s
+--             6             65  0.9790765378s  0.9524003582s  yes
+--             4             17  0.8646994942s  0.902187454s
+--             2              5  0.8896786326s  0.9591653616s
+--             0              2  1.0028687866s  0.9903121374s  yes
+
+-- Overall, parSort2 performs better than parList2.
diff --git a/ch24/Sorting.hs b/ch24/Sorting.hs
new file mode 100644
index 0000000..6fb9870
--- /dev/null
+++ b/ch24/Sorting.hs
@@ -0,0 +1,56 @@
+{-- snippet parSort --}

+module Sorting where

+

+import Control.Parallel (par, pseq)

+

+parSort :: (Ord a) => [a] -> [a]

+parSort (x:xs)    = force greater `par` (force lesser `pseq`

+                                         (lesser ++ x:greater))

+    where lesser  = parSort [y | y <- xs, y <  x]

+          greater = parSort [y | y <- xs, y >= x]

+parSort _         = []

+{-- /snippet parSort --}

+

+{-- snippet sillySort --}

+sillySort (x:xs) = greater `par` (lesser `pseq`

+                                  (lesser ++ x:greater))

+    where lesser   = sillySort [y | y <- xs, y <  x]

+          greater  = sillySort [y | y <- xs, y >= x]

+sillySort _        = []

+{-- /snippet sillySort --}

+

+{-- snippet sort --}

+sort :: (Ord a) => [a] -> [a]

+sort (x:xs) = lesser ++ x:greater

+    where lesser  = sort [y | y <- xs, y <  x]

+          greater = sort [y | y <- xs, y >= x]

+sort _ = []

+{-- /snippet sort --}

+

+{-- snippet seqSort --}

+seqSort :: (Ord a) => [a] -> [a]

+seqSort (x:xs) = lesser `pseq` (greater `pseq`

+                                (lesser ++ x:greater))

+    where lesser  = seqSort [y | y <- xs, y <  x]

+          greater = seqSort [y | y <- xs, y >= x]

+seqSort _ = []

+{-- /snippet seqSort --}

+

+{-- snippet force --}

+force :: [a] -> ()

+force xs = go xs `pseq` ()

+    where go (_:xs) = go xs

+          go [] = 1

+{-- /snippet force --}

+

+{-- snippet parSort2 --}

+parSort2 :: (Ord a) => Int -> [a] -> [a]

+parSort2 d list@(x:xs)

+  | d <= 0     = sort list

+  | otherwise = force greater `par` (force lesser `pseq`

+                                     (lesser ++ x:greater))

+      where lesser      = parSort2 d' [y | y <- xs, y <  x]

+            greater     = parSort2 d' [y | y <- xs, y >= x]

+            d' = d - 1

+parSort2 _ _              = []

+{-- /snippet parSort2 --}