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. 如果prior只有一个元素，你知道所有递归调用要做的就是1在current. 因此，您可以从第二种情况中删除递归调用。

  4. 你的方法是尾递归的，所以用@tailrec.

  5. 最后，考虑使用 aVector而不是List. 追加到 aList是 O(n)，因为方法必须一直遍历到最后（然后从后到前重构 List）。但是添加和附加到 aVector实际上都是 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))
  }
}

您也可以在两种情况下这样做，就像您在问题中描述的那样。但是您应该使用该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如果列表很长，使用 which 应该会产生更好的 prepend 和 append 性能：

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

这避免了递归，我认为更清楚地看到它current没有被修改，它1只是预先添加，并且先验与自身相加，偏移量为 1，最后一个元素本身（与 相加0），然后附加到当前。

甚至避免重复 (1 +: current)：

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