algorithm - 功能性学习困境

Question

我是函数式语言的初学者，我正试图在 Haskell 中完成所有事情。这是一个快速而简单的函数，可以找到一个数的所有因数:

factors :: (Integral a) => a -> [a]
factors x = filter (\z -> x `mod` z == 0) [2..x `div` 2]

工作正常，但我发现它对于大量数据来说太慢了。所以我让自己变得更好:

factorcalc :: (Integral a) => a -> a -> [a] -> [a]
factorcalc x y z
    | y `elem` z      = sort z
    | x `mod` y == 0  = factorcalc x (y+1) (z ++ [y] ++ [(x `div` y)])
    | otherwise       = factorcalc x (y+1) z

但这就是我的问题:即使代码有效，并且可以减少我程序的执行时间，但它太可怕了!

它散发着丑陋的命令式思维的味道:它在循环中不断更新计数器和数据结构，直到完成。由于您无法在纯函数式编程中更改状态，因此我通过将数据保存在参数中来作弊，函数只是一遍又一遍地将这些数据传递给自身。

我可能是错的，但一定有更好的方法来做同样的事情......

Answer 1

请注意，原始问题询问的是所有 因素，而不仅仅是主要 因素。主要因素少得多，可能可以更快地找到它们。也许这就是 OQ 想要的。也许不是。但让我们解决最初的问题，把“乐趣”放回“功能”!

一些观察:

• 这两个函数不会产生相同的输出——如果 x 是一个完全平方，则第二个函数包括两次平方根。

• 第一个函数 enumerates 检查与 x 的大小成比例的一些潜在因素；第二个函数仅检查与x 的平方根 成正比，然后停止(存在上述错误)。

• 第一个函数 (factors) 分配一个列表，其中包含从 2 到 n div 2 的所有整数，其中第二个函数从不分配列表，而是访问更少 参数中一次一个整数。我使用 -O 运行优化器并使用 -ddump-simpl 查看输出，GHC 不够智能，无法优化这些分配。

• factorcalc 是尾递归的，这意味着它编译成一个紧密的机器代码循环； filter 不是也不是。

一些实验表明平方根是 killer :

下面是一个生成 x 从 z 到 2 的因数的示例函数:

factors_from x 1 = []
factors_from x z 
  | x `mod` z == 0 = z : factors_from x (z-1)
  | otherwise      =     factors_from x (z-1)

factors'' x = factors_from x (x `div` 2)

它快一点，因为它不分配，但它仍然不是尾递归的。

这是一个更忠实于原始版本的尾递归版本:

factors_from' x 1 l = l
factors_from' x z l
  | x `mod` z == 0 = factors_from' x (z-1) (z:l)
  | otherwise      = factors_from' x (z-1) l

factors''' x = factors_from x (x `div` 2)

这仍然比 factorcalc 慢，因为它枚举了从 2 到 x div 2 的所有整数，而 factorcalc 停止在平方根处.

有了这些知识，我们现在可以创建一个功能更强大的 factorcalc 版本，它可以复制它的速度和错误:

factors'''' x = sort $ uncurry (++) $ unzip $ takeWhile (uncurry (<=)) $ 
                [ (z, x `div` z) | z <- [2..x], x `mod` z == 0 ]

我没有准确计时，但输入 1 亿，它和 factorcalc 都会立即终止，而其他的都需要几秒钟。

该函数如何工作以及为什么工作留给读者作为练习:-)

---

附录:好的，为了减轻眼球出血，这里有一个稍微更理智的版本(并且没有错误):

saneFactors x = sort $ concat $ takeWhile small $
                [ pair z | z <- [2..], x `mod` z == 0 ]
    where pair z = if z * z == x then [z] else [z, x `div` z]
          small [z, z'] = z < z'
          small [z]     = True