Двухпотоковая подача для предотвращения ненужного запоминания?

Question

Я новичок в 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)

И это говорит

" Здесь введена двойная подача простых чисел, чтобы предотвратить ненужное запоминание и, таким образом, предотвратить утечку памяти, согласно коду Мелиссы О'Нил. "

Как это могло произойти? Я не могу понять, как это работает.

Answer 1

Как правило, определение потока простых чисел в формулировке Ричарда Берда о сите Эратосфена самоотносительно:

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. Это соответствует математическому определению сита Эратосфена как нахождению простых чисел в промежутках между композитами, перечисленных для каждого простого числа p путем подсчета с шагом p, P = {2} U ({3,4,...} \ U {{ p ², p ² + p, p ² + 2p,...} | p в P }).

Созданный поток используется в качестве входных данных в своем собственном определении. Это приводит к сохранению всего потока простых чисел в памяти (или большей части в любом случае). Фиксированная точка здесь - совместное использование 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)

---

Идея (из-за Мелиссы О'Нил) состоит в том, чтобы разделить это на два потока с внутренней петлей, подающей во второй поток простых чисел "над" этим:

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 произвел простое число q только его часть ниже sqrt q может быть отброшен, только после того, как он был использован foldr часть вычисления. Другими словами, эта последовательность поддерживает обратный указатель на себя до sqrt его самой большой произведенной стоимости (так как она потребляется своим потребителем, как print).

Так с одной петлей подачи (с 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"

то же самое, что и птичье сито в верхней части этого поста, по сегментам:

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) используется здесь как бессмысленное сокращение.)

Не существует простого решения для второго определения, т.е. eulers,

---

дополнение: вы можете увидеть ту же идею, реализованную с генераторами Python, для сравнения здесь.

Фактически, этот код Python использует телескопическое, многоэтапное рекурсивное производство потоков эфемерных простых чисел; в Haskell мы можем договориться об этом с помощью многоэтапного комбинатора Fixpoint без совместного использования _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..]