functional-programming - 函数式语言中的质因数分解

Question

我正在用 OCaml 编写，试图提供(某种程度上)高效的质因数分解实现。我认为 2 或更多数字的最佳表示是在指数列表中。为了简单起见，我将按素数的降序进行。所以 2 是 [1]，3 是 [1;0]，4 是 [2]，5 是 [1;0;0]。

我正在考虑使用筛法来取一个数字 n 并寻找 2 和 sqrt(n) 之间所有可能的约数。然后除以任何除数并递归。然而，我能想到的每一个实现似乎都涉及重复搜索列表，这似乎是不必要的低效。我的解决方案的概要最好在这段代码中说明

let rec pf n =
  if (n=2) then ([1], 0)
  else let sq = int_of_float ( (float_of_int n) ** 0.5 ) in
  let primes = getPrimes sq in
  match earliestDiv n primes with
  | None -> n::(zero_list (n-1))
  | Some (x, i) -> let subproblem pf (n/x) in
              increment subproblem i

这里的辅助函数是:

• getPrimes 接受一个 int 并返回所有小于或等于它的素数列表。
• earliestDiv 接受一个整数 n 和一个整数列表 lst，返回一个与 中最早的数字对应的 int*int 选项>lst 划分n。那将是元组的第一个坐标；第二个坐标将返回此素数 x 在素数列表中的索引。
• increment 将采用一个 int 列表和索引，并将索引处的数字增加 1。

所有这些辅助函数都不断地创建列表，并传递列表，等等。事实上，我经常觉得我在做函数式编程。我经常觉得我在不必要地遍历列表，而在命令式语言中我会编写更高效的代码。也许它只是在我的脑海里，当用命令式语言编写时，我很少注意到有多少资源进入了我使用的一些列表操作。但是，如果我遗漏了一些可以防止重复扫描列表的重要技术，我很想听听。

问题:为了编写这个函数，是否有必要重复创建和迭代列表？

Answer 1

如果您最终索引了一个列表，或者用默认元素填充了一个列表直到固定大小，那么列表很可能是错误的数据结构。对于质因数分解，您可能需要一个稀疏数组的实现。 map 将是比固定大小列表更好(如果不是最佳)的实现。