Euler 23 in Scala Heap Size Exception

Question

I want to solve this problem in Scala. My code:

def dividers(n: Int) =
  (1 until n) filter (x => n%x == 0)

def sumOfDividers(n: Int) = dividers(n).sum

val abNumbers = (1 to 28123) filter (x => sumOfDividers(x) > x)

The next step in my solutios is to make some sequence containing all possible of abundant number from abNumbers sequence. I've tried to do this with enhanced for loop, but it throws Java Heap Exception at runtime. How can i place all these sums into a Stream structure?

I assume that `Java Heap Exception` is OutOfMemoryException. But even if give the process 2Mb of memory to work with, it completes successfully, with or without streams. — Denis Tulskiy, Dec 05 '12 at 13:01
@DenisTulskiy indeed - maybe we'd like to look at the OP's 'enahanced for loop'? — Faiz, Dec 05 '12 at 17:41

score 2 · Accepted Answer · answered Dec 05 '12 at 12:27

2

Use the toStream method on ranges:

val abNumbers = ((1 to 28123) toStream).filter (x => sumOfDividers(x) > x)

abNumbers: scala.collection.immutable.Stream[Int] = Stream(12, ?)

Or am I missing something?

answered Dec 05 '12 at 12:27

Matthew Farwell

60,889
18
128
171

1

@senia why? Could you expand please? – Matthew Farwell Dec 05 '12 at 12:33
Reference to Stream is the reference to it's first element. GC is helpless while this reference is alive. – senia Dec 05 '12 at 12:54
@senia I don't understand? And using a var changes that? – Matthew Farwell Dec 05 '12 at 12:58
1

@senia but then you're defining a method. Each time you reference it, it'll create a new Stream. Which is probably not what you want. – Matthew Farwell Dec 05 '12 at 13:03
After some modifications Stream could became too big or infinite. With `def abNumbers` operations like `abNumbers.sum` or `abNumbers.drop` will work on big `Streams`. Even `abNumbers.foreach` will take finite memory (but infinite time) on infinite `Stream`. – senia Dec 05 '12 at 13:06
1

@senia, the OP makes it clear (to me) that he is not going to call `abNumbers.sum` or `abNumbers.drop`. And `abNumbers.foreach` would not be a very feasible idea regardless of whether `abNumbers` is `def` or `val` :-) – Péter Török Dec 05 '12 at 13:14

score 0 · Answer 2 · edited May 23 '17 at 10:34

Streams work nicely with infinite sequences. However, here you know your bounds; you just want to avoid all the intermediate collections that can come about as a by-product of functional programming. (Side Note: Euler 23 should be doable in profligate brute-force even on modest hardware; is it just that your heap is perhaps too small?)

If your main concern is memory, do consider using views. Like Streams, Views in Scala are lazy. But the semantics are different. Consider this:

(1 to 100000) map (_+1) filter (x => x % 2 == 0) map (x => x*x)

The intention here is function composition, but this will create several intermediate collections on the way: Each map and filter will return a new, potentially comparably sized collection. Views are one solution to obtain both performance (via memory efficiency) and compositionality: You just create your 'starting' collection as a view:

(1 to 100000 view) map (_+1) filter (x => x % 2 == 0) map (x => x*x)

Which would quickly return a SeqView and not the usual Seq - when the view is actually forced, your transformations (in map and filter) are effectively done as one as opposed to on different intermediate collections. Think of them as analogous to views on tables in SQL. Depending on how you plan on solving Euler Problem 23, views may be helpful. They are just one of the ways of leveraging laziness in Scala - See this post for the differences between views, streams and iterators: Stream vs Views vs Iterators

Euler 23 in Scala Heap Size Exception

2 Answers2