Самый быстрый способ перечислить диагональные элементы 2D-массива из заданной точки

Question

В 2D-массиве для данной точки наиболее быстрый способ получить диагональные элементы в Scala? Я понимаю, что я могу просто использовать цикл for для прохождения элементов из заданной точки, но он очень похож на Java. Один из способов, которым я придумал, - использовать рекурсивную функцию, которая принимает функцию как аргумент, который вычисляет следующую ячейку. Однако я считаю, что такой метод очень неэффективен. Какой самый идиоматический способ в Скале пройти по диагонали?

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 
} 

Лично я считаю, это менее ясно, чем соответствующий в то время как петли

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, поскольку функциональное программирование и неизменность просто идут очень хорошо. он предлагает два операционных головы и хвоста, которые занимают постоянное время, а сложность времени для обеих операций - 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 
}