Partition



In [1]:

    
import Data.List (foldl')

This implementation should be ~O(2N):



In [2]:

    
partition :: (Ord a) => [a] -> a -> [a]
partition xs pivot =
    [ x | x <- xs, x < pivot] ++ [ x | x <- xs, x >= pivot]

This implementation should be ~O(N):



In [3]:

    
partition' :: (Ord a) => [a] -> a -> [a]
partition' xs pivot =
    let
        computeState (left, right) x =
            if x < pivot then
                (x : left , right)
            else
                (left, x : right)
    in
        uncurry (++) $ foldl' computeState ([], []) xs



In [4]:

    
partition [3, 5, 8, 5, 10, 2, 1] 5
partition' [3, 5, 8, 5, 10, 2, 1] 5









    





[3,2,1,5,8,5,10]






    





[1,2,3,10,5,8,5]

Benchmarks



In [5]:

    
import System.TimeIt
import System.Random



In [6]:

    
sampleSize = 10000000

testRandom = take sampleSize $ randoms (mkStdGen 0)
testOrdered = [1..sampleSize]



In [7]:

    
length . show $ testOrdered

timeIt $ print $ length . show $ partition testOrdered (sampleSize `div` 2)
timeIt $ print $ length . show $ partition' testOrdered (sampleSize `div` 2)









    





78888898






    





78888898
CPU time:   8.97s






    





78888898
CPU time:   6.18s

Observe branch prediction effects!



In [8]:

    
length . show $ testRandom

timeIt $ print $ length . show $ partition testRandom 0
timeIt $ print $ length . show $ partition' testRandom 0









    





203793565






    





203793565
CPU time:  25.49s






    





203793565
CPU time:  22.87s