vector-algorithms-0.9.1.0: Efficient algorithms for vector arrays

Copyright | (c) 2008-2011 Dan Doel
Maintainer | Dan Doel <dan.doel@gmail.com>
Stability | Experimental
Portability | Non-portable (scoped type variables, bang patterns)
Safe Haskell | None
Language | Haskell2010

Data.Vector.Algorithms.Radix

Description

This module provides a radix sort for a subclass of unboxed arrays. The radix class gives information on * the number of passes needed for the data type

- the size of the auxiliary arrays
- how to compute the pass-k radix of a value

Radix sort is not a comparison sort, so it is able to achieve O(n) run time, though it also uses O(n) auxiliary space. In addition, there is a constant space overhead of 2*size*sizeOf(Int) for the sort, so it is not advisable to use this sort for large numbers of very small arrays.

A standard example (upon which one could base their own Radix instance) is Word32:

- We choose to sort on r = 8 bits at a time
- A Word32 has b = 32 bits total

Thus, b/r = 4 passes are required, 2^r = 256 elements are needed in an auxiliary array, and the radix function is:

    radix k e = (e `shiftR` (k*8)) .&. 255

Synopsis

- sort :: forall e m v. (PrimMonad m, MVector v e, Radix e) => v (PrimState m) e -> m ()
- sortBy :: (PrimMonad m, MVector v e) => Int -> Int -> (Int -> e -> Int) -> v (PrimState m) e -> m ()
- class Radix e where
  - passes :: e -> Int
  - size :: e -> Int
  - radix :: Int -> e -> Int

# Documentation

sort :: forall e m v. (PrimMonad m, MVector v e, Radix e) => v (PrimState m) e -> m () Source #

Sorts an array based on the Radix instance.

sortBy Source #

Arguments

:: (PrimMonad m, MVector v e) |
=> Int | the number of passes
-> Int | the size of auxiliary arrays
-> (Int -> e -> Int) | the radix function
-> v (PrimState m) e | the array to be sorted
-> m () |

Radix sorts an array using custom radix information requires the number of passes to fully sort the array, the size of of auxiliary arrays necessary (should be one greater than the maximum value returned by the radix function), and a radix function, which takes the pass and an element, and returns the relevant radix.

class Radix e where Source #

Methods

passes :: e -> Int Source #

The number of passes necessary to sort an array of es

size :: e -> Int Source #

The size of an auxiliary array

radix :: Int -> e -> Int Source #

The radix function parameterized by the current pass

#### Instances

Instances details

Radix Int16 Source # |
Instance details Defined in Data.Vector.Algorithms.Radix Methods passes :: Int16 -> Int Source # size :: Int16 -> Int Source # radix :: Int -> Int16 -> Int Source #
Radix Int32 Source # |
Instance details Defined in Data.Vector.Algorithms.Radix Methods passes :: Int32 -> Int Source # size :: Int32 -> Int Source # radix :: Int -> Int32 -> Int Source #
Radix Int64 Source # |
Instance details Defined in Data.Vector.Algorithms.Radix Methods passes :: Int64 -> Int Source # size :: Int64 -> Int Source # radix :: Int -> Int64 -> Int Source #
Radix Int8 Source # |
Instance details Defined in Data.Vector.Algorithms.Radix Methods passes :: Int8 -> Int Source # size :: Int8 -> Int Source # radix :: Int -> Int8 -> Int Source #
Radix Word16 Source # |
Instance details Defined in Data.Vector.Algorithms.Radix Methods passes :: Word16 -> Int Source # size :: Word16 -> Int Source # radix :: Int -> Word16 -> Int Source #
Radix Word32 Source # |
Instance details Defined in Data.Vector.Algorithms.Radix Methods passes :: Word32 -> Int Source # size :: Word32 -> Int Source # radix :: Int -> Word32 -> Int Source #
Radix Word64 Source # |
Instance details Defined in Data.Vector.Algorithms.Radix Methods passes :: Word64 -> Int Source # size :: Word64 -> Int Source # radix :: Int -> Word64 -> Int Source #
Radix Word8 Source # |
Instance details Defined in Data.Vector.Algorithms.Radix Methods passes :: Word8 -> Int Source # size :: Word8 -> Int Source # radix :: Int -> Word8 -> Int Source #
Radix Int Source # |
Instance details Defined in Data.Vector.Algorithms.Radix Methods passes :: Int -> Int Source # size :: Int -> Int Source # radix :: Int -> Int -> Int Source #
Radix Word Source # |
Instance details Defined in Data.Vector.Algorithms.Radix Methods passes :: Word -> Int Source # size :: Word -> Int Source # radix :: Int -> Word -> Int Source #
(Radix i, Radix j) => Radix (i, j) Source # |
Instance details Defined in Data.Vector.Algorithms.Radix Methods passes :: (i, j) -> Int Source # size :: (i, j) -> Int Source # radix :: Int -> (i, j) -> Int Source #