Почему это поколение Scala Prime так медленно / интенсивно использует память?

Question

Мне не хватает памяти, когда я нахожу 10,001-е простое число.

object Euler0007 {
  def from(n: Int): Stream[Int] = n #:: from(n + 1)
  def sieve(s: Stream[Int]): Stream[Int] = s.head #:: sieve(s.filter(_ % s.head != 0))
  def primes = sieve(from(2))
  def main(args: Array[String]): Unit = {
    println(primes(10001))
  }
}

Это потому, что после каждой "итерации" (это правильный термин в этом контексте?) Из primes,увеличить стек функций, вызываемых для получения следующего элемента, на единицу?

Одно решение, которое я нашел в Интернете, не прибегает к итеративному решению (которого я бы хотел избежатьвойти в функциональное программирование / идиоматическое scala) это this (проблема 7):

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i => ps.takeWhile(j => j * j <= i).forall(i % _ > 0))

Из того, что я вижу, это не ведет к этому рекурсивному пути.Это хороший способ сделать это, или вы знаете лучший способ?

Answer 1

Одной из причин, почему это медленно, является то, что это не сито Эратосфена.Прочитайте http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf для подробного объяснения (примеры приведены на Haskell, но могут быть переведены непосредственно на Scala).

Моё старое решение для проблемы Эйлера №7 также не было "истинным" ситом, но, кажется, работает достаточно хорошо для небольших чисел:

object Sieve {

    val primes = 2 #:: sieve(3)

    def sieve(n: Int) : Stream[Int] =
          if (primes.takeWhile(p => p*p <= n).exists(n % _ == 0)) sieve(n + 2)
          else n #:: sieve(n + 2)

    def main(args: Array[String]) {
      println(primes(10000)) //note that indexes are zero-based
    }
}

Я думаю, что проблема с вашей первой версией в том, что у вас есть только def s и нет val, который собирает результаты и может бытьс помощью функции генерации, поэтому вы всегда можете пересчитать с нуля.

Answer 2

Да, это , потому что вы "увеличиваете стек функций, вызываемых для получения следующего элемента, на единицу после каждой" итерации "" - т.е. добавлять новый фильтр поверх стека фильтров каждый раз после получения каждого простого числа. Это слишком много фильтров .

Это означает, что каждое произведенное простое число проверяется всеми предшествующими простыми числами - но на самом деле нужны только те, которые находятся ниже его квадратного корня. Например, чтобы получить 10001-е простое число, 104743, , во время выполнения будет создано 10000 фильтров, созданных . Но есть только 66 простых чисел ниже 323, квадратный корень из 104743, поэтому только 66 фильтров были действительно необходимы . Все остальные 9934 будут там без нужды, занимая память, усердно работая и не принося никакой пользы.

Этот является ключевым недостатком этого "функционального сита", которое, как представляется, возникло в коде 1970-х годов Дэвидом Тернером, а позже нашло свой путь в книга SICP и другие места. Это , а не , что это пробное деление сито (а не сито Эратосфена ). Это слишком далеко беспокойство об этом. При оптимальном внедрении пробное деление способно очень быстро произвести 10000-е простое число.

Ключевой недостаток этого кода в том, что он не откладывает создание фильтров до нужного момента и в итоге создает слишком много из них.

Говоря сложности сейчас, код "старого сита": O (n ² ) , в n простых числах . Оптимальное пробное деление составляет O (n ^1,5 / log ^0,5 (n)) , а сито с эратосфенами составляет O (n * log ( п) * журнал (журнал (п))) . В качестве эмпирических порядков роста первое обычно обозначается как ~ n^2, второе - ~ n^1.45, а третье ~ n^1.2.

В этом ответе вы найдете код, основанный на генераторах Python для оптимального пробного деления (2-я половина) . Это было , первоначально обсуждавшееся здесь , имеющее отношение к эквиваленту Haskell вашей функции сита.

---

В качестве иллюстрации «читаемый псевдокод» :) для старого сита -

primes = sieve [2..]  where
   sieve (x:xs) = x : sieve [ y | y <- xs, rem y x > 0 ]
                         -- list of 'y's, drawn from 'xs',
                         --         such that (y % x > 0)

