Использование потоков для итерации в Scala - PullRequest
Новая
       10

Использование потоков для итерации в Scala

10 голосов
/ 19 декабря 2011

SICP говорит, что итерационные процессы (например, метод вычисления квадратного корня Ньютона, вычисление «пи» и т. Д.) Могут быть сформулированы в терминах Streams.

Кто-нибудь используетstreams в Scala для моделирования итераций?

Ответы [ 2 ]

17 голосов
/ 20 декабря 2011

Вот один из способов получения потока аппроксимаций числа пи: 

val naturals = Stream.from(0) // 0, 1, 2, ...
val odds = naturals.map(_ * 2 + 1) // 1, 3, 5, ...
val oddInverses = odds.map(1.0d / _) // 1/1, 1/3, 1/5, ...
val alternations = Stream.iterate(1)(-_) // 1, -1, 1, ...
val products = (oddInverses zip alternations)
      .map(ia => ia._1 * ia._2) // 1/1, -1/3, 1/5, ...

// Computes a stream representing the cumulative sum of another one
def sumUp(s : Stream[Double], acc : Double = 0.0d) : Stream[Double] =
  Stream.cons(s.head + acc, sumUp(s.tail, s.head + acc))

val pi = sumUp(products).map(_ * 4.0) // Approximations of pi.

Теперь, скажем, вы хотите 200-ю итерацию: 

scala> pi(200)
resN: Double = 3.1465677471829556

... или 300000-ю:

scala> pi(300000)
resN : Double = 3.14159598691202
7 голосов
/ 20 декабря 2011

Потоки чрезвычайно полезны, когда вы выполняете последовательность рекурсивных вычислений, и один результат зависит от предыдущих результатов, таких как вычисление числа Пи.Вот более простой пример, рассмотрим классический рекурсивный алгоритм для вычисления чисел Фиббоначи (1, 2, 3, 5, 8, 13, ...): 

def fib(n: Int) : Int = n match {
  case 0 => 1
  case 1 => 2
  case _ => fib(n - 1) + fib(n - 2)
}

Одним из основных пунктов этого кода являетсяэто очень просто, но крайне неэффективно.fib(100) чуть не разбил мой компьютер!Каждая рекурсия разветвляется на два вызова, и вы по сути вычисляете одни и те же значения много раз.

Потоки позволяют выполнять динамическое программирование рекурсивным способом, где после вычисления значения оно используется повторно каждый раз, когда оно необходимоснова.Для реализации вышеизложенного с использованием потоков: 

val naturals: Stream[Int] = Stream.cons(0, naturals.map{_ + 1})
val fibs : Stream[Int] = naturals.map{
  case 0 => 1
  case 1 => 2
  case n => fibs(n - 1) + fibs( n - 2)
}
fibs(1) //2
fibs(2) //3
fibs(3) //5
fibs(100) //1445263496

В то время как рекурсивное решение выполняется за O (2 ^ n), решение Streams выполняется за O (n ^ 2).Поскольку вам нужны только последние 2 сгенерированных элемента, вы можете легко оптимизировать это, используя Stream.drop, чтобы размер потока не переполнял память.

...