Getting the largest indices of a bounded element in a multidimensional array in Scala

Question

I have a multidimensional array:

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

The goal is to find the largest index of dimension V for which there is a bounded element 0 <w0 <= W and return both indices and the value of the element.

I currently have this piece of code that works, but I wonder if there is a more efficient and effective way to do this.

 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

You are really better off with a strong or recursive solution here. I will write a recursive option:

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

Then finder(M,W) should do what you want. Note that this is also effective - without boxing aside from the return value.

---

Change - if you care about performance, here is the execution time of existing solutions on a 100x100 array that has no solutions or one solution at 77% of the way to the end (i.e., the execution time should be about 1/4)

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

The table of results compared to the original method, relative time (less faster, compiled with -optimization, but this hardly matters):

  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 

So, your original method was really faster than all sentences except the recursive one.

Answer 2

The fur is quite similar to the others, but it stops when it finds its target

 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

As @Rex explained, the imperative approach in this case looks simpler

 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

I would write an iterator.

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