Scala: Выражать последовательность при ее изменении?

Question

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

Я начинаю с инициализации последовательности всех нечетных чисел плюс 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, ..., (самый большой проход)). Затем, по ситу, я хочу перекончить с каждым элементом и фильтровать все кратные этого элемента из SEQ. Это выглядело бы примерно так, за исключением того, что это просто итерации по каждому нечетному номеру:

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

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

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

Но, конечно, это просто копирует последовательность в итератор, а затем итерации по каждому значению в nums Как это было в начале цикла для цикла (так и в этом случае, это точно эквивалентно предыдущему примеру). Я хочу, чтобы это, каждая итерация, взяла следующее значение от 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.imtable.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

Ни хорошее функциональное решение, ни решение, которое показывает неясные сокровища библиотеки 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 отслеживает текущий элемент и позволяет переназначить коллекцию, которая используется для итерации. Следующий элемент всегда больше текущего элемента.

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

Answer 4

Есть интересная бумага: 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)
    }
}