How can I make my scala function faster?

Question

I made isSorted function in both Scala and Java. When I measured the execution time of both the functions, I saw that the Scala version was very slow. It ran about 3.2 sec for 10000 Int but Java version just ran about 10 ms!!! How can I make faster my scala version?

These were the implementation :

Scala:

def main(args: Array[String]) ={
    println(isSorted(getArray, (x:Int,y:Int) => x<y ))
}
def isSorted[A](items : Array[A], cond: (A,A) => Boolean) : Boolean = items match{
  case Array(_) => true 
  case Array(x,y) =>cond(x,y)
  case Array(_*) => cond(items(0),items(1)) && isSorted(items tail,cond)
}

Java:

public static void main(String... args){
    Sorter<Integer> sorter=new Sorter<Integer>();
    System.out.println(sorter.isSorted(sorter.getList(),new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    }));
}
public  boolean isSorted(List<A> items, Comparator<A> cond){
    for(int i=1;i<items.size();i++){
            if(cond.compare(items.get(i-1), items.get(i)) < 0){
                return false;
            }
        }
    return true;
}

Any suggestion?

I know this is a weird code :)

I would like to use Scala but this bad performance scared me!

Answer 1

Here's how I would do it, in a way that's idiomatic to Scala, more flexible, and sticks to a functional style.

def isSorted[A](xs: Seq[A])(cond: (A, A) => Boolean) = {
  (xs, xs.view.drop(1)).zipped.forall { case(a,b) => cond(a,b) }
}

Used as follows:

val xs = (0 to 10000).toArray
val sorted = isSorted(xs)(_ < _) // or isSorted(xs)((a,b) => a < b) if you prefer

This has several advantages over the original version:

• It works for any sequence, not just Arrays
• It completes about 500 times faster than than the version that uses array pattern matching
  • My rudimentary benchmark took about 4.6 seconds to complete the original version, and 0.008 seconds to complete the proposed version
• The code is both shorter and more idiomatic
• It puts the predicate function in its own braces, meaning it will infer types for you automatically instead of making you put them in by hand. You also get _ wildcards for free.

Edit

With the original signature (which loses the ability to type-infer the conditional function, and restricts the type to only arrays), you would have a function that looks like this:

def isSorted[A](items: Array[A], cond: (A, A) => Boolean): Boolean = { 
  (xs, xs.view.drop(1)).zipped.forall { case(a,b) => cond(a,b) }
}

This seems to be a couple times faster than the version that uses sliding(2) to turn the array into an iterator. It's not quite as speedy as using direct indexers (translating straight from Java). It's still on the order of 500 or 600 times faster than pattern matching directly on the array.

I also changed it from using a negation of exists to using the positive assertion of forall. This doesn't affect the performance, just the readability (exists required a double-negative, which was foolish of me).

Edit 2

I've added a call to .view, to prevent a full copy of the array for the second value. This speeds up the algorithm slightly, getting it to a point where it's nearly (but not quite) as fast as accessing the indices directly. The expression can still generalize to non-Array inputs, were you to ever update the function signature.

Answer 2

I just want to add another approach, which is also O(n).

def isSorted[A](items: Array[A], cond: (A,A) => Boolean): Boolean =
  (0 until items.size - 1).forall(i => cond(items(i), items(i + 1)))

Answer 3

Totally subscribe to @Rex-Kerr answer, a possible improvement on the array indexing approach that relies on examining each end of the array for each iteration, as follows,

def isSorted[A](items: Array[A], cond: (A,A) => Boolean): Boolean = {
  val len = items.length
  for (i <- 1 until len/2+1) 
    if (!(cond(items(i-1),items(i))) || !(cond(items(len-i-1),items(len-i))) ) return false
  true
}

In general, the initial array may be partitioned into n segments and apply the condition on each in parallel.

Answer 4

You're making copies of the entire array in Scala every iteration. If you replace an O(n) algorithm with an O(n^2) one, of course that is going to be slower! This has nothing to do with Scala vs. Java or even pattern matching.

If you want to use an algorithm with tails, switch to a data structure that supports efficient tails (e.g. List).

def isSorted[A](items: List[A], cond: (A,A) => Boolean): Boolean = items match {
  case Nil => true
  case x :: y :: rest if (!cond(x,y)) => false
  case _ => isSorted(items.tail, cond)
}

Alternatively, you can implement the same algorithm as with Java, since arrays are efficient with indexing:

def isSorted[A](items: Array[A], cond: (A,A) => Boolean): Boolean = {
  for (i <- 1 until items.length) if (!(cond(items(i-1),items(i)))) return false
  true
}

Or you could, if performance isn't super-important, switch to some generic but still O(n) algorithm:

def isSorted[A](items: Array[A], cond: (A,A) => Boolean) = 
  items.sliding(2).filter(_.length == 2).forall(x => cond(x(0),x(1)))

This will be maybe 5x slower than the index-based version.

Answer 5

In Scala using the idiomatic style is not always the most appropriate when having the performance into account. In particular, Scala Array pattern matching is really slow.

However, using the non-idiomatic style in this case it will perform similar or slightly better than in Java.

Here you a version of your isSorted algorithm but using the classic if conditional instead of pattern matching. You can run the same benchmark with this solutions and it has to be a big difference. Let me know if performs much better.

 def isSorted[A](items: Array[A], cond: (A,A) => Boolean): Boolean = {
   if  (items.length == 1) true
   else if (cond(items(1), items(0))) false
   else { isSorted(items.tail, cond) }
 }