CODEWITHSUNDEEP
scalafunctional-programming
Abhishek Kumar
Abhishek Kumar

Reputation: 769

How to make following code run for large values of `n` while maintaining the functional style in Scala?

 Seq.fill(n)(math.pow(Random.nextFloat,2) + math.pow(Random.nextFloat,2)).filter(_<1).size.toFloat/n*4

Basically this scala code checks number of times a random points comes out of first quadrant of a unit circle. For large values of n this code gives memory limit exceeded error as it requires too big sequence. I can write this java way. But is there some functional way to achieve this task?

Upvotes: 2

Views: 77

Answers (2)

Nagarjuna Pamu
Nagarjuna Pamu

Reputation: 14825

Instead of filtering the values which are less than 1 after filling the sequence, consider adding valid numbers (i.e numbers greater or equal to 1) to the list. Thus saving unnecessary iteration on the collection.

def nums(n: Int): Iterator[Float] = {
  import scala.util.Random
  def helper(items: Iterator[Float], counter: Int): Iterator[Float] = {
    val num =  math.pow(Random.nextFloat,2) + math.pow(Random.nextFloat,2)
    if (counter > 0) {
      if (num >= 1) helper( items ++ Iterator(num.toFloat), counter - 1) else helper(items, counter - 1)
    } else items
  }
  helper(Iterator[Float](), n)
}

final answer

nums(n).toFloat/(n * 4)

Scala REPL

scala> def nums(n: Int): Iterator[Float] = {
     |       import scala.util.Random
     |       def helper(items: Iterator[Float], counter: Int): Iterator[Float] = {
     |         val num =  math.pow(Random.nextFloat,2) + math.pow(Random.nextFloat,2)
     |         if (counter > 0) {
     |           if (num >= 1) helper( items ++ Iterator(num.toFloat), counter - 1) else helper(items, counter - 1)
     |         } else items
     |       }
     |       helper(Iterator[Float](), n)
     |     }
nums: (n: Int)Iterator[Float]

scala> nums(10000).size.toFloat/(10000 * 4)
res1: Float = 0.053925

Upvotes: 0

Jasper-M
Jasper-M

Reputation: 15086

If you use an Iterator no intermediate collection has to be created in memory.

Iterator.fill(n)(math.pow(Random.nextFloat,2) + math.pow(Random.nextFloat,2)).filter(_<1).size.toFloat/n*4

Upvotes: 3

Related Questions