Я бы сделал несколько модификаций.
- Кажется странным, что вы выполняете
filterPrimes для всех чисел между 2 и max / 2, «фактическим»Техника сита требует, чтобы вы выполняли только filterPrimes для всех простых чисел между 2 и sqrt(max). - Также кажется странным, что вы используете var и a for loop.Чтобы сделать это «функциональным» способом, я бы вместо этого использовал рекурсивную функцию.
- Вместо выполнения
filterPrimes по всему списку, вы можете собирать простые числа по ходу дела;нет необходимости перебрасывать их через фильтр снова и снова. - Довольно странно
map, а затем filter, как вы делаете, так как карта просто помечает, какие элементы фильтровать, вы можете выполнитьто же самое, используя только фильтр.
Итак, вот моя первая попытка этих модификаций:
def filterFactors(seed: Int, xs: List[Int]) = {
xs.filter(x => x % seed != 0)
}
def sieve(max: Int) = {
def go(xs: List[Int]) : List[Int] = xs match {
case y :: ys => {
if (y*y > max) y :: ys
else y :: go(filterFactors(y, ys))
}
case Nil => Nil
}
go((2 to max).toList)
}
Однако, это отражает мой уклон Хаскелла и имеет огромный недостаток: он потребуетиз-за рекурсивного вызова y :: go(...) в вспомогательной функции go.Запуск sieve(1000000) привел к «OutOfMemoryError» для меня.
Давайте попробуем обычный трюк FP: хвостовая рекурсия с аккумуляторами.
def sieve(max: Int) = {
def go(xs: List[Int],
acc: List[Int])
: List[Int] = xs match {
case y :: ys => {
if (y*y > max) acc.reverse ::: (y :: ys)
else go(filterFactors(y, ys), y :: acc)
}
case Nil => Nil
}
go((2 to max).toList, Nil)
}
Добавив значение аккумулятора, мы можем записатьвспомогательная функция go в хвостово-рекурсивной форме, что позволяет избежать проблем с большими стеками.(Стратегия оценки Haskell сильно отличается; поэтому она не нуждается и не извлекает выгоду из хвостовой рекурсии)
Теперь давайте сравним скорость с императивным подходом, основанным на мутациях.
def mutationSieve (max: Int) = {
var arr: Array[Option[Int]] =
(2 to max).map (x => Some (x)).toArray
var i = 0
var seed = (arr (i)).get
while (seed * seed < max) {
for (j: Int <- (i + seed) to (max - 2) by seed) {
arr (j) = None
}
i += 1
while (arr (i).isEmpty) {
i += 1
}
seed = (arr (i)).get
}
arr.flatten
}
Здесь я используюArray[Option[Int]] и «вычеркнуть» число, заменив его запись на «Нет».Есть немного места для оптимизации;возможно, небольшое увеличение скорости можно получить с помощью массива bools, где индекс представляет конкретное число.Как бы то ни было.
Используя очень примитивные технические приемы (аккуратно расставленные new Date() звонки ...), я сравнил функциональную версию примерно в 6 раз медленнее, чем императивная.Ясно, что оба подхода имеют одинаковую сложность времени, но постоянные факторы, связанные с программированием со связанными списками, несут затраты.
Я также сравнил вашу версию, используя Math.sqrt(max).ceil.toInt вместо max / 2: это было примерно в 15 раз медленнее, чем функциональная версия, которую я представил здесь.Интересно, что 1 предполагает, что примерно 1 из каждых 7 чисел от 1 до 1000 (sqrt(1000000)) является простым (1 / ln (1000)), следовательно, Большая часть замедления может быть объяснена тем фактом, что вы выполняете цикл для каждого отдельного числа, в то время как я выполняю свою функцию только для каждого простого числа. Конечно, если для выполнения ~ 1000 итераций потребовалось 15 раз больше времени, для выполнения 500000 итераций потребуется ~ 7500x , поэтому ваш оригинальный код мучительно медленен.