median-stream 0.2.0.0 → 0.3.0.0

raw patch · 5 files changed

+172/−13 lines, 5 filesdep +randomdep +timedep ~basePVP ok

version bump matches the API change (PVP)

Dependencies added: random, time

Dependency ranges changed: base

API changes (from Hackage documentation)

Files

• bench/Bench.hs +87/−0
• median-stream.cabal +29/−1
• src/Data/MedianStream.hs +13/−0
• test/Spec.hs +23/−12
• utils/Utils.hs +20/−0

@@ -0,0 +1,87 @@+import Control.Monad+import Data.MedianStream+import Data.Time.Clock+import System.Random+import Utils++main :: IO ()+main = benchmarks++benchmarks :: IO ()+benchmarks =+  forM_ ns $ \n -> do+    randomList <- take n . randoms <$> newStdGen+    putStrLn $ "\nBENCHMARKING: " ++ show n ++ " elements."+    benchBoth randomList n+  where ns = [10, 100, 1000, 10000, 100000, 200000, 500000]++benchBoth :: [Int] -> Int -> IO ()+benchBoth ls n = do+  putStrLn "Naive Median"+  benchNaiveMedian ls n+  putStrLn "Median Stream"+  benchMedianStream ls n++benchMedianStream :: [Int] -> Int -> IO ()+benchMedianStream ls size = do+  putStrLn "------------"+  putStrLn $ "First " ++ show inc ++ " elements."+  let (ls1, ls2) = splitAt inc ls+  let ms1        = fromList ls1+  timeOpMS ms1+  putStrLn $ "Next " ++ show inc ++ " elements."+  let (ls3, ls4) = splitAt inc ls2+  let ms2        = insertList ms1 ls3+  timeOpMS ms2+  putStrLn $ "Third " ++ show inc ++ " elements."+  let (ls5, ls6) = splitAt inc ls4+  let ms3        = insertList ms2 ls5+  timeOpMS ms3+  putStrLn $ "Last  " ++ show inc ++ " elements."+  let (ls7, ls8) = splitAt inc ls6+  let ms4        = insertList ms3 ls7+  timeOpMS ms4+  putStrLn ""+  where+    inc = size `div` 4++benchNaiveMedian :: [Int] -> Int -> IO ()+benchNaiveMedian ls size = do+  putStrLn "------------"+  putStrLn $ "First " ++ show inc ++ " elements."+  let (ls1, ls2) = splitAt inc ls+  timeOp medianOf ls1+  putStrLn $ "Next " ++ show inc ++ " elements."+  let (ls3, ls4) = splitAt inc ls2+  let ns1        = ls1 ++ ls3+  timeOp medianOf ns1+  putStrLn $ "Third " ++ show inc ++ " elements."+  let (ls5, ls6) = splitAt inc ls4+  let ns2        = ns1 ++ ls5+  timeOp medianOf ns2+  putStrLn $ "Last  " ++ show inc ++ " elements."+  let (ls7, ls8) = splitAt inc ls6+  let ns3        = ns2 ++ ls7+  timeOp medianOf ns3+  where+    inc = size `div` 4++timeOpMS :: MedianStream a -> IO ()+timeOpMS ms = do+  start <- getCurrentTime+  logMedian $ median ms+  end   <- getCurrentTime+  putStrLn $ "Elapsed: " ++ show (diffUTCTime end start)+  where+    logMedian Nothing  = return ()+    logMedian (Just m) = putStrLn $ "Median: " ++ show m++timeOp :: ([Int] -> Maybe Double) -> [Int] -> IO ()+timeOp fn ls = do+  start <- getCurrentTime+  logMedian $ fn ls+  end   <- getCurrentTime+  putStrLn $ "Elapsed: " ++ show (diffUTCTime end start)+  where+    logMedian Nothing  = return ()+    logMedian (Just m) = putStrLn $ "Median: " ++ show m

