双流饲料，以防止不必要的memoization？ [英] double stream feed to prevent unneeded memoization?

问题描述

当我检查了 haskell wiki关于素数，我发现了一些神秘的流优化技术。
在该维基的 3.8线性合并中：

  primesLME = 2：（[3 ，[...] p'p，p * p + 2 * p ..] p' - 素数']）
其中
素数'= 3： （（x：xs）]（其中，p（p） ：t）= x：union xs（joinL t）
  

它说

此处引入了双素数提要，以防止不必要的
记忆，从而防止内存泄漏，按照Melissa O'Neill的
代码。

这怎么可能？我无法弄清楚它是如何工作的。

解决方案

通常情况下，Richard Bird制定Eratosthenes筛是自引用的：

  import Data.List.Ordered（minus，union，unionAll）
 
 ps =（（2 :)。minus [3 ..] foldr（\pr-> p * p：union [p * p + p，p * p + 2 * p ..] r）[]） ps 
  

此定义生成的素数 ps 被用作它的输入。为了防止恶性循环，定义以初始值2开始。这对应于Eratosthenes筛的数学定义，即在复合体之间的间隙中寻找质数，对于每个质数> ， P = {2} U （{3,4，...） } \ U { p ² ， p ² + p

b

生成的流在其自己的定义中用作输入。这会导致整个素数流保留在内存中（或者大部分内存）。此处的固定点是共享， corecursive ：

  fix f = xs其中xs = f xs  - 共享定点组合器
 ps = fix（（2 :)。minus [3 ..]。foldr（...）[]）
  -  = xs其中xs = 2：减[3 ..]（foldr（...）[] xs）
  

---

这个想法 （归因于Melissa O'Neill）将它分成两个 流，内部循环馈入第二个素数之上：

  fix2 f = f xs其中xs = f xs  - 双级固定点组合器
 ps2 = fix2（（2 :)。minus [3 ..]。foldr（...）[]）
  -  = 2：minus [3 ...]（foldr（...）[] xs）其中
  -  xs = 2：minus [3 ..]（foldr（...）[] xs）
  ps2 产生一些素数 p 
时， code>，它的内部流 xs  of core ds只能被实例化为大约 sqrt p ，并且任何由 ps2 产生的素数都可以被丢弃，紧接着由系统收集：
 
 
 
 \ 
 \ 
 < -  ps2 < - 。 
 \ 
 \ 
 < -  xs < - 。 
 / \ 
 \ _________ / 
内循环产生的素数 xs 不能立即被丢弃，因为它们是自身需要的 xs >。当 xs 产生了一个素数 q 时，只有它的 sqrt q 可以在它被计算的 foldr 部分消耗后被丢弃。换句话说，这个序列将指针自身保存到其最大生成值的 sqrt 中（因为它正在被 ）消费者使用，就像 print ）。
 
 
 
因此，通过一个订阅循环（使用 fix ）几乎整个序列都必须保留在内存中，而使用double feed（使用 fix2 ）时，只需要保留大部分内部循环，到主流产生的当前值的平方根。因此整体空间复杂度从大约O（N）减小到大约O（sqrt（N）） - 大幅减少。
 
 
为此，必须使用优化来编译代码，即使用 -O2 开关，并运行独立程序。您可能还必须使用 -fno-cse 开关。在测试代​​码中必须只有一个对 ps2 的引用：
   
事实上，当在Ideone进行测试时，它确实显示了实际上不变的内存消耗。
 
 
 
 
 
 
  Eratosthenes的筛，而不是欧拉的筛。
  
 
 
最初的定义是：
 
 pre >  eratos（x：xs）= x：eratos（xs $ map（* x）[x ..]） -  ps = eratos [2 ..] 
 eulers（x： xs）= x：eulers（减xs $ map（* x）（x：xs）） -  ps = eulers [2 ..] 
  

由于过早处理倍数，两者都非常低效。通过将 map 和枚举融合到一个更远的枚举中（从 x），可以很容易地修复 first 到 x * x ，即 [x * x，x * x + x ..] （（）），所以它的处理可以是 推迟 。以固定的时间间隔枚举）：



  eratos（p：ps）xs | （h，t）< -  span（
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]] 
  

（<$这里使用c $ c>（f * g）x = fx（gx）作为 pointfree 速记。）

第二个定义没有简单的解决方法，即欧拉。 b

另外：你可以看到用Python生成器实现的相同想法， 。

事实上，Python代码使用了短暂素数流的可伸缩，多阶段递归生成;在Haskell 我们可以安排它与非共享，多阶段定点组合器 <$ c

$素数= 2：_Y（（3 :)）：$ c $ _Y ：

（\ p - > [p * p，p * p + 2 * p ..]））
其中
_Y g = g（_Y g） - == g。 G 。 G 。 G 。 ....

筛选k s @（x：xs）| k< x = k：sieve（k + 2）s - == [k，k + 2 ..] \ s，
| True = sieve（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 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..] . 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 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} U ({3,4,...} \ U {{p², p²+p, p²+2p, ...} | p in P}).

The produced stream is used as 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..]

这篇关于双流饲料，以防止不必要的memoization？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！