Статьи

Мемоизация потоков Scala

Январь 16, 2019

Я усвоил сложный способ, которым scala внутренне использует запоминание в Streams.

Это была моя первая попытка решить проблему Эйлера 5

01
02
03
04
05
06
07
08
09
10
11
12
def from(n: Int): Stream[Int] = n #:: from(n + 1)
 
def isDivisibleByRange(n: Int, r: Range) = {
  r.forall(n % _ == 0)
}
 
val a = from(21)
val o = a.find(isDivisibleByRange(_, Range(2, 21)))
o match {
  case Some(i) => println(i)
  case None => println("Nothing found!")
}

Я был немного озадачен тем, почему этот код генерировал ошибку OutOfMemoryError, благодаря Stackoverflow понял, что, поскольку ответ на эту проблему довольно высок 232792560, все целые числа в этом диапазоне будут запоминаться в разных узлах потока и, следовательно, проблема ,

Это на самом деле легко увидеть, позвольте мне сначала изменить функцию генератора потоков с побочным эффектом:

1
2
3
4
def from(n: Int): Stream[Int] = {println(s"Gen $n"); n #:: from(n + 1)}
val s = from(1)
s.take(10).toList
s.take(10).toList

Второе утверждение не напечатало бы ничего.

При таком поведении запоминания существует несколько возможных исправлений, самое простое — нигде не хранить ссылку на начало потока и использовать вместо него метод find итератора:

1
from(1).iterator.find(isDivisibleByRange(_, Range(1, 21)))

В связи с этим примечание, потоки Java 8 не запоминаются, и решение с использованием потоков Java 8 (по общему признанию, может быть значительно улучшено) заключается в следующем:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
@Test
public void testStreamOfInts() {
 Stream<Integer> intStream = Stream.generate(from(1));
 List<Integer> upto20 = IntStream.rangeClosed(1, 20).boxed().collect(Collectors.toList());
 Predicate<Integer> p = (i -> isDivisibleOverRange(i, upto20));
 Optional<Integer> o = intStream.filter(p).findFirst();
 o.ifPresent(i -> System.out.println("Found: " + i));
}
 
private Supplier<Integer> from(Integer i) {
 AtomicInteger counter = new AtomicInteger(0);
 return () ->  counter.incrementAndGet();
}
 
private boolean isDivisibleOverRange(Integer n, List<Integer> l) {
 return l.stream().allMatch(i -> n % i == 0);
}
Ссылка: Мемориализация Scala Streams от нашего партнера JCG Биджу Кунджуммена в блоге all and sundry.
36
Share: