Getting the elements in a 2D vector (matrix)

Question

I am searching a vector of vectors for a specific int.

  def searchVectors(i: Int, vectors: Vector[Vector[Int]]) = {
    val x = vectors.indexWhere(_.indexWhere(_ == i))
    val y = vectors(x).indexOf(y)
    (x, y)
  }

You can see I get the y twice. Firstly when computing x and then again when computing y. Not good. How do I do it so I only compute y once?

Thanks

Answer 1

The one approach you can take is to just iterate all vectors:

def searchVectors(x: Int, vec: Vector[Vector[Int]]) =
  for {
    i <- 0 until vec.size
    j <- 0 until vec(i).size
    if vec(i)(j) == x
  } yield (i, j)

Vector also have zipWithIndex method, which adds index to each element of the collection and creates a tuple of them. So you can use it in order to archive the same thing:

def searchVectors(x: Int, vec: Vector[Vector[Int]]) =
  for {
    (subVec, i) <- vec.zipWithIndex
    (elem, j) <- subVec.zipWithIndex
    if elem == x
  } yield (i, j)

The advantage of this approach, is that instead of external (index-based) loop, you are using internal loop with map/flatMap. If you will combine it with views, then you can implement lazy search:

def searchVectors(x: Int, vec: Vector[Vector[Int]]) =
  for {
    (subVec, i) <- vec.view.zipWithIndex
    (elem, j) <- subVec.view.zipWithIndex
    if elem == x
  } yield (i, j)

Not you will still receive collection of results, but it's lazy collection. So if you will take it's head like this:

searchVectors(3, vector).headOption

It will actually perform search (only at this point) and then, when it's found, it would be returned as Option. No further search will be performed.

Answer 2

Here is a more functional approach to do it:

def searchVectors(i: Int, vectors: Vector[Vector[Int]]) = {
  val outer = vectors.toStream map (_.indexOf(i))
  outer.zipWithIndex.filter(_._1 != -1).headOption map (_.swap)
}

EDIT: I think I like this even better:

def searchVectors(i: Int, vectors: Vector[Vector[Int]]) = {
  vectors.toStream.map(_.indexOf(i)).zipWithIndex.collectFirst {
    case (y, x) if y != -1 => (x, y)
  }
}

Converting to a Stream is optional, but probably more efficient because it avoids searching the whole vector if the desired element has already been found.