| Copyright | (c) 2008-2011 Dan Doel (c) Dong Han 2017-2018 |
|---|---|
| License | BSD |
| Maintainer | [email protected] |
| Stability | experimental |
| Portability | non-portable |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
Z.Data.Vector.Sort
Contents
Description
This module provide three stable sorting algorithms, which are:
mergeSort, a O(log(n)) general-purpose sorting algorithms for all different size vectors.insertSorta O(n^2) sorting algorithms suitable for very small vectors.radixSorta O(n) sorting algorithms based onRadixinstance, which is prefered on large vectors.
Sorting is always performed in ascending order. To reverse the order, either use XXSortBy or use Down, RadixDown newtypes. In general changing comparing functions can be done by creating auxiliary newtypes and Ord instances (make sure you inline instance's method for performence!). Or Radix instances in radixSort case, for example:
data Foo = Foo { key :: Int16, ... }
instance Radix Foo where
-- You should add INLINE pragmas to following methods
bucketSize = bucketSize . key
passes = passes . key
radixLSB = radixLSB . key
radix i = radix i . key
radixMSB = radixMSB . key
Synopsis
- mergeSort :: forall v a. (Vec v a, Ord a) => v a -> v a
- mergeSortBy :: forall v a. Vec v a => (a -> a -> Ordering) -> v a -> v a
- mergeTileSize :: Int
- insertSort :: (Vec v a, Ord a) => v a -> v a
- insertSortBy :: Vec v a => (a -> a -> Ordering) -> v a -> v a
- newtype Down a = Down {
- getDown :: a
- radixSort :: forall v a. (Vec v a, Radix a) => v a -> v a
- class Radix a where
- newtype RadixDown a = RadixDown a
- mergeDupAdjacent :: forall v a. (Vec v a, Eq a) => v a -> v a
- mergeDupAdjacentLeft :: forall v a. Vec v a => (a -> a -> Bool) -> v a -> v a
- mergeDupAdjacentRight :: forall v a. Vec v a => (a -> a -> Bool) -> v a -> v a
- mergeDupAdjacentBy :: forall v a. Vec v a => (a -> a -> Bool) -> (a -> a -> a) -> v a -> v a
Sort
mergeSort :: forall v a. (Vec v a, Ord a) => v a -> v a Source #
O(n*log(n)) Sort vector based on element's Ord instance with classic
mergesort algorithm.
This is a stable sort, During sorting two O(n) worker arrays are needed, one of
them will be freezed into the result vector. The merge sort only begin at tile
size larger than mergeTileSize, each tile will be sorted with insertSort, then
iteratively merged into larger array, until all elements are sorted.
mergeSortBy :: forall v a. Vec v a => (a -> a -> Ordering) -> v a -> v a Source #
mergeTileSize :: Int Source #
The mergesort tile size, mergeTileSize = 8.
insertSort :: (Vec v a, Ord a) => v a -> v a Source #
O(n^2) Sort vector based on element's Ord instance with simple
insertion-sort algorithm.
This is a stable sort. O(n) extra space are needed, which will be freezed into result vector.
insertSortBy :: Vec v a => (a -> a -> Ordering) -> v a -> v a Source #
The Down type allows you to reverse sort order conveniently. A value of type
Down aa (represented as Down a
If a has an Ordthen sortWith by .Down x
>>>compare True FalseGT
>>>compare (Down True) (Down False)LT
If a has a BoundedminBoundmaxBound
>>>minBound :: Int-9223372036854775808
>>>minBound :: Down IntDown 9223372036854775807
All other instances of Down aa.
Since: base-4.6.0.0
Instances
| Foldable Down | Since: base-4.12.0.0 |
Defined in Data.Foldable Methods fold :: Monoid m => Down m -> m # foldMap :: Monoid m => (a -> m) -> Down a -> m # foldMap' :: Monoid m => (a -> m) -> Down a -> m # foldr :: (a -> b -> b) -> b -> Down a -> b # foldr' :: (a -> b -> b) -> b -> Down a -> b # foldl :: (b -> a -> b) -> b -> Down a -> b # foldl' :: (b -> a -> b) -> b -> Down a -> b # foldr1 :: (a -> a -> a) -> Down a -> a # foldl1 :: (a -> a -> a) -> Down a -> a # elem :: Eq a => a -> Down a -> Bool # maximum :: Ord a => Down a -> a # | |
| Eq1 Down | Since: base-4.12.0.0 |
| Ord1 Down | Since: base-4.12.0.0 |
Defined in Data.Functor.Classes | |
| Read1 Down | Since: base-4.12.0.0 |
Defined in Data.Functor.Classes | |
| Show1 Down | Since: base-4.12.0.0 |
| Traversable Down | Since: base-4.12.0.0 |
| Applicative Down | Since: base-4.11.0.0 |
| Functor Down | Since: base-4.11.0.0 |
| Monad Down | Since: base-4.11.0.0 |
| NFData1 Down | Since: deepseq-1.4.3.0 |
Defined in Control.DeepSeq | |
| Generic1 Down | |
| Unbox a => Vector Vector (Down a) | |
Defined in Data.Vector.Unboxed.Base Methods basicUnsafeFreeze :: Mutable Vector s (Down a) -> ST s (Vector (Down a)) # basicUnsafeThaw :: Vector (Down a) -> ST s (Mutable Vector s (Down a)) # basicLength :: Vector (Down a) -> Int # basicUnsafeSlice :: Int -> Int -> Vector (Down a) -> Vector (Down a) # basicUnsafeIndexM :: Vector (Down a) -> Int -> Box (Down a) # basicUnsafeCopy :: Mutable Vector s (Down a) -> Vector (Down a) -> ST s () # | |
| Unbox a => MVector MVector (Down a) | |
Defined in Data.Vector.Unboxed.Base Methods basicLength :: MVector s (Down a) -> Int # basicUnsafeSlice :: Int -> Int -> MVector s (Down a) -> MVector s (Down a) # basicOverlaps :: MVector s (Down a) -> MVector s (Down a) -> Bool # basicUnsafeNew :: Int -> ST s (MVector s (Down a)) # basicInitialize :: MVector s (Down a) -> ST s () # basicUnsafeReplicate :: Int -> Down a -> ST s (MVector s (Down a)) # basicUnsafeRead :: MVector s (Down a) -> Int -> ST s (Down a) # basicUnsafeWrite :: MVector s (Down a) -> Int -> Down a -> ST s () # basicClear :: MVector s (Down a) -> ST s () # basicSet :: MVector s (Down a) -> Down a -> ST s () # basicUnsafeCopy :: MVector s (Down a) -> MVector s (Down a) -> ST s () # basicUnsafeMove :: MVector s (Down a) -> MVector s (Down a) -> ST s () # basicUnsafeGrow :: MVector s (Down a) -> Int -> ST s (MVector s (Down a)) # | |
| Data a => Data (Down a) | Since: base-4.12.0.0 |
Defined in Data.Data Methods gfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Down a -> c (Down a) # gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Down a) # toConstr :: Down a -> Constr # dataTypeOf :: Down a -> DataType # dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Down a)) # dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Down a)) # gmapT :: (forall b. Data b => b -> b) -> Down a -> Down a # gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Down a -> r # gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Down a -> r # gmapQ :: (forall d. Data d => d -> u) -> Down a -> [u] # gmapQi :: Int -> (forall d. Data d => d -> u) -> Down a -> u # gmapM :: Monad m => (forall d. Data d => d -> m d) -> Down a -> m (Down a) # gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Down a -> m (Down a) # gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Down a -> m (Down a) # | |
| Storable a => Storable (Down a) | Since: base-4.14.0.0 |
| Monoid a => Monoid (Down a) | Since: base-4.11.0.0 |
| Semigroup a => Semigroup (Down a) | Since: base-4.11.0.0 |
| Bits a => Bits (Down a) | Since: base-4.14.0.0 |
Defined in Data.Ord Methods (.&.) :: Down a -> Down a -> Down a # (.|.) :: Down a -> Down a -> Down a # xor :: Down a -> Down a -> Down a # complement :: Down a -> Down a # shift :: Down a -> Int -> Down a # rotate :: Down a -> Int -> Down a # setBit :: Down a -> Int -> Down a # clearBit :: Down a -> Int -> Down a # complementBit :: Down a -> Int -> Down a # testBit :: Down a -> Int -> Bool # bitSizeMaybe :: Down a -> Maybe Int # shiftL :: Down a -> Int -> Down a # unsafeShiftL :: Down a -> Int -> Down a # shiftR :: Down a -> Int -> Down a # unsafeShiftR :: Down a -> Int -> Down a # rotateL :: Down a -> Int -> Down a # | |
| FiniteBits a => FiniteBits (Down a) | Since: base-4.14.0.0 |
Defined in Data.Ord Methods finiteBitSize :: Down a -> Int # countLeadingZeros :: Down a -> Int # countTrailingZeros :: Down a -> Int # | |
| Bounded a => Bounded (Down a) | Swaps Since: base-4.14.0.0 |
| (Enum a, Bounded a, Eq a) => Enum (Down a) | Swaps Since: base-4.18.0.0 |
Defined in Data.Ord | |
| Floating a => Floating (Down a) | Since: base-4.14.0.0 |
| RealFloat a => RealFloat (Down a) | Since: base-4.14.0.0 |
Defined in Data.Ord Methods floatRadix :: Down a -> Integer # floatDigits :: Down a -> Int # floatRange :: Down a -> (Int, Int) # decodeFloat :: Down a -> (Integer, Int) # encodeFloat :: Integer -> Int -> Down a # significand :: Down a -> Down a # scaleFloat :: Int -> Down a -> Down a # isInfinite :: Down a -> Bool # isDenormalized :: Down a -> Bool # isNegativeZero :: Down a -> Bool # | |
| Generic (Down a) | |
| Ix a => Ix (Down a) | Since: base-4.14.0.0 |
| Num a => Num (Down a) | Since: base-4.11.0.0 |
| Read a => Read (Down a) | This instance would be equivalent to the derived instances of the
Since: base-4.7.0.0 |
| Fractional a => Fractional (Down a) | Since: base-4.14.0.0 |
| Real a => Real (Down a) | Since: base-4.14.0.0 |
Defined in Data.Ord Methods toRational :: Down a -> Rational # | |
| RealFrac a => RealFrac (Down a) | Since: base-4.14.0.0 |
| Show a => Show (Down a) | This instance would be equivalent to the derived instances of the
Since: base-4.7.0.0 |
| NFData a => NFData (Down a) | Since: deepseq-1.4.0.0 |
Defined in Control.DeepSeq | |
| Eq a => Eq (Down a) | Since: base-4.6.0.0 |
| Ord a => Ord (Down a) | Since: base-4.6.0.0 |
| Prim a => Prim (Down a) | Since: primitive-0.6.5.0 |
Defined in Data.Primitive.Types Methods sizeOfType# :: Proxy (Down a) -> Int# # alignmentOfType# :: Proxy (Down a) -> Int# # alignment# :: Down a -> Int# # indexByteArray# :: ByteArray# -> Int# -> Down a # readByteArray# :: MutableByteArray# s -> Int# -> State# s -> (# State# s, Down a #) # writeByteArray# :: MutableByteArray# s -> Int# -> Down a -> State# s -> State# s # setByteArray# :: MutableByteArray# s -> Int# -> Int# -> Down a -> State# s -> State# s # indexOffAddr# :: Addr# -> Int# -> Down a # readOffAddr# :: Addr# -> Int# -> State# s -> (# State# s, Down a #) # writeOffAddr# :: Addr# -> Int# -> Down a -> State# s -> State# s # setOffAddr# :: Addr# -> Int# -> Int# -> Down a -> State# s -> State# s # | |
| Unbox a => Unbox (Down a) | |
Defined in Data.Vector.Unboxed.Base | |
| type Rep1 Down | Since: base-4.12.0.0 |
Defined in GHC.Generics | |
| newtype MVector s (Down a) | |
Defined in Data.Vector.Unboxed.Base | |
| type Rep (Down a) | Since: base-4.12.0.0 |
Defined in GHC.Generics | |
| newtype Vector (Down a) | |
Defined in Data.Vector.Unboxed.Base | |
radixSort :: forall v a. (Vec v a, Radix a) => v a -> v a Source #
O(n) Sort vector based on element's Radix instance with
radix-sort,
(Least significant digit radix sorts variation).
This is a stable sort, one or two extra O(n) worker array are need
depend on how many passes shall be performed, and a bucketSize
counting bucket are also needed. This sort algorithms performed extremly
well on small byte size types such as Int8 or Word8, while on larger
type, constant passes may render this algorithm not suitable for small
vectors (turning point around 2^(2*passes)).
Types contain radixs, which can be inspected with radix during different passes.
The default instances share a same bucketSize 256, which seems to be a good default.
Methods
bucketSize :: a -> Int Source #
The size of an auxiliary array, i.e. the counting bucket
The number of passes necessary to sort an array of es, it equals to the key's byte number.
The radix function used in the first pass, works on the least significant bit.
radix :: Int -> a -> Int Source #
The radix function parameterized by the current pass (0 < pass < passes e-1).
The radix function used in the last pass, works on the most significant bit.
Similar to Down newtype for Ord, this newtype can inverse the order of a Radix
instance when used in radixSort.
Constructors
| RadixDown a |
Instances
merge duplicated
mergeDupAdjacent :: forall v a. (Vec v a, Eq a) => v a -> v a Source #
merge duplicated adjacent element, prefer left element.
Use this function on a sorted vector will have the same effects as nub.
Arguments
| :: forall v a. Vec v a | |
| => (a -> a -> Bool) | equality tester, |
| -> v a | |
| -> v a |
Merge duplicated adjacent element, prefer left element.
mergeDupAdjacentRight Source #
Arguments
| :: forall v a. Vec v a | |
| => (a -> a -> Bool) | equality tester, |
| -> v a | |
| -> v a |
Merge duplicated adjacent element, prefer right element.