Totient-function generating sieve 消耗太多内存

Question

我已经为 totients 列表编写了一个基于筛子的生成器，并希望总和达到 1000000。

applyEvery :: (a -> a) -> Int -> [a] -> [a]
applyEvery f n xs = xf ++ (\(y:ys) -> f y : applyEvery f n ys) xb
  where
    (xf, xb) = splitAt (n - 1) xs

totients :: [Int]
totients = 1 : sieve [2..] [2..]
  where 
    sieve (x:xs) (y:ys) 
        | x == y    = (y - 1) : sieve xs (propagatePrime x ys)  
        | otherwise = y : sieve xs ys
    propagatePrime j = applyEvery (\x -> (quot x j)*(j - 1)) j

totientSum :: Int -> Int
totientSum n = sum $ take n totients

当 totientSum n 计算 n 超过 40000 时，ghci 需要很长时间来评估并开始消耗大量内存。编译为可执行文件无济于事。我认为这与 Haskell 处理惰性求值的方式有关。

我想知道是否可以选择性地应用严格性来改善上述函数的内存消耗，以便我可以计算总和高达 1000000。我还想知道是否有更好的方法这使用列表，或者我是否应该使用随机访问数据结构。如果您知道计算总和的更快算法，请分享参考。

我认为 applyEvery 的定义可能会有所不同，所以我尝试了以下其他实现，但它们似乎都比上面使用的定义消耗更多的内存。

-- <https://www.reddit.com/2tpqip/>
applyEvery' :: (a -> a) -> Int -> [a] -> [a]
applyEvery' f n = zipWith ($) (cycle (replicate (n - 1) id ++ [f]))

applyEvery'' :: (a -> a) -> Int -> [a] -> [a]
applyEvery'' f n xs = xf ++ (\(y:ys) -> f y : applyEvery'' f n ys) xb
  where
    xf = take (n - 1) xs
    xb = drop (n - 1) xs

Answer 1

正在实施Euler product formula:

您可以利用以下事实：您正在为 [1..n]

范围内的所有数字计算 Euler Phi 数

这样做，您可能会先找到范围 [1..n] 中的所有质数，然后 不是找到每个数的质因数，而是找到每个质数的所有倍数 .显然，后者可以更有效地完成。

一个可能的实现是：

import Data.Int (Int64)
import Control.Applicative ((<$>))
import Data.Array.Unboxed (UArray, elems, accum, listArray)

primes :: Integral a => [a]
primes = 2: 3: filter pred (chain [5,11..] [7,13..])
    where
    chain (x:xs) (y:ys) = x: y: chain xs ys
    pred a = all (\i -> a `mod` i /= 0) $ takeWhile (\i -> i * i <= a) primes

euler_phi :: Int64 -> [Int64]
euler_phi n = elems $ accum (\a p -> a - a `div` p) arr inc
    where
    val = takeWhile (<= n) primes
    idx = map (\i -> takeWhile (<= n) [i,2 * i..]) val

    inc = concat $ zipWith (\i j -> ($j) <$> (,) <$> i) idx val
    arr = listArray (1, n) [1..n] :: UArray Int64 Int64

main = getLine >>= print . sum . euler_phi . read

然后：

\> euler_phi 20
[1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8,16,6,18,8]

将是 Euler totient function for the first 20 numbers；如果你用-O2标志编译，你可能会以相当不错的性能计算累积和：

$ ghc --make -O2 euler_phi.hs
[1 of 1] Compiling Main             ( euler_phi.hs, euler_phi.o )
Linking euler_phi ...

$ time echo 40000 | ./euler_phi
486345716

real    0m0.091s
user    0m0.040s
sys     0m0.006s

Totient-function generating sieve 消耗太多内存

Totient-function generating sieve consuming too much memory

memory

haskell

sieve