Hello community,
here is the log from the commit of package ghc-vector-algorithms for
openSUSE:Factory checked in at 2018-09-03 10:35:09
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Comparing /work/SRC/openSUSE:Factory/ghc-vector-algorithms (Old)
and /work/SRC/openSUSE:Factory/.ghc-vector-algorithms.new (New)
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Package is "ghc-vector-algorithms"
Mon Sep 3 10:35:09 2018 rev:8 rq:632493 version:0.7.0.4
Changes:
--------
---
/work/SRC/openSUSE:Factory/ghc-vector-algorithms/ghc-vector-algorithms.changes
2018-08-20 16:21:01.332958205 +0200
+++
/work/SRC/openSUSE:Factory/.ghc-vector-algorithms.new/ghc-vector-algorithms.changes
2018-09-03 10:35:09.752678695 +0200
@@ -1,0 +2,6 @@
+Thu Aug 30 15:29:21 UTC 2018 - [email protected]
+
+- Update vector-algorithms to version 0.7.0.4.
+ Upstream does not provide a change log file.
+
+-------------------------------------------------------------------
Old:
----
vector-algorithms-0.7.0.1.tar.gz
vector-algorithms.cabal
New:
----
vector-algorithms-0.7.0.4.tar.gz
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Other differences:
------------------
++++++ ghc-vector-algorithms.spec ++++++
--- /var/tmp/diff_new_pack.sfDL8U/_old 2018-09-03 10:35:10.208679871 +0200
+++ /var/tmp/diff_new_pack.sfDL8U/_new 2018-09-03 10:35:10.208679871 +0200
@@ -19,14 +19,13 @@
%global pkg_name vector-algorithms
%bcond_with tests
Name: ghc-%{pkg_name}
-Version: 0.7.0.1
+Version: 0.7.0.4
Release: 0
Summary: Efficient algorithms for vector arrays
License: BSD-3-Clause
Group: Development/Libraries/Haskell
URL: https://hackage.haskell.org/package/%{pkg_name}
Source0:
https://hackage.haskell.org/package/%{pkg_name}-%{version}/%{pkg_name}-%{version}.tar.gz
-Source1:
https://hackage.haskell.org/package/%{pkg_name}-%{version}/revision/2.cabal#/%{pkg_name}.cabal
BuildRequires: ghc-Cabal-devel
BuildRequires: ghc-bytestring-devel
BuildRequires: ghc-primitive-devel
@@ -38,7 +37,8 @@
%endif
%description
-Efficient algorithms for vector arrays.
+Efficient algorithms for sorting vector arrays. At some stage other vector
+algorithms may be added.
%package devel
Summary: Haskell %{pkg_name} library development files
@@ -54,7 +54,6 @@
%prep
%setup -q -n %{pkg_name}-%{version}
-cp -p %{SOURCE1} %{pkg_name}.cabal
%build
%ghc_lib_build
++++++ vector-algorithms-0.7.0.1.tar.gz -> vector-algorithms-0.7.0.4.tar.gz
++++++
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/vector-algorithms-0.7.0.1/bench/Blocks.hs
new/vector-algorithms-0.7.0.4/bench/Blocks.hs
--- old/vector-algorithms-0.7.0.1/bench/Blocks.hs 2015-08-12
23:47:36.000000000 +0200
+++ new/vector-algorithms-0.7.0.4/bench/Blocks.hs 1970-01-01
01:00:00.000000000 +0100
@@ -1,62 +0,0 @@
-{-# LANGUAGE Rank2Types #-}
-
-module Blocks where
-
-import Control.Monad
-import Control.Monad.ST
-
-import Data.Vector.Unboxed.Mutable
-
-import System.CPUTime
-
-import System.Random.MWC (GenIO, Variate(..))
-
--- Some conveniences for doing evil stuff in the ST monad.
--- All the tests get run in IO, but uvector stuff happens
--- in ST, so we temporarily coerce.
-clock :: IO Integer
-clock = getCPUTime
-
--- Strategies for filling the initial arrays
-rand :: Variate e => GenIO -> Int -> IO e
-rand g _ = uniform g
-
-ascend :: Num e => Int -> IO e
-ascend = return . fromIntegral
-
-descend :: Num e => e -> Int -> IO e
-descend m n = return $ m - fromIntegral n
-
-modulo :: Integral e => e -> Int -> IO e
-modulo m n = return $ fromIntegral n `mod` m
-
--- This is the worst case for the median-of-three quicksort
--- used in the introsort implementation.
-medianKiller :: Integral e => e -> Int -> IO e
-medianKiller m n'
- | n < k = return $ if even n then n + 1 else n + k
- | otherwise = return $ (n - k + 1) * 2
- where
- n = fromIntegral n'
- k = m `div` 2
-{-# INLINE medianKiller #-}
-
-initialize :: (Unbox e) => MVector RealWorld e -> Int -> (Int -> IO e) -> IO ()
-initialize arr len fill = init $ len - 1
- where init n = fill n >>= unsafeWrite arr n >> when (n > 0) (init $ n - 1)
-{-# INLINE initialize #-}
-
-speedTest :: (Unbox e) => Int
- -> (Int -> IO e)
- -> (MVector RealWorld e -> IO ())
- -> IO Integer
-speedTest n fill algo = do
- arr <- new n
- initialize arr n fill
- t0 <- clock
- algo arr
- t1 <- clock
- return $ t1 - t0
-{-# INLINE speedTest #-}
-
-
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/vector-algorithms-0.7.0.1/bench/Main.hs
new/vector-algorithms-0.7.0.4/bench/Main.hs
--- old/vector-algorithms-0.7.0.1/bench/Main.hs 2015-08-12 23:47:36.000000000
+0200
+++ new/vector-algorithms-0.7.0.4/bench/Main.hs 1970-01-01 01:00:00.000000000
+0100
@@ -1,201 +0,0 @@
-{-# LANGUAGE Rank2Types #-}
-
-module Main (main) where
-
-import Prelude hiding (read, length)
-import qualified Prelude as P
-
-import Control.Monad.ST
-import Control.Monad.Error
-
-import Data.Char
-import Data.Ord (comparing)
-import Data.List (maximumBy)
-
-import Data.Vector.Unboxed.Mutable
-
-import qualified Data.Vector.Algorithms.Insertion as INS
-import qualified Data.Vector.Algorithms.Intro as INT
-import qualified Data.Vector.Algorithms.Heap as H
-import qualified Data.Vector.Algorithms.Merge as M
-import qualified Data.Vector.Algorithms.Radix as R
-import qualified Data.Vector.Algorithms.AmericanFlag as AF
-import qualified Data.Vector.Algorithms.Tim as T
-
-import System.Environment
-import System.Console.GetOpt
-import System.Random.MWC
-
-import Blocks
-
--- Does nothing. For testing the speed/heap allocation of the building blocks.
-noalgo :: (Unbox e) => MVector RealWorld e -> IO ()
-noalgo _ = return ()
-
--- Allocates a temporary buffer, like mergesort for similar purposes as noalgo.
-alloc :: (Unbox e) => MVector RealWorld e -> IO ()
-alloc arr | len <= 4 = arr `seq` return ()
- | otherwise = (new (len `div` 2) :: IO (MVector RealWorld Int)) >>
return ()
- where len = length arr
-
-displayTime :: String -> Integer -> IO ()
-displayTime s elapsed = putStrLn $
- s ++ " : " ++ show (fromIntegral elapsed / 1e12) ++ " seconds"
-
-run :: String -> IO Integer -> IO ()
-run s t = t >>= displayTime s
-
-sortSuite :: String -> GenIO -> Int -> (MVector RealWorld Int -> IO ()) -> IO
()
-sortSuite str g n sort = do
- putStrLn $ "Testing: " ++ str
- run "Random " $ speedTest n (rand g >=> modulo n) sort
- run "Sorted " $ speedTest n ascend sort
- run "Reverse-sorted " $ speedTest n (descend n) sort
- run "Random duplicates " $ speedTest n (rand g >=> modulo 1000) sort
- let m = 4 * (n `div` 4)
- run "Median killer " $ speedTest m (medianKiller m) sort
-
-partialSortSuite :: String -> GenIO -> Int -> Int
- -> (MVector RealWorld Int -> Int -> IO ()) -> IO ()
-partialSortSuite str g n k sort = sortSuite str g n (\a -> sort a k)
-
--- -----------------
--- Argument handling
--- -----------------
-
-data Algorithm = DoNothing
- | Allocate
- | InsertionSort
- | IntroSort
- | IntroPartialSort
- | IntroSelect
- | HeapSort
- | HeapPartialSort
- | HeapSelect
- | MergeSort
- | RadixSort
- | AmericanFlagSort
- | TimSort
- deriving (Show, Read, Enum, Bounded)
-
-data Options = O { algos :: [Algorithm], elems :: Int, portion :: Int, usage
:: Bool } deriving (Show)
-
-defaultOptions :: Options
-defaultOptions = O [] 10000 1000 False
-
-type OptionsT = Options -> Either String Options
-
-options :: [OptDescr OptionsT]
-options = [ Option ['A'] ["algorithm"] (ReqArg parseAlgo "ALGO")
- ("Specify an algorithm to be run. Options:\n" ++ algoOpts)
- , Option ['n'] ["num-elems"] (ReqArg parseN "INT")
- "Specify the size of arrays in algorithms."
- , Option ['k'] ["portion"] (ReqArg parseK "INT")
- "Specify the number of elements to partial sort/select
in\nrelevant algorithms."
- , Option ['?','v'] ["help"] (NoArg $ \o -> Right $ o { usage =
True })
- "Show options."
- ]
- where
- allAlgos :: [Algorithm]
- allAlgos = [minBound .. maxBound]
- algoOpts = fmt allAlgos
- fmt (x:y:zs) = '\t' : pad (show x) ++ show y ++ "\n" ++ fmt zs
- fmt [x] = '\t' : show x ++ "\n"
- fmt [] = ""
- size = (" " ++) . maximumBy (comparing P.length) . map show $
allAlgos
- pad str = zipWith const (str ++ repeat ' ') size
-
-parseAlgo :: String -> Options -> Either String Options
-parseAlgo "None" o = Right $ o { algos = [] }
-parseAlgo "All" o = Right $ o { algos = [DoNothing .. AmericanFlagSort] }
-parseAlgo s o = leftMap (\e -> "Unrecognized algorithm `" ++ e ++ "'")
- . fmap (\v -> o { algos = v : algos o }) $ readEither s
-
-leftMap :: (a -> b) -> Either a c -> Either b c
-leftMap f (Left a) = Left (f a)
-leftMap _ (Right c) = Right c
-
-parseNum :: (Int -> Options) -> String -> Either String Options
-parseNum f = leftMap (\e -> "Invalid numeric argument `" ++ e ++ "'") . fmap f
. readEither
-
-parseN, parseK :: String -> Options -> Either String Options
-parseN s o = parseNum (\n -> o { elems = n }) s
-parseK s o = parseNum (\k -> o { portion = k }) s
-
-readEither :: Read a => String -> Either String a
-readEither s = case reads s of
- [(x,t)] | all isSpace t -> Right x
- _ -> Left s
-
-runTest :: GenIO -> Int -> Int -> Algorithm -> IO ()
-runTest g n k alg = case alg of
- DoNothing -> sortSuite "no algorithm" g n noalgo
- Allocate -> sortSuite "allocate" g n alloc
- InsertionSort -> sortSuite "insertion sort" g n
insertionSort
- IntroSort -> sortSuite "introsort" g n
introSort
- IntroPartialSort -> partialSortSuite "partial introsort" g n k
introPSort
- IntroSelect -> partialSortSuite "introselect" g n k
introSelect
- HeapSort -> sortSuite "heap sort" g n heapSort
- HeapPartialSort -> partialSortSuite "partial heap sort" g n k
heapPSort
- HeapSelect -> partialSortSuite "heap select" g n k
heapSelect
- MergeSort -> sortSuite "merge sort" g n
mergeSort
- RadixSort -> sortSuite "radix sort" g n
radixSort
- AmericanFlagSort -> sortSuite "flag sort" g n flagSort
- TimSort -> sortSuite "tim sort" g n timSort
- _ -> putStrLn $ "Currently unsupported algorithm: " ++ show
alg
-
-mergeSort :: MVector RealWorld Int -> IO ()
-mergeSort v = M.sort v
-{-# NOINLINE mergeSort #-}
-
-introSort :: MVector RealWorld Int -> IO ()
-introSort v = INT.sort v
-{-# NOINLINE introSort #-}
-
-introPSort :: MVector RealWorld Int -> Int -> IO ()
-introPSort v k = INT.partialSort v k
-{-# NOINLINE introPSort #-}
-
-introSelect :: MVector RealWorld Int -> Int -> IO ()
-introSelect v k = INT.select v k
-{-# NOINLINE introSelect #-}
-
-heapSort :: MVector RealWorld Int -> IO ()
-heapSort v = H.sort v
-{-# NOINLINE heapSort #-}
-
-heapPSort :: MVector RealWorld Int -> Int -> IO ()
-heapPSort v k = H.partialSort v k
-{-# NOINLINE heapPSort #-}
-
-heapSelect :: MVector RealWorld Int -> Int -> IO ()
-heapSelect v k = H.select v k
-{-# NOINLINE heapSelect #-}
-
-insertionSort :: MVector RealWorld Int -> IO ()
-insertionSort v = INS.sort v
-{-# NOINLINE insertionSort #-}
-
-radixSort :: MVector RealWorld Int -> IO ()
-radixSort v = R.sort v
-{-# NOINLINE radixSort #-}
-
-flagSort :: MVector RealWorld Int -> IO ()
-flagSort v = AF.sort v
-{-# NOINLINE flagSort #-}
-
-timSort :: MVector RealWorld Int -> IO ()
-timSort v = T.sort v
-{-# NOINLINE timSort #-}
-
-main :: IO ()
-main = getArgs >>= \args -> withSystemRandom $ \gen ->
- case getOpt Permute options args of
- (fs, _, []) -> case foldl (>>=) (Right defaultOptions) fs of
- Left err -> putStrLn $ usageInfo err options
- Right opts | not (usage opts) ->
- mapM_ (runTest gen (elems opts) (portion opts)) (algos opts)
- | otherwise -> putStrLn $ usageInfo
"uvector-algorithms-bench" options
- (_, _, errs) -> putStrLn $ usageInfo (concat errs) options
-
-
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/vector-algorithms-0.7.0.1/bench/simple/Blocks.hs
new/vector-algorithms-0.7.0.4/bench/simple/Blocks.hs
--- old/vector-algorithms-0.7.0.1/bench/simple/Blocks.hs 1970-01-01
01:00:00.000000000 +0100
+++ new/vector-algorithms-0.7.0.4/bench/simple/Blocks.hs 2018-08-24
13:13:24.000000000 +0200
@@ -0,0 +1,62 @@
+{-# LANGUAGE Rank2Types #-}
+
+module Blocks where
+
+import Control.Monad
+import Control.Monad.ST
+
+import Data.Vector.Unboxed.Mutable
+
+import System.CPUTime
+
+import System.Random.MWC (GenIO, Variate(..))
+
+-- Some conveniences for doing evil stuff in the ST monad.
+-- All the tests get run in IO, but uvector stuff happens
+-- in ST, so we temporarily coerce.
+clock :: IO Integer
+clock = getCPUTime
+
+-- Strategies for filling the initial arrays
+rand :: Variate e => GenIO -> Int -> IO e
+rand g _ = uniform g
+
+ascend :: Num e => Int -> IO e
+ascend = return . fromIntegral
+
+descend :: Num e => e -> Int -> IO e
+descend m n = return $ m - fromIntegral n
+
+modulo :: Integral e => e -> Int -> IO e
+modulo m n = return $ fromIntegral n `mod` m
+
+-- This is the worst case for the median-of-three quicksort
+-- used in the introsort implementation.
+medianKiller :: Integral e => e -> Int -> IO e
+medianKiller m n'
+ | n < k = return $ if even n then n + 1 else n + k
+ | otherwise = return $ (n - k + 1) * 2
+ where
+ n = fromIntegral n'
+ k = m `div` 2
+{-# INLINE medianKiller #-}
+
+initialize :: (Unbox e) => MVector RealWorld e -> Int -> (Int -> IO e) -> IO ()
+initialize arr len fill = initial $ len - 1
+ where initial n = fill n >>= unsafeWrite arr n >> when (n > 0) (initial $ n -
1)
+{-# INLINE initialize #-}
+
+speedTest :: (Unbox e) => Int
+ -> (Int -> IO e)
+ -> (MVector RealWorld e -> IO ())
+ -> IO Integer
+speedTest n fill algo = do
+ arr <- new n
+ initialize arr n fill
+ t0 <- clock
+ algo arr
+ t1 <- clock
+ return $ t1 - t0
+{-# INLINE speedTest #-}
+
+
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/vector-algorithms-0.7.0.1/bench/simple/Main.hs
new/vector-algorithms-0.7.0.4/bench/simple/Main.hs
--- old/vector-algorithms-0.7.0.1/bench/simple/Main.hs 1970-01-01
01:00:00.000000000 +0100
+++ new/vector-algorithms-0.7.0.4/bench/simple/Main.hs 2018-08-24
13:13:24.000000000 +0200
@@ -0,0 +1,201 @@
+{-# LANGUAGE Rank2Types #-}
+
+module Main (main) where
+
+import Prelude hiding (read, length)
+import qualified Prelude as P
+
+import Control.Monad.ST
+import Control.Monad.Error
+
+import Data.Char
+import Data.Ord (comparing)
+import Data.List (maximumBy)
+
+import Data.Vector.Unboxed.Mutable
+
+import qualified Data.Vector.Algorithms.Insertion as INS
+import qualified Data.Vector.Algorithms.Intro as INT
+import qualified Data.Vector.Algorithms.Heap as H
+import qualified Data.Vector.Algorithms.Merge as M
+import qualified Data.Vector.Algorithms.Radix as R
+import qualified Data.Vector.Algorithms.AmericanFlag as AF
+import qualified Data.Vector.Algorithms.Tim as T
+
+import System.Environment
+import System.Console.GetOpt
+import System.Random.MWC
+
+import Blocks
+
+-- Does nothing. For testing the speed/heap allocation of the building blocks.
+noalgo :: (Unbox e) => MVector RealWorld e -> IO ()
+noalgo _ = return ()
+
+-- Allocates a temporary buffer, like mergesort for similar purposes as noalgo.
+alloc :: (Unbox e) => MVector RealWorld e -> IO ()
+alloc arr | len <= 4 = arr `seq` return ()
+ | otherwise = (new (len `div` 2) :: IO (MVector RealWorld Int)) >>
return ()
+ where len = length arr
+
+displayTime :: String -> Integer -> IO ()
+displayTime s elapsed = putStrLn $
+ s ++ " : " ++ show (fromIntegral elapsed / 1e12) ++ " seconds"
+
+run :: String -> IO Integer -> IO ()
+run s t = t >>= displayTime s
+
+sortSuite :: String -> GenIO -> Int -> (MVector RealWorld Int -> IO ()) -> IO
()
+sortSuite str g n sort = do
+ putStrLn $ "Testing: " ++ str
+ run "Random " $ speedTest n (rand g >=> modulo n) sort
+ run "Sorted " $ speedTest n ascend sort
+ run "Reverse-sorted " $ speedTest n (descend n) sort
+ run "Random duplicates " $ speedTest n (rand g >=> modulo 1000) sort
+ let m = 4 * (n `div` 4)
+ run "Median killer " $ speedTest m (medianKiller m) sort
+
+partialSortSuite :: String -> GenIO -> Int -> Int
+ -> (MVector RealWorld Int -> Int -> IO ()) -> IO ()
+partialSortSuite str g n k sort = sortSuite str g n (\a -> sort a k)
+
+-- -----------------
+-- Argument handling
+-- -----------------
+
+data Algorithm = DoNothing
+ | Allocate
+ | InsertionSort
+ | IntroSort
+ | IntroPartialSort
+ | IntroSelect
+ | HeapSort
+ | HeapPartialSort
+ | HeapSelect
+ | MergeSort
+ | RadixSort
+ | AmericanFlagSort
+ | TimSort
+ deriving (Show, Read, Enum, Bounded)
+
+data Options = O { algos :: [Algorithm], elems :: Int, portion :: Int, usage
:: Bool } deriving (Show)
+
+defaultOptions :: Options
+defaultOptions = O [] 10000 1000 False
+
+type OptionsT = Options -> Either String Options
+
+options :: [OptDescr OptionsT]
+options = [ Option ['A'] ["algorithm"] (ReqArg parseAlgo "ALGO")
+ ("Specify an algorithm to be run. Options:\n" ++ algoOpts)
+ , Option ['n'] ["num-elems"] (ReqArg parseN "INT")
+ "Specify the size of arrays in algorithms."
+ , Option ['k'] ["portion"] (ReqArg parseK "INT")
+ "Specify the number of elements to partial sort/select
in\nrelevant algorithms."
+ , Option ['?','v'] ["help"] (NoArg $ \o -> Right $ o { usage =
True })
+ "Show options."
+ ]
+ where
+ allAlgos :: [Algorithm]
+ allAlgos = [minBound .. maxBound]
+ algoOpts = fmt allAlgos
+ fmt (x:y:zs) = '\t' : pad (show x) ++ show y ++ "\n" ++ fmt zs
+ fmt [x] = '\t' : show x ++ "\n"
+ fmt [] = ""
+ size = (" " ++) . maximumBy (comparing P.length) . map show $
allAlgos
+ pad str = zipWith const (str ++ repeat ' ') size
+
+parseAlgo :: String -> Options -> Either String Options
+parseAlgo "None" o = Right $ o { algos = [] }
+parseAlgo "All" o = Right $ o { algos = [DoNothing .. AmericanFlagSort] }
+parseAlgo s o = leftMap (\e -> "Unrecognized algorithm `" ++ e ++ "'")
+ . fmap (\v -> o { algos = v : algos o }) $ readEither s
+
+leftMap :: (a -> b) -> Either a c -> Either b c
+leftMap f (Left a) = Left (f a)
+leftMap _ (Right c) = Right c
+
+parseNum :: (Int -> Options) -> String -> Either String Options
+parseNum f = leftMap (\e -> "Invalid numeric argument `" ++ e ++ "'") . fmap f
. readEither
+
+parseN, parseK :: String -> Options -> Either String Options
+parseN s o = parseNum (\n -> o { elems = n }) s
+parseK s o = parseNum (\k -> o { portion = k }) s
+
+readEither :: Read a => String -> Either String a
+readEither s = case reads s of
+ [(x,t)] | all isSpace t -> Right x
+ _ -> Left s
+
+runTest :: GenIO -> Int -> Int -> Algorithm -> IO ()
+runTest g n k alg = case alg of
+ DoNothing -> sortSuite "no algorithm" g n noalgo
+ Allocate -> sortSuite "allocate" g n alloc
+ InsertionSort -> sortSuite "insertion sort" g n
insertionSort
+ IntroSort -> sortSuite "introsort" g n
introSort
+ IntroPartialSort -> partialSortSuite "partial introsort" g n k
introPSort
+ IntroSelect -> partialSortSuite "introselect" g n k
introSelect
+ HeapSort -> sortSuite "heap sort" g n heapSort
+ HeapPartialSort -> partialSortSuite "partial heap sort" g n k
heapPSort
+ HeapSelect -> partialSortSuite "heap select" g n k
heapSelect
+ MergeSort -> sortSuite "merge sort" g n
mergeSort
+ RadixSort -> sortSuite "radix sort" g n
radixSort
+ AmericanFlagSort -> sortSuite "flag sort" g n flagSort
+ TimSort -> sortSuite "tim sort" g n timSort
+ _ -> putStrLn $ "Currently unsupported algorithm: " ++ show
alg
+
+mergeSort :: MVector RealWorld Int -> IO ()
+mergeSort v = M.sort v
+{-# NOINLINE mergeSort #-}
+
+introSort :: MVector RealWorld Int -> IO ()
+introSort v = INT.sort v
+{-# NOINLINE introSort #-}
+
+introPSort :: MVector RealWorld Int -> Int -> IO ()
+introPSort v k = INT.partialSort v k
+{-# NOINLINE introPSort #-}
+
+introSelect :: MVector RealWorld Int -> Int -> IO ()
+introSelect v k = INT.select v k
+{-# NOINLINE introSelect #-}
+
+heapSort :: MVector RealWorld Int -> IO ()
+heapSort v = H.sort v
+{-# NOINLINE heapSort #-}
+
+heapPSort :: MVector RealWorld Int -> Int -> IO ()
+heapPSort v k = H.partialSort v k
+{-# NOINLINE heapPSort #-}
+
+heapSelect :: MVector RealWorld Int -> Int -> IO ()
+heapSelect v k = H.select v k
+{-# NOINLINE heapSelect #-}
+
+insertionSort :: MVector RealWorld Int -> IO ()
+insertionSort v = INS.sort v
+{-# NOINLINE insertionSort #-}
+
+radixSort :: MVector RealWorld Int -> IO ()
+radixSort v = R.sort v
+{-# NOINLINE radixSort #-}
+
+flagSort :: MVector RealWorld Int -> IO ()
+flagSort v = AF.sort v
+{-# NOINLINE flagSort #-}
+
+timSort :: MVector RealWorld Int -> IO ()
+timSort v = T.sort v
+{-# NOINLINE timSort #-}
+
+main :: IO ()
+main = getArgs >>= \args -> withSystemRandom $ \gen ->
+ case getOpt Permute options args of
+ (fs, _, []) -> case foldl (>>=) (Right defaultOptions) fs of
+ Left err -> putStrLn $ usageInfo err options
+ Right opts | not (usage opts) ->
+ mapM_ (runTest gen (elems opts) (portion opts)) (algos opts)
+ | otherwise -> putStrLn $ usageInfo "vector-algorithms-bench"
options
+ (_, _, errs) -> putStrLn $ usageInfo (concat errs) options
+
+
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore'
old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/AmericanFlag.hs
new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/AmericanFlag.hs
--- old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/AmericanFlag.hs
2015-08-12 23:47:36.000000000 +0200
+++ new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/AmericanFlag.hs
2018-08-24 13:13:24.000000000 +0200
@@ -36,6 +36,8 @@
import Control.Monad
import Control.Monad.Primitive
+import Data.Proxy
+
import Data.Word
import Data.Int
import Data.Bits
@@ -51,31 +53,35 @@
import qualified Data.Vector.Algorithms.Insertion as I
+import Foreign.Storable
+
-- | The methods of this class specify the information necessary to sort
-- arrays using the default ordering. The name 'Lexicographic' is meant
-- to convey that index should return results in a similar way to indexing
-- into a string.
class Lexicographic e where
- -- | Given a representative of a stripe and an index number, this
- -- function should determine whether to stop sorting.
- terminate :: e -> Int -> Bool
+ -- | Computes the length of a representative of a stripe. It should take 'n'
+ -- passes to sort values of extent 'n'. The extent may not be uniform across
+ -- all values of the type.
+ extent :: e -> Int
+
-- | The size of the bucket array necessary for sorting es
- size :: e -> Int
+ size :: Proxy e -> Int
-- | Determines which bucket a given element should inhabit for a
-- particular iteration.
index :: Int -> e -> Int
instance Lexicographic Word8 where
- terminate _ n = n > 0
- {-# INLINE terminate #-}
+ extent _ = 1
+ {-# INLINE extent #-}
size _ = 256
{-# INLINE size #-}
index _ n = fromIntegral n
{-# INLINE index #-}
instance Lexicographic Word16 where
- terminate _ n = n > 1
- {-# INLINE terminate #-}
+ extent _ = 2
+ {-# INLINE extent #-}
size _ = 256
{-# INLINE size #-}
index 0 n = fromIntegral $ (n `shiftR` 8) .&. 255
@@ -84,8 +90,8 @@
{-# INLINE index #-}
instance Lexicographic Word32 where
- terminate _ n = n > 3
- {-# INLINE terminate #-}
+ extent _ = 4
+ {-# INLINE extent #-}
size _ = 256
{-# INLINE size #-}
index 0 n = fromIntegral $ (n `shiftR` 24) .&. 255
@@ -96,8 +102,8 @@
{-# INLINE index #-}
instance Lexicographic Word64 where
- terminate _ n = n > 7
- {-# INLINE terminate #-}
+ extent _ = 8
+ {-# INLINE extent #-}
size _ = 256
{-# INLINE size #-}
index 0 n = fromIntegral $ (n `shiftR` 56) .&. 255
@@ -112,8 +118,8 @@
{-# INLINE index #-}
instance Lexicographic Word where
- terminate _ n = n > 7
- {-# INLINE terminate #-}
+ extent _ = sizeOf (0 :: Word)
+ {-# INLINE extent #-}
size _ = 256
{-# INLINE size #-}
index 0 n = fromIntegral $ (n `shiftR` 56) .&. 255
@@ -128,16 +134,16 @@
{-# INLINE index #-}
instance Lexicographic Int8 where
- terminate _ n = n > 0
- {-# INLINE terminate #-}
+ extent _ = 1
+ {-# INLINE extent #-}
size _ = 256
{-# INLINE size #-}
index _ n = 255 .&. fromIntegral n `xor` 128
{-# INLINE index #-}
instance Lexicographic Int16 where
- terminate _ n = n > 1
- {-# INLINE terminate #-}
+ extent _ = 2
+ {-# INLINE extent #-}
size _ = 256
{-# INLINE size #-}
index 0 n = fromIntegral $ ((n `xor` minBound) `shiftR` 8) .&. 255
@@ -146,8 +152,8 @@
{-# INLINE index #-}
instance Lexicographic Int32 where
- terminate _ n = n > 3
- {-# INLINE terminate #-}
+ extent _ = 4
+ {-# INLINE extent #-}
size _ = 256
{-# INLINE size #-}
index 0 n = fromIntegral $ ((n `xor` minBound) `shiftR` 24) .&. 255
@@ -158,8 +164,8 @@
{-# INLINE index #-}
instance Lexicographic Int64 where
- terminate _ n = n > 7
- {-# INLINE terminate #-}
+ extent _ = 8
+ {-# INLINE extent #-}
size _ = 256
{-# INLINE size #-}
index 0 n = fromIntegral $ ((n `xor` minBound) `shiftR` 56) .&. 255
@@ -174,8 +180,8 @@
{-# INLINE index #-}
instance Lexicographic Int where
- terminate _ n = n > 7
- {-# INLINE terminate #-}
+ extent _ = sizeOf (0 :: Int)
+ {-# INLINE extent #-}
size _ = 256
{-# INLINE size #-}
index 0 n = ((n `xor` minBound) `shiftR` 56) .&. 255
@@ -190,8 +196,8 @@
{-# INLINE index #-}
instance Lexicographic B.ByteString where
- terminate b i = i >= B.length b
- {-# INLINE terminate #-}
+ extent = B.length
+ {-# INLINE extent #-}
size _ = 257
{-# INLINE size #-}
index i b
@@ -199,15 +205,43 @@
| otherwise = fromIntegral (B.index b i) + 1
{-# INLINE index #-}
+instance (Lexicographic a, Lexicographic b) => Lexicographic (a, b) where
+ extent (a,b) = extent a + extent b
+ {-# INLINE extent #-}
+ size _ = size (Proxy :: Proxy a) `max` size (Proxy :: Proxy b)
+ {-# INLINE size #-}
+ index i (a,b)
+ | i >= extent a = index i b
+ | otherwise = index i a
+ {-# INLINE index #-}
+
+instance (Lexicographic a, Lexicographic b) => Lexicographic (Either a b) where
+ extent (Left a) = 1 + extent a
+ extent (Right b) = 1 + extent b
+ {-# INLINE extent #-}
+ size _ = size (Proxy :: Proxy a) `max` size (Proxy :: Proxy b)
+ {-# INLINE size #-}
+ index 0 (Left _) = 0
+ index 0 (Right _) = 1
+ index n (Left a) = index (n-1) a
+ index n (Right b) = index (n-1) b
+ {-# INLINE index #-}
+
+-- | Given a representative of a stripe and an index number, this
+-- function determines whether to stop sorting.
+terminate :: Lexicographic e => e -> Int -> Bool
+terminate e i = i >= extent e
+{-# INLINE terminate #-}
+
-- | Sorts an array using the default ordering. Both Lexicographic and
-- Ord are necessary because the algorithm falls back to insertion sort
-- for sufficiently small arrays.
sort :: forall e m v. (PrimMonad m, MVector v e, Lexicographic e, Ord e)
=> v (PrimState m) e -> m ()
-sort v = sortBy compare terminate (size e) index v
- where e :: e
- e = undefined
-{-# INLINE sort #-}
+sort v = sortBy compare terminate (size p) index v
+ where p :: Proxy e
+ p = Proxy
+{-# INLINABLE sort #-}
-- | A fully parameterized version of the sorting algorithm. Again, this
-- function takes both radix information and a comparison, because the
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore'
old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/Common.hs
new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/Common.hs
--- old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/Common.hs
2015-08-12 23:47:36.000000000 +0200
+++ new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/Common.hs
2018-08-24 13:13:24.000000000 +0200
@@ -18,6 +18,7 @@
import Control.Monad.Primitive
import Data.Vector.Generic.Mutable
+import Data.Word (Word)
import qualified Data.Vector.Primitive.Mutable as PV
@@ -46,3 +47,13 @@
| otherwise = return ()
{-# INLINE countLoop #-}
+midPoint :: Int -> Int -> Int
+midPoint a b =
+ toInt $ (toWord a + toWord b) `div` 2
+ where
+ toWord :: Int -> Word
+ toWord = fromIntegral
+
+ toInt :: Word -> Int
+ toInt = fromIntegral
+{-# INLINE midPoint #-}
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore'
old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/Heap.hs
new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/Heap.hs
--- old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/Heap.hs
2015-08-12 23:47:36.000000000 +0200
+++ new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/Heap.hs
2018-08-24 13:13:24.000000000 +0200
@@ -54,7 +54,7 @@
-- | Sorts an entire array using the default ordering.
sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m ()
sort = sortBy compare
-{-# INLINE sort #-}
+{-# INLINABLE sort #-}
-- | Sorts an entire array using a custom ordering.
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m
()
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore'
old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/Insertion.hs
new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/Insertion.hs
--- old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/Insertion.hs
2015-08-12 23:47:36.000000000 +0200
+++ new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/Insertion.hs
2018-08-24 13:13:24.000000000 +0200
@@ -34,7 +34,7 @@
-- | Sorts an entire array using the default comparison for the type
sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m ()
sort = sortBy compare
-{-# INLINE sort #-}
+{-# INLINABLE sort #-}
-- | Sorts an entire array using a given comparison
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m
()
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore'
old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/Intro.hs
new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/Intro.hs
--- old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/Intro.hs
2015-08-12 23:47:36.000000000 +0200
+++ new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/Intro.hs
2018-08-24 13:13:24.000000000 +0200
@@ -56,7 +56,7 @@
import Data.Bits
import Data.Vector.Generic.Mutable
-import Data.Vector.Algorithms.Common (Comparison)
+import Data.Vector.Algorithms.Common (Comparison, midPoint)
import qualified Data.Vector.Algorithms.Insertion as I
import qualified Data.Vector.Algorithms.Optimal as O
@@ -65,7 +65,7 @@
-- | Sorts an entire array using the default ordering.
sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m ()
sort = sortBy compare
-{-# INLINE sort #-}
+{-# INLINABLE sort #-}
-- | Sorts an entire array using a custom ordering.
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m
()
@@ -106,7 +106,7 @@
sort (d-1) l (mid - 1)
where
len = u - l
- c = (u + l) `div` 2
+ c = midPoint u l
{-# INLINE introsort #-}
-- | Moves the least k elements to the front of the array in
@@ -155,7 +155,7 @@
else if m < mid - 1
then go (n-1) l m (mid - 1)
else return ()
- where c = (u + l) `div` 2
+ where c = midPoint u l
{-# INLINE selectByBounds #-}
-- | Moves the least k elements to the front of the array, sorted.
@@ -207,7 +207,7 @@
go (n-1) mid m u
EQ -> isort (n-1) l m
LT -> go n l m (mid - 1)
- where c = (u + l) `div` 2
+ where c = midPoint u l
{-# INLINE partialSortByBounds #-}
partitionBy :: forall m v e. (PrimMonad m, MVector v e)
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore'
old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/Merge.hs
new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/Merge.hs
--- old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/Merge.hs
2015-08-12 23:47:36.000000000 +0200
+++ new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/Merge.hs
2018-08-24 13:13:24.000000000 +0200
@@ -27,7 +27,7 @@
import Data.Bits
import Data.Vector.Generic.Mutable
-import Data.Vector.Algorithms.Common (Comparison, copyOffset)
+import Data.Vector.Algorithms.Common (Comparison, copyOffset, midPoint)
import qualified Data.Vector.Algorithms.Optimal as O
import qualified Data.Vector.Algorithms.Insertion as I
@@ -35,7 +35,7 @@
-- | Sorts an array using the default comparison.
sort :: (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m ()
sort = sortBy compare
-{-# INLINE sort #-}
+{-# INLINABLE sort #-}
-- | Sorts an array using a custom comparison.
sortBy :: (PrimMonad m, MVector v e) => Comparison e -> v (PrimState m) e -> m
()
@@ -60,7 +60,7 @@
loop mid u
merge cmp (unsafeSlice l len src) buf (mid - l)
where len = u - l
- mid = (u + l) `shiftR` 1
+ mid = midPoint u l
{-# INLINE mergeSortWithBuf #-}
merge :: (PrimMonad m, MVector v e)
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore'
old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/Radix.hs
new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/Radix.hs
--- old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/Radix.hs
2015-08-12 23:47:36.000000000 +0200
+++ new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/Radix.hs
2018-08-24 13:13:24.000000000 +0200
@@ -186,7 +186,7 @@
where
e :: e
e = undefined
-{-# INLINE sort #-}
+{-# INLINABLE sort #-}
-- | Radix sorts an array using custom radix information
-- requires the number of passes to fully sort the array,
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore'
old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/Search.hs
new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/Search.hs
--- old/vector-algorithms-0.7.0.1/src/Data/Vector/Algorithms/Search.hs
2015-08-12 23:47:36.000000000 +0200
+++ new/vector-algorithms-0.7.0.4/src/Data/Vector/Algorithms/Search.hs
2018-08-24 13:13:24.000000000 +0200
@@ -39,7 +39,7 @@
import Data.Vector.Generic.Mutable
-import Data.Vector.Algorithms.Common (Comparison)
+import Data.Vector.Algorithms.Common (Comparison, midPoint)
-- | Finds an index in a given sorted vector at which the given element could
-- be inserted while maintaining the sortedness of the vector.
@@ -70,7 +70,7 @@
LT -> loop (k+1) u
EQ -> return k
GT -> loop l k
- where k = (u + l) `shiftR` 1
+ where k = midPoint u l
{-# INLINE binarySearchByBounds #-}
-- | Finds the lowest index in a given sorted vector at which the given element
@@ -136,7 +136,7 @@
loop !l !u
| u <= l = return l
| otherwise = unsafeRead vec k >>= \e -> if p e then loop l k else loop
(k+1) u
- where k = (u + l) `shiftR` 1
+ where k = midPoint u l
{-# INLINE binarySearchPBounds #-}
-- | Given a predicate that is guaranteed to be monotone on the vector elements
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/vector-algorithms-0.7.0.1/tests/properties/Tests.hs
new/vector-algorithms-0.7.0.4/tests/properties/Tests.hs
--- old/vector-algorithms-0.7.0.1/tests/properties/Tests.hs 2015-08-12
23:47:36.000000000 +0200
+++ new/vector-algorithms-0.7.0.4/tests/properties/Tests.hs 2018-08-24
13:13:24.000000000 +0200
@@ -117,15 +117,8 @@
check_permutation = do
qc $ label "introsort" . prop_permutation (INT.sort :: Algo Int ())
- qc $ label "intropartial" . prop_sized (const . prop_permutation)
- (INT.partialSort :: SizeAlgo Int ())
- qc $ label "introselect" . prop_sized (const . prop_permutation)
- (INT.select :: SizeAlgo Int ())
qc $ label "heapsort" . prop_permutation (H.sort :: Algo Int ())
- qc $ label "heappartial" . prop_sized (const . prop_permutation)
- (H.partialSort :: SizeAlgo Int ())
- qc $ label "heapselect" . prop_sized (const . prop_permutation)
- (H.select :: SizeAlgo Int ())
+
qc $ label "mergesort" . prop_permutation (M.sort :: Algo Int ())
qc $ label "timsort" . prop_permutation (T.sort :: Algo Int ())
qc $ label "radix I8" . prop_permutation (R.sort :: Algo Int8 ())
@@ -149,6 +142,17 @@
qc $ label "flag W64" . prop_permutation (AF.sort :: Algo Word64 ())
qc $ label "flag Word" . prop_permutation (AF.sort :: Algo Word ())
qc $ label "flag ByteString" . prop_permutation (AF.sort :: Algo
B.ByteString ())
+{-
+ qc $ label "intropartial" . prop_sized (const . prop_permutation)
+ (INT.partialSort :: SizeAlgo Int ())
+ qc $ label "introselect" . prop_sized (const . prop_permutation)
+ (INT.select :: SizeAlgo Int ())
+ qc $ label "heappartial" . prop_sized (const . prop_permutation)
+ (H.partialSort :: SizeAlgo Int ())
+ qc $ label "heapselect" . prop_sized (const . prop_permutation)
+ (H.select :: Algo Int ())
+-}
+
where
qc prop = quickCheckWith args prop
diff -urN '--exclude=CVS' '--exclude=.cvsignore' '--exclude=.svn'
'--exclude=.svnignore' old/vector-algorithms-0.7.0.1/vector-algorithms.cabal
new/vector-algorithms-0.7.0.4/vector-algorithms.cabal
--- old/vector-algorithms-0.7.0.1/vector-algorithms.cabal 2015-08-12
23:47:36.000000000 +0200
+++ new/vector-algorithms-0.7.0.4/vector-algorithms.cabal 2018-08-24
13:13:24.000000000 +0200
@@ -1,15 +1,17 @@
name: vector-algorithms
-version: 0.7.0.1
+version: 0.7.0.4
license: BSD3
license-file: LICENSE
author: Dan Doel
maintainer: Dan Doel <[email protected]>
+ Erik de Castro Lopo <[email protected]>
copyright: (c) 2008,2009,2010,2011,2012,2013,2014,2015 Dan Doel
(c) 2015 Tim Baumann
-homepage: http://code.haskell.org/~dolio/
+homepage: https://github.com/erikd/vector-algorithms/
category: Data
synopsis: Efficient algorithms for vector arrays
-description: Efficient algorithms for vector arrays
+description: Efficient algorithms for sorting vector arrays. At some
stage
+ other vector algorithms may be added.
build-type: Simple
cabal-version: >= 1.9.2
@@ -36,18 +38,29 @@
description: Enable the quickcheck tests
default: True
+-- flag dump-simpl
+-- description: Dumps the simplified core during compilation
+-- default: False
+
+flag llvm
+ description: Build using llvm
+ default: False
+
source-repository head
- type: darcs
- location: http://hub.darcs.net/dolio/vector-algorithms
+ type: git
+ location: https://github.com/erikd/vector-algorithms/
library
hs-source-dirs: src
build-depends: base >= 4.5 && < 5,
- vector >= 0.6 && < 0.12,
+ vector >= 0.6 && < 0.13,
primitive >=0.3 && <0.7,
bytestring >= 0.9 && < 1.0
+ if ! impl (ghc >= 7.8)
+ build-depends: tagged >= 0.4 && < 0.9
+
exposed-modules:
Data.Vector.Algorithms.Optimal
Data.Vector.Algorithms.Insertion
@@ -63,9 +76,15 @@
Data.Vector.Algorithms.Common
ghc-options:
- -Odph
-funbox-strict-fields
+ -- Cabal/Hackage complains about these
+ -- if flag(dump-simpl)
+ -- ghc-options: -ddump-simpl -ddump-to-file
+
+ if flag(llvm)
+ ghc-options: -fllvm
+
include-dirs:
include
@@ -81,8 +100,8 @@
if flag(InternalChecks)
cpp-options: -DVECTOR_INTERNAL_CHECKS
-executable vector-algorithms-bench
- hs-source-dirs: bench
+executable simple-bench
+ hs-source-dirs: bench/simple
if !flag(bench)
buildable: False
@@ -93,7 +112,14 @@
Blocks
build-depends: base, mwc-random, vector, vector-algorithms, mtl
- ghc-options: -Wall -Odph
+ ghc-options: -Wall
+
+ -- Cabal/Hackage complains about these
+ -- if flag(dump-simpl)
+ -- ghc-options: -ddump-simpl -ddump-to-file
+
+ if flag(llvm)
+ ghc-options: -fllvm
test-suite properties
hs-source-dirs: tests/properties
@@ -115,3 +141,6 @@
QuickCheck >= 2,
vector,
vector-algorithms
+
+ if flag(llvm)
+ ghc-options: -fllvm
