Получение наибольших индексов ограниченного элемента в многомерном массиве в 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 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 2

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

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

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

                  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 3

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

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))

Answer 4

Как сказал @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))