14

この質問は、Scala がリストを使用してパターン マッチングと再帰を行う方法と、そのパフォーマンスに関するものです。

リストを再帰する関数があり、コンスでマッチングを行う場合、たとえば次のようになります。

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

ハスケルでは:

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

Haskell などと同じセマンティクスを使用しています。Haskell の実装については疑問の余地はないと思います。それは単にリストを扱う方法だからです。リストが長い場合 (数千ノードのリストを操作することになります)、Haskell は点滅しません (私は想像しますが、試したことはありません)。

しかし、私が Scala で理解していることから、match ステートメントは unapply extractor メソッドを呼び出してリストをコンスで分割し、例をリストに何もしない関数に拡張します。

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

ハスケルでは:

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

apply extractor メソッドを呼び出して、cons をまとめます。長いリストの場合、これは非常に高価になると思います。

説明のために、私の特定のケースでは、文字のリストを再帰してさまざまなものを蓄積したいと考えています。ここで、入力文字列は数十キロバイトまでです。

長いリストを再帰したい場合、再帰の各ステップで本当にコンストラクタとエクストラクタを呼び出すのでしょうか? それとも最適化はありますか？またはそれを行うより良い方法はありますか？この場合、いくつかのアキュムレータ変数が必要になり、何もしないリストを再帰するだけではないことは明らかです...

(私の Haskell を許してください、私は 2 年間 1 行も書いていません。)

(そして、はい、末尾再帰に行きます。)

4

1 に答える 1

19

まず、Haskell は厳密ではないため、末尾のこれらの関数呼び出しはまったく評価されない可能性があります。一方、Scala は、戻る前にすべてのリストを計算します。Haskell で起こることに近い実装は次のようになります。

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

これは厳密なa を受け取り、非厳密なLista を返します。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。それがすべて失敗すると、定数をロードしてnull返します。

つまり、x :: xsextractor を呼び出していません。

蓄積に関しては、考慮したい別のパターンがあります。

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、リストに物を蓄積したい場合にメソッドを使用することです。

于 2009-09-03T14:23:52.253 に答える