Наименьшее бесплатное число - алгоритм разделяй и властвуй

Я читаю книгу Pearls of Functional Algorithm Design. Пытался реализовать решение по принципу "разделяй и властвуй" для задачи наименьшее свободное число.

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

Но это работает не быстрее решения, которое можно было бы назвать «наивным». Который

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

Я не знаю, почему это так, что не так с алгоритмом «разделяй и властвуй» и как его улучшить.

Пытался использовать BangPatterns, реализовав версию partition, которая также возвращает длину первого списка в кортеже, поэтому исключается дополнительный обход для m =length us. Ни у кого из них не было улучшений.

Первый занимает более 5 секунд, тогда как второй делает это почти мгновенно в ghci на входе [0..9999999].


algorithm haskell divide-and-conquer
person Dulguun Otgon    schedule 16.07.2015    source источник

Ответы (1)


arrow_upward
3
arrow_downward

У вас патологический ввод, на котором head . (\\) [0..] выполняется за время O(N). \\ определяется как следует:

(\\) =  foldl (flip delete)

delete x xs — это операция O(N), которая удаляет первый x из xs. foldl (flip delete) xs ys удаляет все элементы ys из xs один за другим.

В [0..] \\ [0..9999999] мы всегда находим следующий удаляемый элемент в начале списка, поэтому результат можно оценить за линейное время.

Если вы вместо этого наберете minfree' (reverse [0..9999999]) в GHCi, это займет квадратичное время, и вы обнаружите, что оно почти никогда не заканчивается.

С другой стороны, алгоритм «разделяй и властвуй» не будет замедляться при обратном входе.

person András Kovács    schedule 16.07.2015
comment
О, я совершенно пропустил, что minfree работает с неупорядоченным списком, а minfree работает быстро только с упорядоченным списком. - person Dulguun Otgon; 16.07.2015