欧拉计划 50：算法非常慢，无法理解原因
Project Euler 50: Algorithm is incredibly slow, failing to understand why
我正在使用 Project Euler 来学习 Haskell。我是 Haskell 的新手，在想出一种不会花费大量时间的算法时遇到了很多麻烦。我估计这里的程序需要 14 亿年才能找到解决方案。
问题：
Which prime, below one-million, can be written as the sum of the most
consecutive primes?
这是我的来源。我遗漏了 isPrime。我发布它是因为它解决问题的效率太低了。我认为问题在于 slicedChains 和 primeChains 调用，但我不确定它是什么。我以前用 C++ 解决过这个问题。但无论出于何种原因，Haskell.
中的有效解决方案似乎超出了我的范围
编辑：我已经包含了 isPrime。
import System.Environment (getArgs)
import Data.List (nub,maximumBy)
import Data.Ord (comparing)
isPrime :: Integer -> Bool
isPrime 1 = False
isPrime 2 = True
isPrime x
| any (== 0) (fmap (x `mod`) [2..x-1]) = False
| otherwise = True
primeChain :: Integer -> [Integer]
primeChain x = [ n | n <- 1 : 2 : [3,5..x-1], isPrime n ]
slice :: [a] -> [Int] -> [a]
slice xs args = take (to - from + 1) (drop from xs)
where from = head args
to = last args
subsequencesOfSize :: Int -> [a] -> [[a]]
subsequencesOfSize n xs = let l = length xs
in if n>l then [] else subsequencesBySize xs !! (l-n)
where
subsequencesBySize [] = [[[]]]
subsequencesBySize (x:xs) = let next = subsequencesBySize xs
in zipWith (++) ([]:next) (map (map (x:)) next ++ [[]])
slicedChains :: Int -> [Integer] -> [[Integer]]
slicedChains len xs = nub [x | x <- fmap (xs `slice`) subseqs, length x > 1]
where subseqs = [x | x <- (subsequencesOfSize 2 [1..len]), (last x) > (head x)]
primeSums :: Integer -> [[Integer]]
primeSums x = filter (\ns -> sum ns == x) chain
where xs = primeChain x
len = length xs
chain = slicedChains len xs
compLength :: [[a]] -> [a]
compLength xs = maximumBy (comparing length) xs
cleanSums :: [Integer] -> [[Integer]]
cleanSums xs = fmap (compLength) filtered
where filtered = filter (not . null) (fmap primeSums xs)
main :: IO()
main = do
args <- getArgs
let arg = read (head args) :: Integer
let xs = primeChain arg
print $ maximumBy (comparing length) $ cleanSums xs
你的基本问题是你没有根据你目前找到的最佳解决方案来修剪你的搜索space。
我可以从您使用 maximumBy 来查找最长序列的事实中看出这一点。
例如，如果在搜索过程中找到一个连续的 4 个素数序列，其总和小于 10^6，则您不必检查任何以大于 250000 的素数开头的序列。
要进行这种修剪，您必须跟踪到目前为止找到的解决方案并将候选序列的测试与它们的生成交错进行，以便到目前为止找到的最佳解决方案可以提前停止搜索。
更新
slicedChains 中存在一些效率低下的地方。 Haskell 列表被实现为链表。该视频很好地概述了链表以及它们与数组的区别：(link)
您代码中的以下表达式会出现问题 w.r.t。效率：
* nub 有二次 运行 时间
* length x > 1 - length 的复杂度为 O(n)，其中 n 是列表的长度。更好的写法是：
lengthGreaterThan1 :: [a] -> Bool
lengthGreaterThan1 (_:_:_) = True
lengthGreaterThan1 _ = False
* subsequencesOfSize 2 [1..len] 可能写得更简洁：
[ [a,b] | a <- [1..len], b <- [a+1..len] ]
这也将确保 a < b.
* slice 中的 take 和 drop 调用也是 O(n)
* 在 primeSums 中，对 primeChain 的调用将一遍又一遍地重新生成本质上相同的列表，从而导致对 [= 的多次调用25=]。更好的方法是像这样定义 primeChain：
allPrimes = filter isPrime [1..]
primeChain x = takeWhile (<= x) allPrimes
列表 allPrimes 将生成一次，primeChain 只需使用该列表的前缀。
* primeSums x负责找和正好x的序列，但是它看的序列很多那不可能行得通。例如，primeSums 31 将检查：
11 + 13 + 17, 11 + 13 + 17 + 23, 11 + 13 + 17 + 23 + 29,
17 + 19, 17 + 19 + 23, 17 + 19 + 23 + 29,
19 + 23, 19 + 23 + 29
23 + 29
尽管很明显 none 这些总和可能等于 31。
所以你首先需要的是一个好的数据结构：一旦你找到一个长度为 n 的序列，你就不会关心更短长度的序列，所以你的主要需求是：（1）跟踪求和，(2) 追踪集合中的素数，(3) 移除最小元素，(4) 添加一个新的最大元素。关键是 摊销 ，其中支付大笔费用的频率不高，以至于您可以假装每次手术的费用很小。数据结构如下所示：
data Queue x = Q [x] [x]
q_empty (Q [] []) = True
q_empty _ = False
q_headtails (Q (x:xs) rest) = (x, Q xs rest)
q_headtails (Q [] xs) = case reverse xs of y:ys -> (y, Q ys [])
[] -> error "End of queue."
q_append el (Q beg end) = Q beg (el:end)
所以解构列表是可能的，但有时会触发 O(n) 操作，但这没关系，因为当它发生时，我们不必再执行 n 个步骤，所以它平均每步进行一次操作。 （您可能还想使用脊柱严格列表来完成此操作。）
为了节省长度操作并对列表项求和，您可能也想缓存它们：
type Length = Int
type Sum = Int
type Prime = Int
data PrimeSeq = PS Length Sum (Queue Prime)
headTails (PS len sum q) = (x, PS (len - 1) (sum - x) xs)
where (x, xs) = q_headtails q
append x (PS len sum xs) = PS (len + 1) (sum + x) (q_append x xs)
这些算法看起来像：
- 缓存您开始使用的 PrimeSeq 副本
- 继续向其添加素数并测试素数，直到达到 10^6。
- 如果您发现一个序列更长的新素数，请更换缓存。
- 每当您 运行 进入 10^6 时，恢复到缓存，从队列的前面拉出一个素数，然后根据需要重复。
你的素数生成是二次的（isPrime 101 测试 rem 101 100 == 0 即使 10 是 101[=53 的最大数字=] 需要测试——实际上 7 就足够了）。
然而即使有了它，一个足够简单的基于列表的代码在2 秒（在 Intel Core i7 2.5 GHz 上，在 GHCi 中解释）。并且通过更正代码以利用上述优化（此外，仅通过素数进行测试），它需要 0.1s.
此外，f x | t = False | otherwise = True 与 f x = not t 相同。
PE 站点要求我们不要给您任何提示。
但总的来说，由于其惰性，Haskell 中效率的关键是生成尽可能小的重复劳动。作为一个例子，我们可以将它们作为一个过程的一部分一起生成，而不是单独计算列表的每个切片，
slices :: Int -> [a] -> [[a]]
slices n = map (take n) . iterate tail -- sequence of list's slices of length n each
还有一个原则就是，尽量解决一个比较一般的问题，你就是一个例子
编写了这样一个函数后，我们可以通过尝试为其参数设置不同的值（从小到大）来使用它，以探索解决问题的方式。我们被告知 21 个连续素数。其中 22 个呢？ 27？ 1127 个？ ...我已经说得够多了。
如果它开始花费太多时间，我们可以通过 empirical orders of growth 分析评估完整解决方案所需的 运行 时间。
虽然使用未优化的 isPrime 代码可以很快找到解决方案，但探索过程可能会慢得令人望而却步，但使用优化代码就足够快了：
primes :: [Int]
primes = 2 : filter isPrime [3,5..]
isPrime n = and [rem n p > 0 | p <- takeWhile ((<= n).(^2)) primes]
我正在使用 Project Euler 来学习 Haskell。我是 Haskell 的新手，在想出一种不会花费大量时间的算法时遇到了很多麻烦。我估计这里的程序需要 14 亿年才能找到解决方案。
问题：
Which prime, below one-million, can be written as the sum of the most consecutive primes?
这是我的来源。我遗漏了 isPrime。我发布它是因为它解决问题的效率太低了。我认为问题在于 slicedChains 和 primeChains 调用，但我不确定它是什么。我以前用 C++ 解决过这个问题。但无论出于何种原因，Haskell.
中的有效解决方案似乎超出了我的范围编辑：我已经包含了 isPrime。
import System.Environment (getArgs)
import Data.List (nub,maximumBy)
import Data.Ord (comparing)
isPrime :: Integer -> Bool
isPrime 1 = False
isPrime 2 = True
isPrime x
| any (== 0) (fmap (x `mod`) [2..x-1]) = False
| otherwise = True
primeChain :: Integer -> [Integer]
primeChain x = [ n | n <- 1 : 2 : [3,5..x-1], isPrime n ]
slice :: [a] -> [Int] -> [a]
slice xs args = take (to - from + 1) (drop from xs)
where from = head args
to = last args
subsequencesOfSize :: Int -> [a] -> [[a]]
subsequencesOfSize n xs = let l = length xs
in if n>l then [] else subsequencesBySize xs !! (l-n)
where
subsequencesBySize [] = [[[]]]
subsequencesBySize (x:xs) = let next = subsequencesBySize xs
in zipWith (++) ([]:next) (map (map (x:)) next ++ [[]])
slicedChains :: Int -> [Integer] -> [[Integer]]
slicedChains len xs = nub [x | x <- fmap (xs `slice`) subseqs, length x > 1]
where subseqs = [x | x <- (subsequencesOfSize 2 [1..len]), (last x) > (head x)]
primeSums :: Integer -> [[Integer]]
primeSums x = filter (\ns -> sum ns == x) chain
where xs = primeChain x
len = length xs
chain = slicedChains len xs
compLength :: [[a]] -> [a]
compLength xs = maximumBy (comparing length) xs
cleanSums :: [Integer] -> [[Integer]]
cleanSums xs = fmap (compLength) filtered
where filtered = filter (not . null) (fmap primeSums xs)
main :: IO()
main = do
args <- getArgs
let arg = read (head args) :: Integer
let xs = primeChain arg
print $ maximumBy (comparing length) $ cleanSums xs
你的基本问题是你没有根据你目前找到的最佳解决方案来修剪你的搜索space。
我可以从您使用 maximumBy 来查找最长序列的事实中看出这一点。
例如，如果在搜索过程中找到一个连续的 4 个素数序列，其总和小于 10^6，则您不必检查任何以大于 250000 的素数开头的序列。
要进行这种修剪，您必须跟踪到目前为止找到的解决方案并将候选序列的测试与它们的生成交错进行，以便到目前为止找到的最佳解决方案可以提前停止搜索。
更新
slicedChains 中存在一些效率低下的地方。 Haskell 列表被实现为链表。该视频很好地概述了链表以及它们与数组的区别：(link)
您代码中的以下表达式会出现问题 w.r.t。效率：
* nub 有二次 运行 时间
* length x > 1 - length 的复杂度为 O(n)，其中 n 是列表的长度。更好的写法是：
lengthGreaterThan1 :: [a] -> Bool
lengthGreaterThan1 (_:_:_) = True
lengthGreaterThan1 _ = False
* subsequencesOfSize 2 [1..len] 可能写得更简洁：
[ [a,b] | a <- [1..len], b <- [a+1..len] ]
这也将确保 a < b.
* slice 中的 take 和 drop 调用也是 O(n)
* 在 primeSums 中，对 primeChain 的调用将一遍又一遍地重新生成本质上相同的列表，从而导致对 [= 的多次调用25=]。更好的方法是像这样定义 primeChain：
allPrimes = filter isPrime [1..]
primeChain x = takeWhile (<= x) allPrimes
列表 allPrimes 将生成一次，primeChain 只需使用该列表的前缀。
* primeSums x负责找和正好x的序列，但是它看的序列很多那不可能行得通。例如，primeSums 31 将检查：
11 + 13 + 17, 11 + 13 + 17 + 23, 11 + 13 + 17 + 23 + 29,
17 + 19, 17 + 19 + 23, 17 + 19 + 23 + 29,
19 + 23, 19 + 23 + 29
23 + 29
尽管很明显 none 这些总和可能等于 31。
所以你首先需要的是一个好的数据结构：一旦你找到一个长度为 n 的序列，你就不会关心更短长度的序列，所以你的主要需求是：（1）跟踪求和，(2) 追踪集合中的素数，(3) 移除最小元素，(4) 添加一个新的最大元素。关键是 摊销 ，其中支付大笔费用的频率不高，以至于您可以假装每次手术的费用很小。数据结构如下所示：
data Queue x = Q [x] [x]
q_empty (Q [] []) = True
q_empty _ = False
q_headtails (Q (x:xs) rest) = (x, Q xs rest)
q_headtails (Q [] xs) = case reverse xs of y:ys -> (y, Q ys [])
[] -> error "End of queue."
q_append el (Q beg end) = Q beg (el:end)
所以解构列表是可能的，但有时会触发 O(n) 操作，但这没关系，因为当它发生时，我们不必再执行 n 个步骤，所以它平均每步进行一次操作。 （您可能还想使用脊柱严格列表来完成此操作。）
为了节省长度操作并对列表项求和，您可能也想缓存它们：
type Length = Int
type Sum = Int
type Prime = Int
data PrimeSeq = PS Length Sum (Queue Prime)
headTails (PS len sum q) = (x, PS (len - 1) (sum - x) xs)
where (x, xs) = q_headtails q
append x (PS len sum xs) = PS (len + 1) (sum + x) (q_append x xs)
这些算法看起来像：
- 缓存您开始使用的 PrimeSeq 副本
- 继续向其添加素数并测试素数，直到达到 10^6。
- 如果您发现一个序列更长的新素数，请更换缓存。
- 每当您 运行 进入 10^6 时，恢复到缓存，从队列的前面拉出一个素数，然后根据需要重复。
你的素数生成是二次的（isPrime 101 测试 rem 101 100 == 0 即使 10 是 101[=53 的最大数字=] 需要测试——实际上 7 就足够了）。
然而即使有了它，一个足够简单的基于列表的代码在2 秒（在 Intel Core i7 2.5 GHz 上，在 GHCi 中解释）。并且通过更正代码以利用上述优化（此外，仅通过素数进行测试），它需要 0.1s.
此外，f x | t = False | otherwise = True 与 f x = not t 相同。
PE 站点要求我们不要给您任何提示。
但总的来说，由于其惰性，Haskell 中效率的关键是生成尽可能小的重复劳动。作为一个例子，我们可以将它们作为一个过程的一部分一起生成，而不是单独计算列表的每个切片，
slices :: Int -> [a] -> [[a]]
slices n = map (take n) . iterate tail -- sequence of list's slices of length n each
还有一个原则就是，尽量解决一个比较一般的问题，你就是一个例子
编写了这样一个函数后，我们可以通过尝试为其参数设置不同的值（从小到大）来使用它，以探索解决问题的方式。我们被告知 21 个连续素数。其中 22 个呢？ 27？ 1127 个？ ...我已经说得够多了。
如果它开始花费太多时间，我们可以通过 empirical orders of growth 分析评估完整解决方案所需的 运行 时间。
虽然使用未优化的 isPrime 代码可以很快找到解决方案，但探索过程可能会慢得令人望而却步，但使用优化代码就足够快了：
primes :: [Int]
primes = 2 : filter isPrime [3,5..]
isPrime n = and [rem n p > 0 | p <- takeWhile ((<= n).(^2)) primes]