通常情况下,Richard Bird在筛选法求素数时的定义是自我引用的:
import Data.List.Ordered (minus, union, unionAll)
ps = 2 : minus [3..]
(foldr (\p r -> p*p : union [p*p+p, p*p+2*p..] r) [] ps)
这个定义产生的质数
ps
被用作输入。为了避免“恶性循环”,该定义以初始值2为基础进行改进。这对应于 Eratosthenes 筛法的数学定义,即在合数之间的空隙中找到质数,由每个质数
p 的计数步骤枚举。
P = { 2 } ∪ ( { 3,4,5,... } \ ⋃p in P { p2, p2+p, p2+2p, ... } )
所产生的流被用作其自身定义的输入。这导致整个质数流保留在内存中(或者至少大部分)。这里的固定点是“共享”、“核递归”的概念。
fix f = xs where xs = f xs
ps = fix ((2:) . minus [3..] . foldr (...) [])
这个想法(由Melissa O'Neill提出)是将其分成两个流,其中一个内部循环将进入第二个“上面”的质数流:
fix2 f = f xs where xs = f xs
ps2 = fix2 ((2:) . minus [3..] . foldr (...) [])
因此,当
ps2
生成某个质数
p
时,其内部流
xs
的
“核心”质数只需要实例化到大约
sqrt p
,任何由
ps2
生成的质数都可以被系统立即丢弃和垃圾回收:
\
\
<- ps2 <-.
\
\
<- xs <-.
/ \
\_________/
内部循环xs
生成的质数不能立即丢弃,因为它们对xs
流本身是必要的。当xs
生成一个质数q
时,只有在它被foldr
部分消耗后才能丢弃其下面部分的内容,也就是在其被它的消费者(如print
)消耗时,该序列会维护指向其自身的后向指针,直到其最大产生值的sqrt
()。
因此,只使用一个反馈循环(使用
fix
)几乎需要将整个序列保留在内存中,而使用双重反馈(使用
fix2
)仅需要大部分保留内部循环,该内部循环仅达到主流产生的当前值的平方根。因此,总体空间复杂度从约
O(N)降低到约
O(sqrt(N))--大幅降低。
为使此方法奏效,代码必须使用优化编译,即使用-O2
开关,并独立运行。您还可能需要使用-fno-cse
开关。测试代码中只能有对ps2
的一个引用:
main = getLine >>= (read >>> (+(-1)) >>> (`drop` ps2) >>> print . take 5)
实际上,在Ideone测试时,
它确实显示几乎恒定的内存消耗。
重申一下,它是埃拉托斯特尼筛法,而不是欧拉筛法。
最初的定义如下:
eratos (x:xs) = x : eratos (minus xs $ map (*x) [x..] )
eulers (x:xs) = x : eulers (minus xs $ map (*x) (x:xs))
由于对倍数的过早处理,两者都非常低效。可以通过将map
和枚举融合成一个更远的枚举(从x
移动到x * x
,即[x * x,x * x + x..]
)来轻松解决第一个定义,因此其处理可以被延迟,因为这里每个质数的倍数是独立生成的(以固定间隔枚举):
eratos (p:ps) xs | (h,t) <- span (< p*p) xs =
h ++ eratos ps (minus t [p*p, p*p+p..])
这与本文开头介绍的Bird筛法类似,
逐段进行筛选:
ps = 2 : [n | (r:q:_, px) <- (zip . tails . (2:) . map (^2) <*> inits) ps,
n <- [r+1..q-1] `minus` foldr union []
[[s+p, s+2*p..q-1] | p <- px, let s = r`div`p*p]]
((f <*> g) x = f x (g x)
在这里被用作pointfree的简写。)
对于第二个定义,即eulers
,没有简单的解决方法。
< p >
添加: 你可以看到使用Python生成器实现相同想法的比较,
在这里。
事实上,这段Python代码采用了一个望远镜式、多阶段的短暂质数流递归生成;在Haskell中,我们可以使用非共享的、多阶段的不动点组合子_Y
来安排它:
primes = 2 : _Y ((3:) . sieve 5 . unionAll . map (\p -> [p*p, p*p+2*p..]))
where
_Y g = g (_Y g)
sieve k s@(x:xs) | k < x = k : sieve (k+2) s
| True = sieve (k+2) xs
primesLME
必须重新评估primes'
已经评估过的内容,因此这种解耦会增加时间复杂度,并将primeLME
从持久数据转变为短暂数据,与流的本质相悖。 - FooBee