@@ -1,5 +1,5 @@ name:                median-stream-version:             0.2.0.0+version:             0.3.0.0 synopsis:            Constant-time queries for the median of a stream of numeric                      data. description:         Uses the two-heap approach to support O(lg n) insertions@@ -23,11 +23,39 @@  test-suite median-stream-test   type:                exitcode-stdio-1.0+  other-modules:       Utils   hs-source-dirs:      test+                     , utils   main-is:             Spec.hs   build-depends:       base                      , median-stream                      , QuickCheck+  ghc-options:         -threaded -rtsopts -with-rtsopts=-N+  default-language:    Haskell2010++benchmark median-stream-bench-optimized+  type:                exitcode-stdio-1.0+  other-modules:       Utils+  hs-source-dirs:      bench+                     , utils+  main-is:             Bench.hs+  build-depends:       base+                     , time+                     , median-stream+                     , random+  ghc-options:         -threaded -rtsopts -with-rtsopts=-N -O3+  default-language:    Haskell2010++benchmark median-stream-bench-non-optimized+  type:                exitcode-stdio-1.0+  other-modules:       Utils+  hs-source-dirs:      bench+                     , utils+  main-is:             Bench.hs+  build-depends:       base+                     , time+                     , median-stream+                     , random   ghc-options:         -threaded -rtsopts -with-rtsopts=-N   default-language:    Haskell2010 

@@ -19,10 +19,13 @@ , insert , median , size+, fromList+, insertList ) where  import Data.Heap (MaxHeap, MinHeap, Heap) import qualified Data.Heap as Heap hiding (MaxHeap, MinHeap, Heap)+import Data.List (foldl') import Data.Maybe (fromJust)  type Left a  = MaxHeap a@@ -76,6 +79,16 @@ -- Complexity: O(1) size :: MedianStream a -> Int size (MedianStream lh rh) = Heap.size lh + Heap.size rh++-- | Creates a MedianStream from a list of input elements.+-- Complexity: O(nlgn)+fromList :: (Real a, Eq a) => [a] -> MedianStream a+fromList = insertList empty++-- | Adds a list of input elements to an existing MedianStream+-- Complexity: O(nlgn)+insertList :: (Real a, Eq a) => MedianStream a -> [a] -> MedianStream a+insertList = foldl' (+>)  popAndSwap :: (Heap.HeapItem pol1 a,                Heap.HeapItem pol2 a)

@@ -3,6 +3,7 @@ import Data.List hiding (insert) import Data.MedianStream import Test.QuickCheck+import Utils  prop_medianStreamOnInts :: [Int] -> Bool prop_medianStreamOnInts xs = medianOf xs == median (foldr insert empty xs)@@ -22,19 +23,29 @@ prop_medianStreamOnDoublesV3 :: [Double] -> Bool prop_medianStreamOnDoublesV3 xs = medianOf xs == median (foldl' (+>) empty xs) -medianOf :: (Real a, Eq a) => [a] -> Maybe Double-medianOf []  = Nothing-medianOf [x] = Just . fromRational $ toRational x-medianOf xs  =-  let sorted = sort xs-      len    = length xs-    in case even len of-      True  -> let [x, y] = take 2 $ drop (len `div` 2 - 1) sorted-                in Just $ average x y-      False -> medianOf . take 1 $ drop (len `div` 2) sorted+prop_medianStreamOnIntsFromList :: [Int] -> Bool+prop_medianStreamOnIntsFromList xs = medianOf xs == median (fromList xs) -average :: (Real a) => a -> a -> Double-average x l = (/2) . fromRational $ toRational (x + l)+prop_medianStreamOnDoublesFromList :: [Double] -> Bool+prop_medianStreamOnDoublesFromList xs = medianOf xs == median (fromList xs)++prop_medianStreamOnIntsInsertList :: [Int] -> Bool+prop_medianStreamOnIntsInsertList xs =+  let (fh, sh) = halves xs+      ms       = fromList fh+    in medianOf fh         == median ms &&+       medianOf (fh ++ sh) == median (insertList ms sh)++prop_medianStreamOnDoublesInsertList :: [Double] -> Bool+prop_medianStreamOnDoublesInsertList xs =+  let (fh, sh) = halves xs+      ms       = fromList fh+    in medianOf fh         == median ms &&+       medianOf (fh ++ sh) == median (insertList ms sh)++halves :: [a] -> ([a], [a])+halves ls = splitAt mid ls+  where mid = length ls `div` 2  return [] runTests = $quickCheckAll

@@ -0,0 +1,20 @@+module Utils+(+  medianOf+) where++import Data.List (sort)++medianOf :: (Real a, Eq a) => [a] -> Maybe Double+medianOf []  = Nothing+medianOf [x] = Just . fromRational $ toRational x+medianOf xs  =+  let sorted = sort xs+      len    = length xs+    in case even len of+      True  -> let [x, y] = take 2 $ drop (len `div` 2 - 1) sorted+                in Just $ average x y+      False -> medianOf . take 1 $ drop (len `div` 2) sorted++average :: (Real a) => a -> a -> Double+average x l = (/2) . fromRational $ toRational (x + l)