Home » JVM Languages » Scala » Memoization of Scala Streams

About Biju Kunjummen

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 our best selling eBooks for FREE!

1. JPA Mini Book

2. JVM Troubleshooting Guide

3. JUnit Tutorial for Unit Testing

4. Java Annotations Tutorial

5. Java Interview Questions

6. Spring Interview Questions

7. Android UI Design

and many more ....

 

One comment

  1. 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

Your email address will not be published. Required fields are marked *

*


two × = 4

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Want to take your Java Skills to the next level?
Grab our programming books for FREE!
  • Save time by leveraging our field-tested solutions to common problems.
  • The books cover a wide range of topics, from JPA and JUnit, to JMeter and Android.
  • Each book comes as a standalone guide (with source code provided), so that you use it as reference.
Last Step ...

Where should we send the free eBooks?

Good Work!
To download the books, please verify your email address by following the instructions found on the email we just sent you.