1

我已经为 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超过n40000 时，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
4

1 回答 1

2

在实施欧拉乘积公式时：

欧拉乘积公式

您可以利用您正在计算范围内所有数字的 Euler Phi 数的事实[1..n]

这样做，您可能首先找到范围内的所有素数，[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]

将是前 20 个数字的欧拉函数；如果你用flag编译，-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
于 2016-02-08T22:46:59.420 回答