最小的自由数——分而治之算法

Question

我正在读一本书 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

但是这个解决方案的工作速度并不比可能称为 "naive" 解决方案的解决方案快。这是

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

不知道为什么会这样，分治算法有什么问题，如何改进。

尝试使用 BangPatterns，实现 partition 的版本，该版本还 returns 元组中第一个列表的长度，因此它消除了 m =length us 的额外遍历。 None 其中有改进。

第一个需要超过 5 秒，而第二个在 ghci 中几乎立即完成输入 [0..9999999].

Answer 1

您有病理输入，head . (\) [0..] 在 O(N) 时间内执行。 \ 定义为 follows:

(\) =  foldl (flip delete)

delete x xs 是一个 O(N) 操作，它从 xs 中删除第一个 x。 foldl (flip delete) xs ys 将 ys 的所有元素从 xs 中一一删除。

在[0..] \ [0..9999999]中，我们总是在列表的头部找到下一个要删除的元素，所以结果可以在线性时间内评估。

如果您改为在 GHCi 中键入 minfree' (reverse [0..9999999])，这将花费二次方时间，并且您会发现它几乎永远不会完成。

另一方面，分而治之算法不会减慢反向输入的速度。

最小的自由数——分而治之算法

The smallest free number - divide and conquer algorithm

algorithm

haskell

divide-and-conquer