2
\$\begingroup\$

This is the Haskell version of my recursive Fisher-Yates shuffle in JS.

import System.Random

pick :: Int -> [a] -> ([a],[a])
pick _ []     = ([],[])
pick 0 (x:xs) = ([x],xs)
pick i (x:xs) = (,) <$> fst <*> ((x:) . snd) $ pick (i-1) xs

shuffle :: [a] -> IO [a]
shuffle = runner =<< length
          where
          runner :: Int -> [a] -> IO [a]
          runner 0 xs = return xs
          runner i xs = randomRIO (0, i-1) >>= \r -> let (y,ys) = pick r xs
                                                     in (y ++) <$> runner (i-1) ys

The pick function fetches the i'th item in a the list as a singular list alongside a list with the remaining items. ie pick 3 [1,2,3,4,5,6,7] = ([4],[1,2,3,5,6,7]).

Although the above code is a version of the modern method which is claimed to work in O(n) this pretty fast shuffle code still seems to work in exponential time (i think).

Prelude Main> take 10 <$> shuffle [1..100000]
[20141,12487,79977,44600,14825,86744,65941,84737,97850,21214]
(0.57 secs, 334,790,152 bytes)

Prelude Main> take 10 <$> shuffle [1..1000000]
[698377,452503,263121,737622,550957,927399,453318,657374,728367,775039]
(6.81 secs, 3,782,234,776 bytes)

I have two questions.

  1. Can the time complexity improved while using the List type?
  2. I am not fully in control of Haskell's performance gimmicks like unboxed types and such. Can it's performance boosted by means of such Haskell tools or what data type would be the best?
\$\endgroup\$
3
\$\begingroup\$

First, let me ungolf and simplify your code slightly, so it will be easier for me to read:

import System.Random

pick :: Int -> [a] -> (a,[a])
pick 0 (x:xs) = (x, xs)
pick i (x:xs) = let (y,ys) = pick (i-1) xs
                in (y, x:ys)
pick _ []     = error "pick: Invalid index"

shuffle :: [a] -> IO [a]
shuffle lst = runner (length lst) lst
  where
    runner :: Int -> [a] -> IO [a]
    runner 0 xs = return xs
    runner i xs = do
      r <- randomRIO (0, i-1)
      let (y,ys) = pick r xs
      (y:) <$> runner (i-1) ys

Every call to pick is O(i), since you need to iterate through on average half of the array to extract the value and move it to the front. In when calling pick, i is on average equal to n/2 (where n is the length of the list). runner is called recursively n times.

So in conclusion, pick has time complexity O(n) and shuffle has time complexity O(n^2), which is indeed much worse than linear, but not quite exponential as you feared. There are also some minor issues with your functions not being tail recursive, but that should only affect constant factors and memory usage, not complexity.

This also matches your measurements, since 0.57 * 10^2 ≈ 6.81

If you compare it to the modern method which you linked, that code instead uses a swap operation which is O(1), which gives you the promised O(n) complexity.

On a side-note, your javascript version of the algorithm has the same problem, since Array.splice is an O(n) operation.


So, to your questions:

  1. Can we improve the time complexity while using the list type?

    No. Not unless we change the algorithm to something different, which in a way you have already done in both your implementations by not using the swap operation. An O(1) swap operation for lists is not available, since all random access costs O(n). You can however easily fix it in your js-version (see here).

    If you do want to use a different algorithm, there are O(n*log n) algorithms that works on lists, which is not quite linear, but it's the best we can get for lists. You could also use the same algorithm with a Map, which has O(log n) swap operations.

  2. Unboxed types and similar gimmicks will only only help with constant factors, not algorithmic complexity. However, what would help a lot is to use a mutable array or vector. They do have an O(1) swap operation. They come in both an IO version and an ST version which can be used from pure functions.

There are a number of different implementations of a random shuffle function on this page, including Fisher-Yates with both a Map (O(n*log n)) and a mutable Array (O(n)).

\$\endgroup\$
  • 1
    \$\begingroup\$ Thank you, but i guess your code won't compile primarily due to the pick _ [] = ([], []) line. That's basically why i had chosen to return a singleton instead of the head. But anyways, thank again... I suppose i have to use a Vector type and do like fromList and toList \$\endgroup\$ – Redu Nov 24 '19 at 16:53
  • 1
    \$\begingroup\$ Oh, right, I missed that. \$\endgroup\$ – Hjulle Nov 24 '19 at 16:56
  • 1
    \$\begingroup\$ Your answer is great and accepted. The only thing is, i don't like throwing exceptions unless i definitelly need to. I compared the : and ++ versions and they have similar performance. However i will annex a swap version to my JS answer. Thanks for the heads up at there. \$\endgroup\$ – Redu Nov 24 '19 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.