| Copyright | (c) Sergey Vinokurov 2023 |
|---|---|
| License | Apache-2.0 (see LICENSE) |
| Maintainer | serg.foo@gmail.com |
| Safe Haskell | Safe-Inferred |
| Language | GHC2021 |
Data.Vector.Algorithms.Quicksort.Median
Description
Synopsis
- class Median (a :: Type) (b :: Type) (m :: Type -> Type) (s :: Type) | a -> b, m -> s where
- selectMedian :: (MVector v b, Ord b) => a -> v s b -> m (MedianResult b)
- data Median3 a = Median3
- data Median3or5 a = Median3or5
- data MedianResult a
- = ExistingValue !a !Int
- | Guess !a
Documentation
class Median (a :: Type) (b :: Type) (m :: Type -> Type) (s :: Type) | a -> b, m -> s where Source #
Median selection algorithm that, given a vector, should come up with an elements that has good chances to be median (i.e to be greater that half the elements and lower than the other remaining half). The closer to the real median the selected element is, the faster quicksort will run and the better parallelisation will be achieved.
Instance can be declared for specific monad. This is useful if we want to select median at random and need to thread random gen.
Parameter meaning;
- a - the median parameter we're defining instance for
- b - type of ellements this median selection method is applicable to
- m - monad the median selection operates in
- s - the same ‘index’ as in ‘ST s’ because vector to be sorted is parameterised and m may need to mention it
Methods
Arguments
| :: (MVector v b, Ord b) | |
| => a | Median algorithm than can carry extra info to be used during median selection (e.g. random generator) |
| -> v s b | Array |
| -> m (MedianResult b) |
Come up with a median value of a given array
Instances
| (PrimMonad m, s ~ PrimState m) => Median (Median3 a) a m s Source # | |
Defined in Data.Vector.Algorithms.Quicksort.Median Methods selectMedian :: (MVector v a, Ord a) => Median3 a -> v s a -> m (MedianResult a) Source # | |
| (PrimMonad m, s ~ PrimState m) => Median (Median3or5 a) a m s Source # | |
Defined in Data.Vector.Algorithms.Quicksort.Median Methods selectMedian :: (MVector v a, Ord a) => Median3or5 a -> v s a -> m (MedianResult a) Source # | |
Pick first, last, and the middle elements and find the one that's between the other two, e.g.
given elements a, b, and c find y among them that satisfies x <= y <= z.
Constructors
| Median3 |
Instances
| (PrimMonad m, s ~ PrimState m) => Median (Median3 a) a m s Source # | |
Defined in Data.Vector.Algorithms.Quicksort.Median Methods selectMedian :: (MVector v a, Ord a) => Median3 a -> v s a -> m (MedianResult a) Source # | |
data Median3or5 a Source #
Pick first, last, and the middle elements, if all of them are
distinct then return median of 3 like Median3 does, otherwise
take median of 5 from the already taken 3 and extra 2 elements at
1/4th and 3/4th of array length.
Constructors
| Median3or5 |
Instances
| (PrimMonad m, s ~ PrimState m) => Median (Median3or5 a) a m s Source # | |
Defined in Data.Vector.Algorithms.Quicksort.Median Methods selectMedian :: (MVector v a, Ord a) => Median3or5 a -> v s a -> m (MedianResult a) Source # | |
data MedianResult a Source #
Median selection result.
Constructors
| ExistingValue !a !Int | Value that was located at specific index in the original array. |
| Guess !a | Value that is a good guess for a real median but may not be present in the array (or we don't know where it's exactly). Good example is to pick first, last, and middle element and average them, which restricts us to dealing with numeric values but may yield good results depending on distribution of values in the array to be sorted. |