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

In a 2D array, for a given point what is the fastest way to get the diagonal elements in Scala? I understand that I can simply use a for loop to walk through the elements from a given point, but it feels very java-like. One of the ways I have come up with is to use a recursive function which accepts a function as an argument that calculates the next cell. However I feel such a method is very inefficient. What is the most idiomatic way in Scala to walk through a diagonal?

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

3 个解决方案

#1

Fast functional code in Scala generally involves tail-recursive functions, and fast array access generally involves indexing. So your options are limited.

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

In this case,

在这种情况下,

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
}

Personally, I find this less clear than the corresponding while loop

就我个人而言，我发现这比相应的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
}

but your preferences may vary.

但是你的偏好可能不同。

There are optimization frameworks that will take higher-order index traversal (e.g. for (i <- xss.indices) ans(i) = xss(i)(i)) and change it into the while loop. (ScalaBlitz is one.)

有一些优化框架将进行高阶索引遍历(例如，对于(i <- xss.indices) ans(i) = xss(i))并将其更改为while循环。(ScalaBlitz。)

#2

You can also use Tail recursion and Immutable data-structures like List as functional programming and immutability just go along very well. it offers two operations head and tail which takes constant time and Time-complexity of both operation is O(1).

您还可以使用Tail递归和不可变的数据结构，如List，作为函数式编程和不可变性。它提供了两个操作头和尾，这两个操作都需要常数时间和时间复杂度为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)

#3

Just for fun, some (arguably) more colloquial Scala, noticing that diagonal elements are issued from a rotation of lines, you may use code as follows. It'll be less efficient than a for loop though.

为了好玩，一些(可以说)更口语化的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
}

#1