双流馈送以防止不必要的记忆? [英] double stream feed to prevent unneeded memoization?
问题描述
我是 Haskell 的新手，我正在尝试以流处理风格实现 Euler's Sieve.
当我查看 有关素数的 Haskell Wiki 页面时，我发现了一些神秘的流优化技术.在该维基的 3.8 线性合并中:
primesLME = 2 : ([3,5..] `minus` joinL [[p*p, p*p+2*p..] | p <- primes'])在哪里素数' = 3 : ([5,7..] `减去` joinL [[p*p, p*p+2*p..] | p <-素数'])joinL ((x:xs):t) = x : union xs (joinL t)它说
<块引用>这里引入了双质数提要，以防止不必要的memoization 从而防止内存泄漏，根据 Melissa O'Neill 的说法代码."
怎么会这样?我不知道它是如何工作的.
通常，Richard Bird 的 Eratosthenes 筛法中的质数流定义是自指的:
import Data.List.Ordered(减去，union，unionAll)ps = 2 : 减去 [3..] -- `:` 是缺点"；(foldr (pr -> p*p : union [p*p+p, p*p+2*p..] r) [] ps)由这个定义产生的素数 ps 被用作它的输入.为了防止恶性循环，定义以初始值 2 开头.这对应于 Eratosthenes 筛的数学定义，即在复合物之间的间隙中寻找素数，为每个素数枚举p 以 p,
P = { 2 } ∪ ( { 3,4,5,... } ⋃p in P { p2, p2+p, p2+2p, ... } )
生成的流在其自己的定义中用作输入.这会导致整个素数流保留在内存中(或大部分).这里的修复点是共享，核心递归:
fix f = xs where xs = f xs -- 一个共享的固定点组合器ps = fix ((2:) . 减去 [3..] . foldr (...) [])-- = xs 其中 xs = 2 : 减去 [3..] (foldr (...) [] xs)这个想法(由于 Melissa O'Neill)是，然后将其分成两个流，并带有一个内循环馈送进入第二个质数流above"它:
fix2 f = f xs where xs = f xs -- 双阶段定点组合器ps2 = fix2 ((2:) . 减去 [3..] . foldr (...) [])-- = 2 : 减去 [3..] (foldr (...) [] xs) 其中-- xs = 2 : 减去 [3..] (foldr (...) [] xs)因此，当 ps2 产生一些质数 p 时，其内部流 xs 的 core" 质数只需要实例化大约 sqrt p，并且任何由 ps2 产生的素数都可以在之后立即被系统丢弃和垃圾收集:
由内循环xs 产生的素数不能立即丢弃，因为xs 流本身需要它们.当 xs 产生一个质数 q 时，只有它在 sqrt q 之下的部分可以被丢弃，就在它被 消耗之后foldr 部分计算.换句话说，这个序列保持指向自身的后向指针，向下指向其最大产生值的 sqrt(因为它被它的消费者消费，比如 print).
因此，对于一个 feed 循环(使用 fix)，几乎整个序列都必须保留在内存中，而使用 double feed(使用 fix2)时，只有内部循环需要大部分保留，仅达到主流产生的当前值的平方根.因此，整体空间复杂度从大约 O(N) 降低到大约 O(sqrt(N)) —— 大幅降低.
为此，必须使用优化编译代码，即使用 -O2 开关，并独立运行.您可能还必须使用 -fno-cse 开关.并且在测试代码中必须只有一个对 ps2 的引用:
main = getLine >>= (read >>> (+(-1)) >>> (`drop` ps2) >>> print . take5)事实上，在 Ideone 上进行测试时，确实显示内存消耗几乎恒定.
这是埃拉托色尼筛法，而不是欧拉筛法.
最初的定义是:
eratos (x:xs) = x : eratos (减去 xs $ map (*x) [x..] ) -- ps = eratos [2..]euler (x:xs) = x : euler (减去 xs $ map (*x) (x:xs)) -- ps = euler [2..]由于对倍数的过早处理，两者都非常低效.通过将 map 和枚举融合为一个远离的枚举(从 x 到 x*x，即[x*x, x*x+x..])，这样它的处理就可以推迟 -- 因为这里每个素数的倍数是独立生成的(以固定间隔枚举):
eratos (p:ps) xs |(h,t) <- span (< p*p) xs = -- ps = 2 : eratos ps [2..]h ++ eratos ps(减去 t [p*p, p*p+p..])——延迟筛分"；这与本文顶部的 Bird 筛子相同，segment-wise:
ps = 2 : [n |(r:q:_, px) <- (zip .tails .(2:) .map (^2) <*> inits) ps,n <- [r+1..q-1] `减` foldr union [][[s+p, s+2*p..q-1] |p <- px，让 s = r`div`p*p]]((f <*> g) x = fx (gx) 在这里用作 pointfree 简写.)
对于第二个定义，即 euler，没有简单的解决方法.
补充:您可以在此处看到使用 Python 生成器实现的相同想法，以便进行比较>.
事实上，该 Python 代码采用了伸缩式、多级递归产生的临时素数流；在 Haskell 我们可以安排与非共享，多阶段固定点组合器_Y:
primes = 2 : _Y ((3:) .sieve 5 . unionAll . map (p -> [p*p, p*p+2*p..]))在哪里_Y g = g (_Y g) -- == g .G .G .G .....筛 k s@(x:xs) |k＜x = k : 筛分 (k+2) s -- == [k,k+2..] \ s,|True = 筛分 (k+2) xs -- 当 s ⊂ [k,k+2..]I'm new to Haskell and I'm trying to implement Euler's Sieve in stream processing style.
When I checked the Haskell Wiki page about prime numbers, I found some mysterious optimization technique for streams. In 3.8 Linear merging of that wiki:
primesLME = 2 : ([3,5..] `minus` joinL [[p*p, p*p+2*p..] | p <- primes'])
where
primes' = 3 : ([5,7..] `minus` joinL [[p*p, p*p+2*p..] | p <- primes'])
joinL ((x:xs):t) = x : union xs (joinL t)
And it says
"The double primes feed is introduced here to prevent unneeded memoization and thus prevent memory leak, as per Melissa O'Neill's code."
How could this be? I can't figure out how it works.
Normally, definition of primes stream in Richard Bird's formulation of the sieve of Eratosthenes is self-referential:
import Data.List.Ordered (minus, union, unionAll)
ps = 2 : minus [3..] -- `:` is "cons"
(foldr (p r -> p*p : union [p*p+p, p*p+2*p..] r) [] ps)
The primes ps produced by this definition are used as the input to it. To prevent a vicious circle the definition is primed with the initial value, 2. This corresponds to the mathematical definition of the sieve of Eratosthenes as finding primes in the gaps between the composites, enumerated for each prime p by counting up in steps of p,
P = { 2 } ∪ ( { 3,4,5,... } ⋃p in P { p2, p2+p, p2+2p, ... } )
The produced stream is used as the input in its own definition. This causes the retention of the whole stream of primes in memory (or most of it anyway). The fixpoint here is sharing, corecursive:
fix f = xs where xs = f xs -- a sharing fixpoint combinator
ps = fix ((2:) . minus [3..] . foldr (...) [])
-- = xs where xs = 2 : minus [3..] (foldr (...) [] xs)
The idea (due to Melissa O'Neill) is, then, to separate this into two streams, with an inner loop feeding into the second stream of primes "above" it:
fix2 f = f xs where xs = f xs -- double-staged fixpoint combinator
ps2 = fix2 ((2:) . minus [3..] . foldr (...) [])
-- = 2 : minus [3..] (foldr (...) [] xs) where
-- xs = 2 : minus [3..] (foldr (...) [] xs)
Thus, when ps2 produces some prime p, its inner stream xs of "core" primes needs only be instantiated up to about sqrt p, and any primes which are produced by ps2 can get discarded and garbage-collected by the system immediately afterwards:
<- ps2 <-.
<- xs <-.
/
\_________/ Primes produced by the inner loop xs can not be immediately discarded, because they are needed for xs stream itself. When xs has produced a prime q, only its part below sqrt q can be discarded, just after it has been consumed by the foldr part of the computation. In other words this sequence maintains back pointer into itself down to the sqrt of its biggest produced value (as it is being consumed by its consumer, like print).
So with one feed loop (with fix) almost the whole sequence would have to be retained in memory, while with the double feed (with fix2) only the inner loop needs to be mostly retained that only reaches up to the square root of the current value produced by the main stream. Thus the overall space complexity is reduced from about O(N) to about O(sqrt(N)) -- a drastic reduction.
For this to work the code must be compiled with optimizations, i.e. with the -O2 switch, and run standalone. You may also have to use -fno-cse switch. And there must be only one reference to ps2 in the testing code:
main = getLine >>= (read >>> (+(-1)) >>> (`drop` ps2) >>> print . take 5)
In fact, when tested at Ideone, it does show a practically constant memory consumption.
And it's the Sieve of Eratosthenes, not Euler's sieve.
The initial definitions are:
eratos (x:xs) = x : eratos (minus xs $ map (*x) [x..] ) -- ps = eratos [2..]
eulers (x:xs) = x : eulers (minus xs $ map (*x) (x:xs)) -- ps = eulers [2..]
Both are very inefficient because of the premature handling of the multiples. It is easy to remedy the first definition by fusing the map and the enumeration into one enumeration moved further away (from x to x*x, i.e. [x*x, x*x+x..]), so that its handling can be postponed -- because here each prime's multiples are generated independently (enumerated at fixed intervals):
eratos (p:ps) xs | (h,t) <- span (< p*p) xs = -- ps = 2 : eratos ps [2..]
h ++ eratos ps (minus t [p*p, p*p+p..]) -- "postponed sieve"
which is the same as Bird's sieve at the top of this post, segment-wise:
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) is used here as a pointfree shorthand.)
There is no easy fix for the second definition, i.e. eulers.
addition: you can see the same idea implemented with Python generators, for comparison, here.
In fact, that Python code employs a telescopic, multistage recursive production of ephemeral primes streams; in Haskell we can arrange for it with the non-sharing, multi-staged fixpoint combinator _Y:
primes = 2 : _Y ((3:) . sieve 5 . unionAll . map (p -> [p*p, p*p+2*p..]))
where
_Y g = g (_Y g) -- == g . g . g . g . ....
sieve k s@(x:xs) | k < x = k : sieve (k+2) s -- == [k,k+2..] \ s,
| True = sieve (k+2) xs -- when s ⊂ [k,k+2..]
这篇关于双流馈送以防止不必要的记忆?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
