如何让我的scala功能更快？

Question

我isSorted在Scala和Java中都有功能.当我测量两个函数的执行时间时,我发现Scala版本非常慢.它运行大约3.2秒为10000 Int但Java版本只运行大约10ms!如何让我的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;
}

有什么建议吗？

我知道这是一个奇怪的代码:)

我想使用Scala,但这种糟糕的表现吓到了我!

Answer 1

您每次迭代都会在Scala中复制整个数组.如果用一个O(n)算法替换算法O(n^2),当然会慢一点!这与Scala与Java甚至模式匹配无关.

如果要使用带尾部的算法,请切换到支持高效尾部的数据结构(例如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)
}

或者,您可以实现与Java相同的算法,因为数组在索引时效率很高:

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
}

或者你可以,如果性能不是非常重要,切换到一些通用但仍然是O(n)算法:

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

这可能比基于索引的版本慢5倍.