从给定点列出二维数组对角线元素的最快方法

Question

在二维数组中，对于给定点，在 Scala 中获取对角线元素的最快方法是什么？我知道我可以简单地使用 for 循环从给定点遍历元素，但感觉非常 java-like。我想出的方法之一是使用递归函数，它接受一个函数作为计算下一个单元格的参数。但是我觉得这样的方法效率很低。 Scala 中最惯用的走对角线的方式是什么？

Answer 1

Scala 中的快速函数代码通常涉及尾递归函数，而快速数组访问通常涉及索引。所以你的选择是有限的。

在这种情况下，

def diag(xss: Array[Array[Double]]): Array[Double] = {
  val ans = new Array[Double](xss.length)
  @annotation.tailrec def inner(i: Int) {
    if (i < xss.length) {
      ans(i) = xss(i)(i)
      inner(i+1)
    }
  }
  inner(0)
  ans
}

就个人而言，我发现这不如相应的 while 循环清晰

def diag(xss: Array[Array[Double]]): Array[Double] = {
  val ans = new Array[Double](xss.length)
  var i = 0
  while (i < xss.length) {
    ans(i) = xss(i)(i)
    i += 1
  }
  ans
}

但您的偏好可能会有所不同。

有些优化框架会采用高阶索引遍历（例如for (i <- xss.indices) ans(i) = xss(i)(i)）并将其更改为while循环。（ScalaBlitz 就是其中之一。）

Answer 2

您还可以使用 Tail recursion 和 List 等不可变数据结构，因为函数式编程和不变性非常相配。它提供两个操作 head 和 tail 需要常数时间并且两个操作的时间复杂度是 O(1).

 @annotation.tailrec
  def f(arr: List[List[Int]], res: List[Int] = Nil): List[Int] = {
    if (arr.isEmpty) res
    else 
      f(arr.tail.map(_.tail), res :+ arr.head.head)
  }

  val x = List(List(1, 2, 3, 4), List(5, 6, 7, 8), List(9, 10, 11, 12), List(13, 14, 15, 16))

scala> f(x)
res0: List[Int] = List(1, 6, 11, 16)

Answer 3

只是为了好玩，一些（可以说）更通俗的Scala，注意到对角线元素是由线条的旋转发出的，您可以使用如下代码。不过，它的效率会低于 for 循环。

def diag(m: Array[Array[Int]]) = {
  val (m1, m2) = m.zipWithIndex.
    map{case (l, i) => val (l1, l2) = splitAt(l.size-i); l1 ++ l2}.
    transpose.zipWithIndex.
    map{case (l, i) => l.splitAt(i+1)}.
    unzip
  m1 ++ m2.init
}

从给定点列出二维数组对角线元素的最快方法

Fastest way to list diagonal elements of a 2D array from a given point

arrays

functional-programming

scala