Получение наибольших индексов ограниченного элемента в многомерном массиве в Scala

Question

У меня есть многомерный массив:

val M = Array.ofDim[Int](V, N)

Цель состоит в том, чтобы найти наибольший индекс измерения V, для которого существует ограниченный элемент 0

В настоящее время у меня есть этот фрагмент кода, который работает, но мне интересно, есть ли более хороший и эффективный способ сделать это.

M.zipWithIndex.reverse.collectFirst({
  case (arr, ind) if arr.exists(a => a <= W && a > 0) => {
    arr.zipWithIndex.find(a => a._1 <= W && a._1 > 0) match {
      case Some((weight, ind2)) => (ind, ind2, weight)
    }
  }
})

Answer 1

Вы действительно лучше с императивным или рекурсивным решением здесь. Я напишу рекурсивный:

def finder(arr: Array[Array[Int]], w: Int, i: Int = 0, j: Int = 0): Option[(Int,Int,Int)] = {
  val ri = arr.length-i-1
  if (i >= arr.length) None
  else if (arr(ri)(j) > 0 && arr(ri)(j) < w) Some(ri,j,arr(ri)(j))
  else if (j+1 < arr(i).length) finder(arr,w,i,j+1)
  else finder(arr,w,i+1)
}

затем finder(M,W) должен делать то, что вы хотите. Обратите внимание, что это также эффективно - без бокса, кроме возвращаемого значения.

---

Изменить - если вы заботитесь о производительности, вот время выполнения существующих решений в массиве 100x100, у которого нет решений или одного решения на 77% пути к концу (т. Е. Время выполнения должно составлять около 1/4):

Original without answer:     65 μs / iteration
Original with answer at 1/4: 18 μs / iteration

Таблица результатов по сравнению с оригинальным методом, относительное время, затраченное (чем меньше, тем быстрее, скомпилировано с -optimise, но это вряд ли имеет значение):

                  No Answer    1/4 Answer
Original            1.00          1.00
Rex                 0.55          0.72
4e6                 1.95          7.00
missingfaktor       2.41          1.91
Luigi               4.93          3.92

Таким образом, ваш оригинальный метод был на самом деле быстрее, чем все предложения, за исключением рекурсивного.

Answer 2

Мех, довольно похож на остальных, но останавливается, когда находит цель

def find(M: Array[Array[Int]], W: Int): Option[(Int, Int, Int)] = {
  for {
    x <- M.indices.reverse
    y <- M(x).indices
    a = M(x)(y)
    if 0 < a && a <= W
  } return Some(x, y, a)
  None
}

Answer 3

Как сказал @Rex, императивный подход в этом случае выглядит проще

scala> val m = Array.tabulate(v,n)(_ + _)
m: Array[Array[Int]] = Array(Array(0, 1, 2, 3), Array(1, 2, 3, 4), Array(2, 3, 4, 5))

scala> for { 
     | i <- v-1 to 0 by -1
     | j <- n-1 to 0 by -1
     | if m(i)(j) > 0 && m(i)(j) < 2
     | } yield (i, j, m(i)(j))
res23: scala.collection.immutable.IndexedSeq[(Int, Int, Int)] = Vector((1,0,1), (0,1,1))

scala> res23.headOption
res24: Option[(Int, Int, Int)] = Some((1,0,1))

Answer 4

Я бы написал итератор.

scala> def itr[A](as: Array[Array[A]]) = new Iterator[(Int, Int, A)] {
     |   private var r = 0 
     |   private var c = -1
     |   def next = {
     |     if(c == as(r).length - 1) {
     |       c = 0
     |       r += 1
     |     } else {
     |       c += 1
     |     }
     |     (r, c, as(r)(c))
     |   }
     |   def hasNext = {
     |     !((r == as.length - 1) && (c == as(r).length - 1))
     |   }
     | }
itr: [A](as: Array[Array[A]])java.lang.Object with Iterator[(Int, Int, A)]

scala> val xs = Array.tabulate(5, 6)(_ + _)
xs: Array[Array[Int]] = Array(Array(0, 1, 2, 3, 4, 5), Array(1, 2, 3, 4, 5, 6), Array(2, 3, 4, 5, 6, 7), Array(3, 4, 5, 6, 7, 8), Array(4, 5, 6, 7, 8, 9))

scala> itr(xs).find { case (_, _, x) => 5 < x && x <= 7 }
res19: Option[(Int, Int, Int)] = Some((1,5,6))