Memoization of Scala Streams

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);
}
Reference: Memoization of Scala Streams from our JCG partner Biju Kunjummen at the all and sundry blog.

Do you want to know how to develop your skillset to become a Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

JPA Mini Book

Learn how to leverage the power of JPA in order to create robust and flexible Java applications. With this Mini Book, you will get introduced to JPA and smoothly transition to more advanced concepts.

JVM Troubleshooting Guide

The Java virtual machine is really the foundation of any Java EE platform. Learn how to master it with this advanced guide!

Given email address is already subscribed, thank you!
Oops. Something went wrong. Please try again later.
Please provide a valid email address.
Thank you, your sign-up request was successful! Please check your e-mail inbox.
Please complete the CAPTCHA.
Please fill in the required fields.

One Response to "Memoization of Scala Streams"

  1. Mortimer says:

    you could also directly create an iterator:

    def from(n: Int) = Iterator.iterate(n)(_ + 1)

    The scaladoc is very explicit about Stream doing memoization by the way.

Leave a Reply


− eight = 1



Java Code Geeks and all content copyright © 2010-2014, Exelixis Media Ltd | Terms of Use | Privacy Policy | Contact
All trademarks and registered trademarks appearing on Java Code Geeks are the property of their respective owners.
Java is a trademark or registered trademark of Oracle Corporation in the United States and other countries.
Java Code Geeks is not connected to Oracle Corporation and is not sponsored by Oracle Corporation.
Do you want to know how to develop your skillset and become a ...
Java Rockstar?

Subscribe to our newsletter to start Rocking right now!

To get you started we give you two of our best selling eBooks for FREE!

Get ready to Rock!
You can download the complementary eBooks using the links below:
Close