Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Memoization of Scala Streams

DZone's Guide to

Memoization of Scala Streams

· Java Zone
Free Resource

Make it happen: rapid app development on Kubernetes as a managed service.

I learnt the hard way that Scala internally uses memoization with Streams. 

This was my first attempt at a solution to Euler Problem 5

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!")
}

I was a little mystified by why this code was throwing an OutOfMemoryError, realized thanks to Stackoverflow that since the answer to this problem is quite high 232792560, all the integers in this range will be memoized within the different nodes of the stream and hence the issue.

This is actually easy to see, let me first modify the stream generator function with a side effect:

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

The second statement would not print anything.

Given this memoization behavior there are a few possible fixes, the simplest is to not keep a reference to the head of the stream anywhere and to use the find method of iterator instead:

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

On a related note, Java 8 streams are not memoized and a solution using Java 8 streams (admittedly can be improved massively) is the following:

@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);
}


Tutorial: WordPress as distributed microservices on Kubernetes.

Topics:

Published at DZone with permission of Biju Kunjummen, DZone MVB. See the original article here.

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.

X

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}