In Scala, why is my sieve algorithm so slow?

Question

I am trying to implement the Sieve of Eratosthenes using lists and filters, rather than arrays and a loop. I am not sure why the following performs much worse than the imperative equivalent. 1 million should fly completely, but my car stops.

val max = 1000000 def filterPrimes(upper: Int, seed: Int = 2, sieve: List[Int] = List()): List[Int] = sieve.map(x => if (x % seed == 0 && x > seed) 0 else x).filter(_ > 0) var filtered: List[Int] = (2 to max).toList for (i <- 2 to max / 2) filtered = filterPrimes(max, i, filtered) filtered.foreach(println(_)) 

Answer 1

There are several potential problems, although I really don’t see a single “smoking gun” ... Anyway, this is what I have. At first:

 sieve.map(x => if (x % seed == 0 && x > seed) 0 else x).filter(_ > 0) 

can be written more briefly:

 sieve.filter(x => x <= seed || x % seed != 0) 

Further, upper not used in filterPrimes (this should not affect performance, though).

Third, do not use the var and for loop if you want to really use a pure functional style, instead turn filterPrimes into a tail-recursion function. The compiler may be smart enough to optimize copies if you do it this way (although I would not hold my breath).

Finally, and most importantly, your for loop spends a huge amount of time filtering values ​​that have already been filtered. For example, it tries to filter multiples of 4 after they have already filtered out all multiples of 2. If you want to use this sieve algorithm effectively, you need to select your seeds from the remaining items in the list.

In other words, keep the index in the list and define the seed from the index, for example:

 iteration 0: 2 3 4 5 6 7 8 9 ... index: ^ iteration 1: 2 3 5 7 9 ... index: ^ iteration 2: 2 3 5 7 ... index: ^ 

this avoids duplication of effort. Also, you don't need to keep repeating until you get to max , I think you can really stop when you walk past sqrt(max) .

Answer 2

If you want to see a functional way of performing a sieve, see Genuine Eratosthenes sieve .

Answer 3

I would make a few changes.

• It seems strange that you are doing filterPrimes for all numbers between 2 and max / 2 , for an "actual" sieve you only need to do filterPrimes for all primes between 2 and sqrt(max) .
• It also seems strange that you are using a var and a for loop. To make this a “functional” way, I would use a recursive function instead.
• Instead of doing filterPrimes all over the list, you can collect primes as you go; no need to throw them through the filter again and again.
• This is rather strange for map , and then filter , how you do it, since the map just determines which elements to filter, you can do the same using only the filter.

So here is my first attempt at these changes:

 def filterFactors(seed: Int, xs: List[Int]) = { xs.filter(x => x % seed != 0) } def sieve(max: Int) = { def go(xs: List[Int]) : List[Int] = xs match { case y :: ys => { if (y*y > max) y :: ys else y :: go(filterFactors(y, ys)) } case Nil => Nil } go((2 to max).toList) } 

However, this reflects my Haskell bias and has a huge flaw: it will take up a huge amount of stack space due to the recursive call of y :: go(...) in the go helper function. Running sieve(1000000) led to "OutOfMemoryError" for me.

Try using the generic FP trick: tail recursion with batteries.

 def sieve(max: Int) = { def go(xs: List[Int], acc: List[Int]) : List[Int] = xs match { case y :: ys => { if (y*y > max) acc.reverse ::: (y :: ys) else go(filterFactors(y, ys), y :: acc) } case Nil => Nil } go((2 to max).toList, Nil) } 

By adding a battery value, we can write the auxiliary function go in a tail recursive form, thereby avoiding the huge glass problem. (Haskell's evaluation strategy is very different, so it does not need any benefits from tail recursion)

Now compare speed with the imperative, mutation-based approach.

 def mutationSieve (max: Int) = { var arr: Array[Option[Int]] = (2 to max).map (x => Some (x)).toArray var i = 0 var seed = (arr (i)).get while (seed * seed < max) { for (j: Int <- (i + seed) to (max - 2) by seed) { arr (j) = None } i += 1 while (arr (i).isEmpty) { i += 1 } seed = (arr (i)).get } arr.flatten } 

Here I use Array[Option[Int]] and “cross out” the number, replacing its entry with “No”. There is a small portion of optimization opportunities; perhaps a slight speedup can be obtained using the bools array, where the index represents a specific number. Whatever.

Using very primitive technologies (carefully placed calls to new Date() ...) I compared the functional version about 6 times slower than the actual version. It is clear that both approaches have the same complexity in time, but the constant factors associated with programming with linked lists are costly.

I also compared your version using Math.sqrt(max).ceil.toInt instead of max / 2 : it was about 15 times slower than the functional version presented here. Interestingly, it is estimated ¹ that approximately 1 out of every 7 numbers between 1 and 1000 ( sqrt(1000000) ) is prime (1 / ln (1000)), so a significant part of the slowdown may be due to the fact that you loop on each separate room, while I perform my function only for every simple one. Of course, if it took 15 times to complete ~ 1000 iterations, it would take ~ 7500x to complete 500,000 iterations , so your source code is painfully slow.

Answer 4

This is a quick sieve that implements hints of mergeconflict and some tips from the article mentioned by Ken Wayne VanderL:

 def createPrimes (MAX: Int) : Array[Boolean] = { val pri = (false :: false :: true :: List.range (3, MAX + 1).map (_ % 2 != 0)).toArray for (i <- List.range (3, MAX) if (pri (i))) { var j = 2 * i; while (j < MAX) { if (pri (j)) pri (j) = false; j += i; } } pri } val MAX = 1000*1000 (1 to MAX).filter (createPrimes (MAX)) 

Graph Comparison: The vertical axis shows seconds, the horizontal - from 100,000 to 1,000,000 primes. The deltaNovember algorithm has already been improved to work only with math.sqrt (max) and the filtering proposed by Alexey Romanov in a comment. From Dan Burton, I took the second algorithm and the last one with a slight modification to match my interface (List, not Array) and bitSet Sieve, with which it is associated only in a comment, but which is the fastest.

Answer 5

Lists are immutable, and each call to filterPrimes creates a new list. You create a lot of lists, which, by the way, are not needed.

Go with your first instinct (which you probably call the "imperative equivalent"), which I assume uses a single variable array.

(Edited to clarify that I realized that creating multiple lists is not necessary.)