Бесконечные потоки в Скале

Question

Скажите, у меня есть функция, например, старая любимая

def factorial(n:Int) = (BigInt(1) /: (1 to n)) (_*_)

Теперь я хочу найти наибольшее значение n, для которого factorial(n) подходит для Long. Я мог бы сделать

(1 to 100) takeWhile (factorial(_) <= Long.MaxValue) last

Это работает, но 100 - произвольное большое число; то, что я действительно хочу с левой стороны, - это бесконечный поток, который продолжает генерировать большие числа, пока не будет выполнено условие takeWhile

Я придумал

val s = Stream.continually(1).zipWithIndex.map(p => p._1 + p._2)

а есть ли лучший способ?

(я также знаю, что могу найти решение рекурсивно, но это не то, что я ищу.)

Answer 1

Stream.from(1)

создает поток, начинающийся с 1 и увеличивающийся на 1. Это все в API документах .

Answer 2

Решение с использованием итераторов

Вы также можете использовать Iterator вместо Stream.Stream хранит ссылки на все вычисленные значения.Поэтому, если вы планируете посещать каждое значение только один раз, итератор - более эффективный подход.Недостатком итератора является его изменчивость.

Есть несколько удобных методов для создания Iterator s, определенных для его сопутствующего объекта .

Edit

К сожалению, я не знаю короткого (поддерживаемого библиотекой) способа достижения чего-то вроде

Stream.from(1) takeWhile (factorial(_) <= Long.MaxValue) last

Подход, который я выбрал для продвижения Iterator для определенного количества элементов, - drop(n: Int) илиdropWhile:

Iterator.from(1).dropWhile( factorial(_) <= Long.MaxValue).next - 1

- 1 работает для этой специальной цели, но не является общим решением.Но не должно быть проблем с реализацией метода last на Iterator с использованием pimp my library.Проблема с получением последнего элемента бесконечного итератора может быть проблематичной.Поэтому он должен быть реализован как метод, подобный lastWith, интегрирующий takeWhile.

Ужасный обходной путь может быть выполнен с помощью sliding, который реализован для Iterator:

scala> Iterator.from(1).sliding(2).dropWhile(_.tail.head < 10).next.head
res12: Int = 9

Answer 3

, как указал @ziggystar, Streams сохраняет список ранее вычисленных значений в памяти, поэтому использование Iterator является большим улучшением.

для дальнейшего улучшения ответа, я бы сказал, что "бесконечно«потоки», обычно вычисляются (или могут быть вычислены) на основе предварительно вычисленных значений.если это так (а в вашем факториальном потоке это определенно так), я бы предложил вместо этого использовать Iterator.iterate.

выглядело бы примерно так:

scala> val it = Iterator.iterate((1,BigInt(1))){case (i,f) => (i+1,f*(i+1))}
it: Iterator[(Int, scala.math.BigInt)] = non-empty iterator

тогда вы могли бысделайте что-то вроде:

scala> it.find(_._2 >= Long.MaxValue).map(_._1).get - 1
res0: Int = 22

или используйте @ziggystar sliding решение ...

другим простым примером, который приходит на ум, будут числа Фибоначчи:

scala> val it = Iterator.iterate((1,1)){case (a,b) => (b,a+b)}.map(_._1)
it: Iterator[Int] = non-empty iterator

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

Answer 4

Исходная функция «факториала» не является оптимальной, поскольку факториалы каждый раз вычисляются с нуля.Самая простая / неизменная реализация, использующая запоминание, выглядит следующим образом:

val f : Stream[BigInt] = 1 #:: (Stream.from(1) zip f).map { case (x,y) => x * y }

И теперь ответ может быть вычислен следующим образом:

println( "count: " + (f takeWhile (_<Long.MaxValue)).length )

Answer 5

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

Iterator.from(1).find(i => factorial(i+1) > Long.MaxValue).get

Использование .get здесь допустимо, поскольку find для бесконечной последовательности никогда не вернет None.