Scala列表递归性能

Question

这个问题是关于Scala使用列表及其性能进行模式匹配和递归的方式.

如果我有一个函数可以在列表上进行递归,并且我在一个缺点上进行匹配,例如:

def myFunction(xs) = xs match { 
  case Nil => Nil
  case x :: xs => «something» myFunction(xs)
}

在Haskell:

myFunction [] = []
myFunction (x:xs) = «something» : myFunction xs

我正在使用与我相同的语义,例如,Haskell.我不认为对Haskell实现有任何疑问,因为这只是你处理列表的方式.对于一个很长的列表(我将在一个有几千个节点的列表上运行),Haskell不会眨眼(我想,但我从未尝试过).

但是根据我对Scala的理解,匹配语句将调用unapply提取器方法来围绕缺点拆分列表,并将示例扩展为对列表不执行任何操作的函数:

def myFunction(xs) = xs match { 
  case Nil => Nil
  case x :: xs => x :: myFunction(xs)
}

在Haskell:

myFunction [] = []
myFunction (x:xs) = x : myFunction xs

它会调用apply extractor方法将它重新组合在一起.对于很长的清单,我想这会非常昂贵.

为了说明,在我的特定情况下,我想要递归一个字符列表并累积各种东西,其中输入字符串是几十千字节的任何东西.

如果我想在一个长列表中进行递归,我是否真的会为递归的每一步调用构造函数和提取器？或者有优化吗？还是更好的方法呢？在这种情况下,我需要几个累加器变量,显然我不会只是在列表上做任何事情的递归...

(请原谅我的Haskell,我两年没写过了.)

(是的,我要去尾递归.)

Answer 1

首先,Haskell是非严格的,因此尾部的这些函数调用可能永远不会被评估.另一方面,Scala将在返回之前计算所有列表.对Haskell中发生的事情的更密切实现将是:

def myFunction[T](l: List[T]): Stream[T] = l match {   
  case Nil => Stream.empty  
  case x :: xs => x #:: myFunction(xs)
}

收到一个List严格的,并返回一个Stream非严格的.

现在,如果你想避免模式匹配和提取器(虽然在这种特殊情况下没有调用 - 见下文),你可能只是这样做:

def myFunction[T](xs: List[T]): Stream[T] =
  if (xs.isEmpty) Stream.empty else xs.head #:: myFunction(xs.tail)

我刚刚意识到你打算去尾递归.你写的不是尾递归的,因为你预先x添加了递归的结果.处理列表时,如果向后计算结果然后反转,则会得到尾递归:

def myFunction[T](xs: List[T]): List[T] = {
  def recursion(input: List[T], output: List[T]): List[T] = input match {
    case x :: xs => recursion(xs, x :: output)
    case Nil => output
  }
  recursion(xs, Nil).reverse
}

最后,让我们反编译一个例子,看看它是如何工作的:

class ListExample {
  def test(o: Any): Any = o match {
    case Nil => Nil
    case x :: xs => xs
    case _ => null
  }
}

产生:

public class ListExample extends java.lang.Object implements scala.ScalaObject{
public ListExample();
  Code:
   0:   aload_0
   1:   invokespecial   #10; //Method java/lang/Object."<init>":()V
   4:   return

public java.lang.Object test(java.lang.Object);
  Code:
   0:   aload_1
   1:   astore_2
   2:   getstatic       #18; //Field scala/Nil$.MODULE$:Lscala/Nil$;
   5:   aload_2
   6:   invokestatic    #24; //Method scala/runtime/BoxesRunTime.equals:(Ljava/lang/Object;Ljava/lang/Object;)Z
   9:   ifeq    18
   12:  getstatic       #18; //Field scala/Nil$.MODULE$:Lscala/Nil$;
   15:  goto    38
   18:  aload_2
   19:  instanceof      #26; //class scala/$colon$colon
   22:  ifeq    35
   25:  aload_2
   26:  checkcast       #26; //class scala/$colon$colon
   29:  invokevirtual   #30; //Method scala/$colon$colon.tl$1:()Lscala/List;
   32:  goto    38
   35:  aconst_null
   36:  pop
   37:  aconst_null
   38:  areturn

public int $tag()   throws java.rmi.RemoteException;
  Code:
   0:   aload_0
   1:   invokestatic    #42; //Method scala/ScalaObject$class.$tag:(Lscala/ScalaObject;)I
   4:   ireturn

}

解码时,它首先equals在传递的参数和对象上调用方法Nil.如果为true,则返回后者.否则,它会调用instanceOf[::]该对象.如果为true,则将对象强制转换为该对象,并tl在其上调用该方法.如果做不到这一点,请加载cosntant null并将其返回.

所以,你看,x :: xs不是在调用任何提取器.

至于累积,还有另一种你可能想要考虑的模式:

val list = List.fill(100)(scala.util.Random.nextInt)
case class Accumulator(negative: Int = 0, zero: Int = 0, positive: Int = 0)
val accumulator = list.foldLeft(Accumulator())( (acc, n) => 
  n match {
    case neg if neg < 0 => acc.copy(negative = acc.negative + 1)
    case zero if zero == 0 => acc.copy(zero = acc.zero + 1)
    case pos if pos > 0 => acc.copy(positive = acc.positive + 1)
  })

默认参数和复制方法是我用来简化示例的Scala 2.8特性,但是foldLeft当你想在列表上积累东西时,重点是使用该方法.