Least Free Numbers - Divide and Conquer Algorithm
I am reading the book "Pearls of a Functional Algorithm". Tried implementing the Divide and Transcend solution for the smallest toll 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 it doesn't work any faster than what you might call a "naive" solution. What does
import Data.List ((\\))
minfree' = head . (\\) [0..]
I do not know why this is so, what is wrong with the division and conquest algorithm and how to improve it.
Tried using BangPatterns
by implementing a version partition
that also returns the length of the first list in a tuple, so removes the extra traversal for m =length us
. None of them have improved.
It takes more than 5 seconds first, while the second does it almost instantly in ghci on input [0..9999999]
.
source to share
You have a pathological input that head . (\\) [0..]
takes O (N) time. \\
is defined as follows :
(\\) = foldl (flip delete)
delete x xs
is an O (N) operation that removes the first x
from xs
. foldl (flip delete) xs ys
removes all elements ys
from the xs
.
In [0..] \\ [0..9999999]
we always find that the next item must be removed at the head of the list, so the result can be evaluated in linear time.
If you type minfree' (reverse [0..9999999])
in GHCi instead, it will take quadratic time and you will find that it almost never ends.
On the other hand, a divide and rest algorithm would not slow down the return entry.
source to share