Geek Answers Handbook

Haskell: a comparison of methods for generating combinations

I used to do a few 99 Haskell Problems, and I thought that exercise 27 ("write a function to list possible combinations") was interesting because it is a simple concept and lends itself to multiple implementations.

I was interested in relative performance, so I decided to launch several different implementations - the results are shown in the table below. (For reference: Emacs bash ansi-term on LXDE (Ubuntu 14.04), running on VirtualBox, Thinkpad X220, 8 GB RAM, i5 64 bit 2.4ghz.)

TL DR:

(i) Why are the methods for generating a combination of # 7 and # 8 (from the table below, the code included at the bottom of the message) much faster than the rest?
(ii) Also, what are the actual numbers in the column Bytes?

(i) This is odd because feature # 7 works by filtering the force set (which waaaay is more than a list of combinations); I suspect that this is laziness at work, i.e. What is the function that makes the most effective use of the fact that we only requested the length of the list, not the list itself. (In addition, its “memory usage” is lower than other functions, but again, I’m not sure exactly which metric associated with the memory is displayed.)

# 8: user5402 . .

(ii) Bytes GHCi :set +s; , ~ 25 + HD.)?

enter image description here

:

import Data.List

--algorithms to generate combinations
--time required to compute the following: length $ 13 "abcdefghijklmnopqrstuvwxyz"

--(90.14 secs, 33598933424 bytes)
combDC1 :: (Eq a) => Int -> [a] -> [[a]]
combDC1 n xs = filter (/= []) $ combHelper n n xs []

combHelper :: Int -> Int -> [a] -> [a] -> [[a]]
combHelper n _ []        chosen           = if length chosen == n
                                               then [chosen]
                                               else [[]]
combHelper n i remaining chosen
  | length chosen == n = [chosen]
  | n - length chosen > length remaining = [[]]                     
  | otherwise = combHelper n (i-1) (tail remaining) ((head remaining):chosen) ++
                combHelper n i (tail remaining) chosen

--(167.63 secs, 62756587760 bytes)
combSoln1 :: Int -> [a] -> [([a],[a])]
combSoln1 0 xs = [([],xs)]
combSoln1 n [] = []
combSoln1 n (x:xs) = ts ++ ds
  where
    ts = [ (x:ys,zs) | (ys,zs) <- combSoln1 (n-1) xs ]
    ds = [ (ys,x:zs) | (ys,zs) <- combSoln1 n     xs ]

--(71.40 secs,  30480652480 bytes)
combSoln2 :: Int -> [a] -> [[a]]
combSoln2 0 _  = [ [] ]
combSoln2 n xs = [ y:ys | y:xs' <- tails xs
                           , ys <- combSoln2 (n-1) xs']

--(83.75 secs, 46168207528 bytes)
combSoln3 :: Int -> [a] -> [[a]]
combSoln3 0 _  = return []
combSoln3 n xs = do
  y:xs' <- tails xs
  ys <- combSoln3 (n-1) xs'
  return (y:ys)

--(92.34 secs, 40541644232 bytes)
combSoln4 :: Int -> [a] -> [[a]]
combSoln4 0 _ = [[]]
combSoln4 n xs = [ xs !! i : x | i <- [0..(length xs)-1] 
                               , x <- combSoln4 (n-1) (drop (i+1) xs) ]

--(90.63 secs, 33058536696 bytes)
combSoln5 :: Int -> [a] -> [[a]]
combSoln5 _ [] = [[]]
combSoln5 0 _  = [[]]
combSoln5 k (x:xs) = x_start ++ others
    where x_start = [ x : rest | rest <- combSoln5 (k-1) xs ]
          others  = if k <= length xs then combSoln5 k xs else []


--(61.74 secs, 33053297832 bytes)                                                                         
combSoln6 :: Int -> [a] -> [[a]]
combSoln6 0 _ = [[]]
combSoln6 _ [] = []
combSoln6 n (x:xs) = (map (x:) (combSoln6 (n-1) xs)) ++ (combSoln6 n xs)


--(8.41 secs, 10785499208 bytes)
combSoln7 k ns = filter ((k==).length) (subsequences ns)


--(3.15 secs, 2889815872 bytes)
subsequencesOfSize :: Int -> [a] -> [[a]]
subsequencesOfSize n xs = let l = length xs
                          in if n>l then [] else subsequencesBySize xs !! (l-n)
 where
   subsequencesBySize [] = [[[]]]
   subsequencesBySize (x:xs) = let next = subsequencesBySize xs
                               in zipWith (++) ([]:next) (map (map (x:)) next ++ [[]])
+4
2

, SO-:

n

subsequencesOfSize :: Int -> [a] -> [[a]]
subsequencesOfSize n xs = let l = length xs
                          in if n>l then [] else subsequencesBySize xs !! (l-n)
 where
   subsequencesBySize [] = [[[]]]
   subsequencesBySize (x:xs) = let next = subsequencesBySize xs
                             in zipWith (++) ([]:next) (map (map (x:)) next ++ [[]])

ghci:

ghci> length $ combSoln7   13 "abcdefghijklmnopqrstuvwxyz"
10400600
(13.42 secs, 10783921008 bytes)

ghci> length $ subsequencesOfSize  13 "abcdefghijklmnopqrstuvwxyz"
10400600
(6.52 secs, 2889807480 bytes)
+2
fact :: (Integral a) => a -> a
fact n = product [1..n]

ncombs n k = -- to evaluate number of combinations
    let n' = toInteger n
        k' = toInteger k
    in div (fact n') ((fact k') * (fact (n' - k')))

combinations :: Int -> [a] -> [[a]]
combinations 0 xs = [[]]
combinations 1 xs = [[x] | x <- xs]
combinations n xs =
    let ps = reverse [0..n - 1]
        inc (p:[])
            | pn < length xs = pn:[]
            | otherwise = p:[]
            where pn = p + 1
        inc (p:ps)
            | pn < length xs = pn:ps
            | (head psn) < length xs = inc ((head psn):psn)
            | otherwise = (p:ps)
            where pn = p + 1
                  psn = inc ps
        amount = ncombs (length xs) n
        pointers = take (fromInteger amount) (iterate inc ps)
        c' xs ps = map (xs!!) (reverse ps)
    in map (c' xs) pointers

Haskell . , . , , 6,1 , 3,5 2,9 .

0

More articles:


All Articles