5
\$\begingroup\$

I made an isSorted function in Scala and Java as well and when I measured the time of functions' run 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?

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 sorter=new Sorter();
    System.out.println(sorter.isSorted(sorter.getList(),new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2.compareTo(o1);
        }
    }));
}
public <A> 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 suggestions?

I would like to use Scala, but this bad performance scared me! Can I keep Scala's syntactic sugar?

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Java 8, which will release in a week, will support Lambdas, so you can use some of the syntaxic sugar. Keep in mind though that Scala is much less verbose than Java is. \$\endgroup\$
    – skiwi
    Mar 10, 2014 at 21:28
  • \$\begingroup\$ I think the Java version can be faster.... would that review be interesting to you? \$\endgroup\$
    – rolfl
    Mar 10, 2014 at 21:39
  • \$\begingroup\$ Yes I know I wrote it down. I am interested in making faster the Scala version. \$\endgroup\$
    – bitli
    Mar 10, 2014 at 21:50

3 Answers 3

7
\$\begingroup\$

The problem is simply that your two solutions are not equivalent. For example, you would probably not use Array, but barring that, a direct translation of the Java code to Scala would be:

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
    }
    return true
}

However, using an Array in Scala is a bit uncommon, and one would rather use Seq instead. Especially, a LinearSeq promises an efficient tail operation but slow indexing, this is reversed for an IndexedSeq.

@tailrec // remind the compiler that the recursion can be eliminated
def isSorted[A](items: LinearSeq[A], cond: (A, A) => Boolean): Boolean = items match {
  case Seq()     => true  // you forgot to handle empty input!
  case Seq(_)    => true 
  case x :: tail => cond(x, tail.head) && isSorted(tail, cond)
}

But in this specific case, destructuring is actually silly: The isSorted test should male sense for any iterable (let's hope that it terminates, but that isn't our problem). It doesn't actually matter that much here that we can't do much destructuring for a general trait like Iterable. This here is a fairly elegant solution, but I wouldn't make any bets about performance.

def isSorted[A](items: Iterable[A], cond: (A, A) => Boolean): Boolean =
  items.isEmpty || (items zip items.tail forall (pair => cond(pair._1, pair._2)))

The zip method joins two lists pairwise: items = Seq(1, 2, 3, 4) would then produce ((1, 2), (2, 3), (3, 4)).

I am not sure whether any of these solutions would actually be faster – it's to be expected that Scala is a bit slower than Java, but the difference for a careful implementation should not be as large as in your question.


Style notes:

  • Always annotate tail recursive functions with @tailrec (from the scala.annotation package). This will either perform a tail call optimization or produce an error if the compiler is unable to do so.
  • When specifying the type of a variable, put a space after the :, but not before: name: Type. (source)
  • Invoke methods by using ., except when the method is an operator or takes a function as parameter – items.tail instead of items tail (source)
  • In general, the spacing around your operators is inconsistent. A comma should always be followed by a space, and binary operators like = or < should have a space on either side. (source)
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I just compared your last method to his Scala method and your's MUCH faster. The test was an array with 20000 numbered from 0 to 20000. His method took around 5.7 seconds on my machine. Your method took less than 50ms. I couldn't get your @tailrec method to run (I got a MatchError with both mutable and immutable collections). My code: gist.github.com/luiscubal/9476082 (sorry if this is not idiomatic, I'm new to Scala) \$\endgroup\$
    – luiscubal
    Mar 10, 2014 at 22:50
1
\$\begingroup\$

Amon's solution is simple and functional but it doesn't work on arrays and other IndexedSeqs. If you want a general isSorted method that works on any sequential datastructure and is very fast you need to use an iterator.

def isSorted[T](list: Iterable[T])(lt: (T, T) => Boolean): Boolean = {
  @tailrec
  def loop(last: T, iter: Iterator[T]): Boolean = {
    if(!iter.hasNext) true
    else {
      val elem = iter.next
      if(lt(elem, last)) false
      else loop(elem, iter)
    }
  }

  val iter = list.iterator
  !iter.hasNext || loop(iter.next, iter)
}

As far as I know the only way to make this even faster is by specialisation.

\$\endgroup\$
0
\$\begingroup\$

I love languages for their quirks. I would use list and:

def IsSorted(l:List[Int]) = (l, l.tail).zipped.forall(_ <= _)

source: stackoverflow

\$\endgroup\$
1
  • \$\begingroup\$ If you did not get my hint - "If you plan on using something like ´.elements.toList´ then you are better of using list in the first place". \$\endgroup\$
    – Margus
    Jun 25, 2014 at 10:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.