0

私はScalaを初めて使用し、これが正しい書き方であるかどうかを知りたいと思っていました。

def createCol(prior: List[Int], current: List[Int]): List[Int] = {
  if (prior.isEmpty) List(1) ++ current
  else if (prior.tail.isEmpty)   // begin of the block to improve
    createCol(prior.tail, current ++ List(prior.head))
  else
    createCol(prior.tail, current ++ List(prior.head + prior.tail.head))
}

私が興味を持っているのはこれです：

if (prior.tail.isEmpty)
  createCol(prior.tail, current ++ List(prior.head))
else
  createCol(prior.tail, current ++ List(prior.head + prior.tail.head))

ほぼ同じ関数呼び出しを繰り返しているcreateColので、代わりにこれを試しました。

val ssum = if (prior.tail.isEmpty) prior.head else prior.head + prior.tail.head
createCol(prior.tail, current ++ List(ssum))

それを行うための最良または推奨される方法は何ですか？

ありがとう

4

2 に答える 2

7

いくつかのポイント：

  1. コードを大幅に簡素化するため、Scalaのパターンマッチングフレームワークを使用するように関数を変更しました。

  2. List(x) ++ someListこれは単一アイテムのリストを不必要に構築するので、そうすべきではありません。prependメソッド::（または+:）を使用する必要があります。（）を追加する場合も同様:+です。

  3. 要素が1つしかない場合は、再帰呼び出しが実行するのは、の前に付加するpriorことだけであることがわかります。したがって、2番目のケースから再帰呼び出しをドロップできます。1current

  4. メソッドは末尾再帰なので、。で注釈を付け@tailrecます。

  5. 最後に、のVector代わりに使用することを検討してListください。メソッドは最後までトラバースする必要があるため（その後、リストを後ろから前に再構築する必要があるため） 、aに追加するのListはO（n）です。ただし、aの先頭と追加はどちらVectorも事実上O（1）です。

それで：

@tailrec
def createCol(prior: List[Int], current: List[Int]): List[Int] = {
  prior match {
    case Nil => 1 :: current
    case head :: Nil => 1 +: current :+ head
    case head :: tail => createCol(tail, current :+ (head + tail.head))
  }
}

質問で説明したように、2つのケースでそれを行うこともできます。ただし、明示的に：headOptionを実行する代わりに、メソッドを使用する必要があります。if/else

@tailrec
def createCol(prior: List[Int], current: List[Int]): List[Int] = {
  prior match {
    case Nil =>
      1 :: current
    case head :: tail =>
      createCol(tail, current ++ List(head + tail.headOption.getOrElse(0)))
  }
}
于 2012-09-26T04:24:54.850 に答える
2

あなたの関数は次のものと同等のようです：

def createCol(prior: List[Int], current: List[Int]) =
  if (prior.isEmpty) 1 :: current
  else 1 :: current ::: (prior, prior.tail :+ 0).zipped.map(_ + _)

またはVector、リストが長い場合は、追加と追加のパフォーマンスが向上するはずです。

def createCol(prior: Vector[Int], current: Vector[Int]) =
  if (prior.isEmpty) 1 +: current
  else (1 +: current) ++ (prior, prior.tail :+ 0).zipped.map(_ + _)

これにより再帰が回避currentされ、変更されていないこと、つまり、前に追加され1ていること、および前の要素がそれ自体と合計され、最後の要素自体（で合計されている0）とのオフセットが1であることがわかり、現在に追加されていることがわかります。

または、（1 +：current）の繰り返しを避けるために：

(1 +: current) ++ (
  if (prior.isEmpty) Vector()
  else (prior, prior.tail :+ 0).zipped.map(_ + _))
于 2012-09-26T08:01:21.237 に答える