Scala: повторять последовательность, изменяя ее?

Question

Я пытаюсь реализовать Сито Эратосфена в Scala.

Я начинаю с инициализации последовательности всех нечетных чисел плюс 2:

// (end goal is to find all prime factors of bigNumber)
val largestPrime : Long = Math.ceil(Math.sqrt(bigNumber)).toLong
var nums : Seq[Long] = (3L to largestPrime by 2L).toSeq
nums +: 2L

Теперь nums содержит Seq (2,3,5,7,9,11,13,15, ..., (mostPrime)).Затем с помощью Sieve я хочу перебрать каждый элемент и отфильтровать все кратные этого элемента из Seq.Это выглядело бы примерно так, за исключением того, что это просто повторялось по каждому нечетному числу:

for(i : Long <- 3L to largestPrime by 2L) {
    nums = nums.filter((j : Long) => j == i || j % i != 0)
}

Так что вместо этого я хотел бы использовать что-то вроде этого:

for(i <- nums) {
    // filter
}

Но, конечноэто просто копирует последовательность в итератор, а затем выполняет итерацию по каждому значению в nums, как это было в начале цикла for (так что в этом случае это точно эквивалентно предыдущему примеру).Я хочу, чтобы на каждой итерации получалось следующее значение из nums.

Как лучше всего это реализовать?Должен ли я использовать индексную переменную и цикл while?Я не уверен, как получить элемент из последовательности (то есть, как получить элемент x последовательности, где x является индексом).Или есть более функциональный способ сделать это?

---

Редактировать: я только что нашел функцию scanLeft, я пытаюсь понять, как ее использовать, так как подозреваю, что она может быть полезна вэто дело ...

Answer 1

Давайте начнем с того, что я считаю самой большой проблемой выше.У вас есть это:

for (i <- mi) { mi = something else }

Это не изменит mi, который повторяется.Это mi останется неизменным повсюду.Возможно, вы можете изменить значение mi, но изменить его не получится.Кстати, это может не сработать.

Итак, как вы это делаете?Вы не используете для понимания - или, по крайней мере, не так.Вы можете посмотреть мою собственную версию здесь , которая перебирает коллекцию, отличную от мутируемой.Или вот одна строка:

(n: Int) => (2 to n) |> (r => r.foldLeft(r.toSet)((ps, x) => if (ps(x)) ps -- (x * x to n by x) else ps))

Теперь вернемся к тому, что вы хотите сделать ... когда вы используете для понимания, вы на самом деле вызываете метод foreach, map или flatMap на нем, поэтому вам понадобится коллекция, которая может обрабатывать один из этих методов и , не испытывая проблем с переходом следующего элемента с одной итерации наследующий.Как я уже сказал, я не уверен, что коллекция Scala отвечает всем требованиям.Если бы вы пошли по этому пути, вам было бы лучше использовать петлю while и отслеживать вещи самостоятельно.Например:

def primes(n: Int) = {
    import scala.collection.mutable.LinkedList
    val primes = LinkedList(3 to n by 2: _*)
    var p = primes
    while (p.nonEmpty) {
        var scanner = p
        while (scanner.next.nonEmpty) {
            if (scanner.next.head % p.head == 0)
                scanner.next = scanner.next.next
            else
                scanner = scanner.next
        }
        p = p.next
    }
    primes
}

Обратите внимание, что я держу указатель на начало LinkedList, перемещаю p через каждое известное простое число и перемещаю scanner через все оставшиеся числа, чтобы вырезатьштрихи.

Answer 2

Пример в документах по scala.collection.immutable.Stream имеет решето:

object Main extends Application {

  def from(n: Int): Stream[Int] =
    Stream.cons(n, from(n + 1))

  def sieve(s: Stream[Int]): Stream[Int] =
    Stream.cons(s.head, sieve(s.tail filter { _ % s.head != 0 }))

  def primes = sieve(from(2))

  primes take 10 print
}

Answer 3

Есть интересная статья: http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Я пытался перевести код Haskell, приведенный в этой статье, в Scala, но я не тестировал производительность.

object primes {

    type SI = Stream[Int]

    def sieve:SI = {
        def wheel2357:SI = Stream(4,2,4,6,2,6,4,2,4,6,6,
            2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,
            6,4,2,4,6,2,6,4,2,4,2,10,2,10,2) append wheel2357
        def spin(s:SI, n:Int):SI = Stream.cons(n, spin(s.tail, n + s.head))

        case class It(value:Int, step:Int) {
            def next = new It(value + step, step)

            def atLeast(c:Int):It =
            if (value >= c) this
            else new It(value + step, step).atLeast(c)
        }

        implicit object ItOrdering extends Ordering[It] {
            def compare(thiz:It, that:It) = {
                val r = thiz.value - that.value
                if (r == 0) thiz.step - that.step else r
            }

        }

        import scala.collection.immutable.TreeSet

        def sieve(cand:SI, set:Set[It]):SI = {
            val c = cand.head
            val set1 = TreeSet[It]() ++ set.dropWhile(_.value < c) ++
               set.takeWhile(_.value < c).map(_.atLeast(c))
            if (set1.elements.next.value == c) {
                val set2 = TreeSet[It]() ++ set1.dropWhile(_.value == c) ++
                    set1.takeWhile(_.value == c).map(_.next)
                sieve(cand.tail, set2)
            } else {
                Stream.cons(c, sieve(cand.tail, set1 + It(c*c,2*c)))
            }
        }
        Stream(2,3,5,7,11) append sieve(spin(wheel2357,13),
                  new TreeSet[It] + It(121,22))
    }

    def main(args:Array[String]) {
        sieve.takeWhile(_ < 1000).foreach(println)
    }
}

Answer 4

Ни хорошее функциональное решение, ни решение, которое раскрывает неясные сокровища библиотеки Scala, но довольно легко создать специализированный итератор самостоятельно.

class ModifyingIterator(var collection: Seq[Long]) extends Iterator[Long] {
  var current = collection.head
  def next = {
    current = collection.find(_ > current).get
    current
  }
  def hasNext = collection.exists(_ > current)
}

val mi = new ModifyingIterator(nums)

for (i <- mi) {
    mi.collection = mi.collection.filter((j : Long) => j == i || j % i != 0)
}
println(mi.collection)

ModifyingIterator отслеживает текущий элемент и позволяет переназначить коллекцию, которая используется для итерации. Следующий элемент всегда больше текущего элемента.

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