我正在 Haskell 中编写一个函数，它接受两个整数 a 和 b 并计算 [a,b] 的最大子集的长度，使得所有元素互质。现在，这样做的原因是因为我相信调查这些值可能会产生产生微不足道的较小边界的方法(可能大到足以暗示每个推测范围内的实际素数，例如连续的正方形)。所以我很自然地尝试对一些相当大的数字运行它。
不幸的是，下面的代码运行速度不够快，以至于我无法使用它。我认为这个缺陷是 Haskell 的懒惰策略导致的问题，但我既不知道语法也不知道我需要强制执行以防止操作累积的地方。
subsets [] = [[]]
subsets (x:xs) = subsets xs ++ map (x:) (subsets xs)
divides a b = (mod a b == 0)
coprime a b = ((gcd a b) == 1)
mutually_coprime [] = True
mutually_coprime (x:xs) | (coprime_list x xs) = mutually_coprime xs
| otherwise = False
coprime_list _ [] = True
coprime_list a (x:xs) | (coprime a x) = coprime_list a xs
| otherwise = False
coprime_subsets a b = coprime_subsets_helper (subsets [a..b])
coprime_subsets_helper [] = []
coprime_subsets_helper (x:xs) | (mutually_coprime x) = [x] ++ (coprime_subsets_helper xs)
| otherwise = coprime_subsets_helper xs
coprime_subset_length a b = max_element (map list_length (coprime_subsets a b))
list_length [] = 0
list_length (x:xs) = 1 + list_length xs
max_element a = max_element_helper a 0
max_element_helper [] a = a
max_element_helper (x:xs) a | (x > a) = max_element_helper xs x
| otherwise = max_element_helper xs a
只是为了弄清楚这依赖于什么样的输入，“coprime_subsets 100 120”对我来说似乎从来没有停止过。我实际上让它运行，起床，做了一些其他事情，然后再回来。 它还在运行。我怀疑一个大瓶颈是立即计算所有子集。但是，我不想对生成的子集设置人为的下限。这可能会筛选出所有互质集，让我一无所有。
到目前为止我尝试了什么:
我用 gcd 替换了原来的互质函数。最初这对所有整数使用模和迭代检查。我假设 gcd 使用了类似欧几里德算法的东西，理论上应该运行得更快。
我一直在想办法将子集的生成构建到互质集生成器中。到目前为止，我还没有想出任何办法。我也不确定这是否真的有帮助。
我一直在寻找 Haskell 的懒惰政策可能对我造成伤害的任何地方。没有什么突出的，但我敢肯定。
我也知道这可能是我使用的环境 (winhugs) 的效率问题。我会说这就是问题所在；然而，当我在 Math Stack Exchange 上询问如何确定最大子集(对于一般 n 大小的范围)时，我收到的答案表明，从计算上讲，这是一个非常缓慢的计算过程。如果是这样，那很好。我只是希望能够跑完我感兴趣的一些范围，而无需花费几乎永远的时间。
我知道这个网站一般不允许效率；但是，我已经尝试了很多，我不只是想在这里偷懒。我知道 Haskell 有很多奇怪的怪癖，可以迫使它变得看似低效。自从我编写代码以来已经有一段时间了，我怀疑我已经陷入其中一个怪癖。
最佳答案
首先，我们必须找出慢的地方。
处理数字时，应使用提供所需精度和范围的最快表示法。您的代码没有顶级类型签名，因此 GHC 将 coprime_subsets 的类型签名推断为
coprime_subsets :: Integral a => a -> a -> [[a]]
这允许 GHC 为您选择一个 Integral，它会很乐意选择 Integer，这比 Int 慢得多。使用 Integer，程序会花费大量时间来计算 gcds。强制 GHC 使用 Int 将运行时间从 6 秒减少到 1 秒，因为 GHC 可以直接对机器整数进行整数数学运算。
注意:始终提供顶级类型签名也是一种很好的做法。即使编译器没有从中受益，人类也经常这样做。
现在，进入问题的核心。运行
main = print . length $ coprime_subsets (100 :: Int) 120
main :: IO ()
启用分析(stack build --profile for Stack)并将+RTS -p -h传递给可执行文件(-p时间和 -h 空间)给我们一个分割:
COST CENTRE MODULE SRC %time %alloc
subsets Coprime src/Coprime.hs:(4,1)-(5,52) 52.5 100.0
coprime Coprime src/Coprime.hs:11:1-26 25.5 0.0
coprime_list Coprime src/Coprime.hs:(19,1)-(21,41) 18.5 0.0
coprime_subsets_helper Coprime src/Coprime.hs:(27,1)-(29,69) 1.8 0.0
mutually_coprime Coprime src/Coprime.hs:(14,1)-(16,43) 1.7 0.0
当我们使用 Integer 时，绝大多数 (~78%) 的时间都花在了 coprime 测试上。大部分现在都花在了构建 powerset 上，所以让我们先看看那里。
接下来，我们要明白为什么会慢。
通常有三种加速策略:
- 提高其渐近复杂性。
- 改进其常数因子。
- 减少调用它的次数。
哪些可能适用于子集？ (1) 是一个显而易见的选择。构造幂集是 O(2^n)，因此这里的任何渐近改进确实会非常有帮助。我们能找到吗？从理论上讲，我们应该能够。正如 Daniel 所建议的，这个问题等同于最大派系问题，它也是指数级的。然而，最大派系有一个基数较小的解，这意味着我们也应该能够找到这个问题的渐近改进。
降低其渐近复杂性(以及我们调用它的次数)的关键见解是，我们生成绝大多数子集只是为了稍后在检查它们的互素性时将它们丢弃。如果我们可以避免最初生成坏子集，我们将生成更少的子集并执行更少的互素性检查。如果修剪结果的数量与整个计算树的大小成正比，这将产生渐近改进。这种剪枝在函数式算法优化中很常见；你可以在 Richard Bird's sudoku solver 中看到一个有启发性的例子.事实上，如果我们可以编写一个只生成非互质子集的函数，我们就可以解决整个问题!
终于，我们准备好修复它了!
我们可以通过修改原始生成器子集来过滤掉非互质项来做到这一点:
coprimeSubsets [] = [[]]
coprimeSubsets (x:xs)
= coprimeSubsets xs ++ map (x :) (coprimeSubsets (filter (coprime x) xs))
(如果我们仔细考虑的话，我们可以在这里使用一些巧妙的折叠，但显式递归也很好。)
完成此操作后，我们可以在大约 0.1 秒内找到 [100..120] 的互质子集，提高了一个数量级。成本中心报告讲述了这个故事:
COST CENTRE MODULE SRC %time %alloc
MAIN MAIN <built-in> 42.9 0.5
coprimeSubsets Coprime src/Coprime.hs:(33,1)-(35,75) 28.6 67.4
CAF GHC.IO.Encoding <entire-module> 14.3 0.1
coprime Coprime src/Coprime.hs:13:1-26 14.3 31.1
现在我们实际上大部分时间都花在做 IO 之类的事情上。此外，我们的 coprime 测试的调用次数现在仅为 3,848，提高了几个数量级。我们还可以在 3 秒内找到 [100..150] 的互质子集，相比之下……好吧，我没有等它完成，但至少要等几分钟。
下一个寻找加速的地方可能是内存 coprime 函数，因为这个问题涉及多次针对相同的参数计算它。
关于algorithm - 尝试优化此算法/代码以计算 a 和 b 之间互质整数的最大子集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45678702/