и для оптимального пробного деления (TD) сита, синхронизированного по квадратам простых чисел,

primes = sieve [2..] primes   where
  sieve (x:xs) ps = x : (h ++ sieve [ y | y <- t, rem y p > 0 ] qs)
          where
            (p:qs) = ps     -- 'p' is head elt in 'ps', and 'qs' the rest
            (h,t)  = span (< p*p) xs    -- 'h' are elts below p^2 in 'xs'
                                        -- and 't' are the rest

и для сита Эратосфена , , разработанного Ричардом Бердом , как видно из той статьи JFP, упомянутой в другом ответе здесь,

primes = 2 : minus [3..] 
               (foldr (\p r-> p*p : union [p*p+p, p*p+2*p..] r) [] primes)
                      -- function of 'p' and 'r', that returns 
                      -- a list with p^2 as its head elt, ...

Короткий и быстрый. (minus a b - это список a со всеми удаляемыми из него эльтами b; union a b - это список a со всеми эльтами из b постепенно добавляется к нему без дубликатов; оба имеют дело с упорядоченными, неубывающими списками ). foldr - это правый сгиб списка. Поскольку он является линейным, он работает на ~ n^1.33, для того чтобы он работал на ~ n^1.2, можно использовать древовидное сворачивание * функция foldi).

---

Ответ на ваш второй вопрос также: да . Ваш второй код, переписанный в том же «псевдокоде»,

ps = 2 : [i | i <- [3..], all ((> 0).rem i) (takeWhile ((<= i).(^2)) ps)]

очень похоже на описанное выше оптимальное сито TD - для каждого кандидата проверяется все простые числа ниже его квадратного корня. В то время как сито организует это с последовательностью отложенных фильтров во время выполнения, последнее определение заново выбирает необходимые простые числа для каждого кандидата. Один может быть быстрее другого, в зависимости от компилятора, но оба по сути одинаковы.

И третий тоже да : сито из Эратосфена лучше,

ps = 2 : 3 : minus [5,7..] (unionAll [[p*p, p*p+2*p..] | p <- drop 1 ps])

unionAll = foldi union' []          -- one possible implementation
union' (x:xs) ys = x : union xs ys
   -- unconditionally produce first elt of the 1st arg 
   -- to avoid run-away access to infinite lists

Похоже, что это может быть реализовано и в Scala, судя по сходству других фрагментов кода.(Хотя я не знаю Скала).unionAll здесь реализуется древовидная структура сгиба (щелкните для изображения и полного кода) , но также может быть реализована с помощью скользящего массива, работающего сегмент за сегментом вдоль потоков кратных простых чисел.

TL; DR: да, да и да.

Answer 3

FWIW, вот настоящее Сито Эратосфена:

def sieve(n: Int) = (2 to math.sqrt(n).toInt).foldLeft((2 to n).toSet) { (ps, x) => 
    if (ps(x)) ps -- (x * x to n by x) 
    else ps
}

Вот бесконечный поток простых чисел, использующий вариацию на Сите Эратосфена, которая сохраняет свои фундаментальные свойства:

case class Cross(next: Int, incr: Int)

def adjustCrosses(crosses: List[Cross], current: Int) = {
  crosses map {
    case cross @ Cross(`current`, incr) => cross copy (next = current + incr)
    case unchangedCross                 => unchangedCross
  }
}

def notPrime(crosses: List[Cross], current: Int) = crosses exists (_.next == current)

def sieve(s: Stream[Int], crosses: List[Cross]): Stream[Int] = {
    val current #:: rest = s

    if (notPrime(crosses, current)) sieve(rest, adjustCrosses(crosses, current))
    else current #:: sieve(rest, Cross(current * current, current) :: crosses)
}

def primes = sieve(Stream from 2, Nil)

Однако это несколько сложно использовать, так как каждый элемент Stream составлен с использованием списка crosses, который имеет столько же чисел, сколько было простых чисел, вплоть до числа, и кажется, что для почему-то эти списки хранятся в памяти для каждого номера в Stream.

Например, на основании комментария primes take 6000 contains 56993 выдаст исключение GC, тогда как primes drop 5000 take 1000 contains 56993 довольно быстро вернет результат в моих тестах.