Haskell - The smallest free number - divide and conquer algorithm

Questions

I m reading a book Pearls of Functional Algorithm Design . Tried implementing the divide and conquer solution for smallest free number problem.

minfree xs = minfrom 0 (length xs) xs

minfrom a 0 _  = a
minfrom a n xs = if m == b - a
                    then minfrom b (n-m) vs
                    else minfrom a (m)   us
    where b = a + 1 + (n `div` 2)
          (us,vs) = partition (<b) xs
          m = length us

But this one works no faster than the solution that one might call "naive" solution. Which is

import Data.List ((\))
minfree  = head . (\) [0..]

I don t know why this is like this, what s wrong with the divide and conquer algorithm and how to improve it.

Tried using BangPatterns, implementing the version of partition that also returns first list s length in the tuple, so it eliminates additional traversal for m =length us. None of them made improvement.

First one takes more than 5 seconds, whereas second one does it almost instantly in ghci on input [0..9999999].

Answers

https://hackage.haskell.org/package/base-4.8.0.0/docs/src/Data-OldList.html https://hackage.haskell.org/package/base-4.8.0.0/docs/src/Data-OldList.html

(\) =  foldl (flip delete)

delete x xs is an O(N) operation that removes the first x from xs. foldl (flip delete) xs ys deletes all elements of ys from xs one by one.

In [0..] \ [0..9999999], we always find the next element to be deleted at the head of the list, so the result can be evaluated in linear time.

If you instead type minfree (reverse [0..9999999]) into GHCi, that takes quadratic time and you find that it pretty much never finishes.

The divide-and-conquer algorithm on the other hand would not slow down on the reversed input.

Source

License : cc by-sa 3.0

http://stackoverflow.com/questions/31446342/the-smallest-free-number-divide-and-conquer-algorithm

Related