双流进料以防止不必要的记忆化？

Question

双流进料以防止不必要的记忆化？

haskellprimessieve-of-eratostheneslazy-sequencesspace-leak

12

我是Haskell的新手，正在尝试以流处理方式实现欧拉筛法。

当我查看有关素数的Haskell维基页面时，我发现了一些神秘的流优化技术。在该维基的3.8线性合并中：

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)

它说：

“在这里引入双引号反馈以防止不必要的记忆化，从而防止内存泄漏，如Melissa O'Neill的代码所述。”

为什么呢？我无法理解它是如何工作的。

- FooBee

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Will Ness · Accepted Answer

通常情况下，Richard Bird在筛选法求素数时的定义是自我引用的：

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)

这个定义产生的质数 ps 被用作输入。为了避免“恶性循环”，该定义以初始值2为基础进行改进。这对应于 Eratosthenes 筛法的数学定义，即在合数之间的空隙中找到质数，由每个质数 p 的计数步骤枚举。

P = { 2 } ∪ ( { 3,4,5,... } \ ⋃_{_p in P} { p², p²+p, p²+2p, ... } )

所产生的流被用作其自身定义的输入。这导致整个质数流保留在内存中（或者至少大部分）。这里的固定点是“共享”、“核递归”的概念。

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)

这个想法（由Melissa O'Neill提出）是将其分成两个流，其中一个内部循环将进入第二个“上面”的质数流：

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)

因此，当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..] )    -- ps = eratos [2..]
eulers (x:xs) = x : eulers (minus xs $ map (*x) (x:xs))    -- ps = eulers [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 (minus t [p*p, p*p+p..])   -- "postponed sieve"

这与本文开头介绍的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)                                   -- == 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..]