Finding "column-wise" maximum in a two dimensional array

Question

Assume I have a two dimensional Array, for example like this:

val A1 = Array(Array(4,0,0,0),Array(3),Array(3,4,40,1),Array(50,2))

Now I would like to have maximum of items in each position.

If I write the array above in the matrix form then it's obvious what I mean by "column-wise" maximum:

4  0  0 0
3
3  4 40 1
50 2
----------
50 4 40 1 (result)

So the answer in this case would be Array(50,4,40,1) (empty values would be ignored).

I can do it like this:

A1.foldLeft(A1.head)( (x1, x2) =>
  x1.padTo(x2.length, Int.MinValue).zip(x2.padTo(x1.length,Int.MinValue)).
    map { pair => pair._1 max pair._2 }
)

but somehow this feels quite hardcore for a simple thing like this. So I would appreciate a simpler way to do this.

Maybe there is

1) Some function to do this directly?

2) Some way to do this "zipping with default value": x1.padTo(x2.length, Int.MinValue).zip(x2.padTo(x1.length,Int.MinValue)) better?

3) Some other way to improve this?

Answer 1

Use .tranpose to obtain the 'columns' of your Array[Array[Int]], then call .map(_.max) to get the max value of all of those:

scala> val A1 = Array(Array(4,0,0,0),Array(3),Array(3,4,40,1),Array(50,2))
A1: Array[Array[Int]] = Array(Array(4, 0, 0, 0), Array(3), Array(3, 4, 40, 1), Array(50, 2))

scala> A1.transpose
res5: Array[Array[Int]] = Array(Array(4, 3, 3, 50), Array(0, 4, 2), Array(0, 40), Array(0, 1))

scala> A1.transpose.map(_.max)
res6: Array[Int] = Array(50, 4, 40, 1)

---

Edit: .tranpose may throw an exception if Arrays encountered later in the Array[Array[T]] are longer than the first ones:

scala> Array(Array(1,2,3), Array(1,2,3,4)).transpose
java.lang.ArrayIndexOutOfBoundsException: 3
  at scala.collection.mutable.ArrayOps$$anonfun$transpose$1$$anonfun$apply$1.apply(ArrayOps.scala:102)
  at scala.collection.mutable.ArrayOps$$anonfun$transpose$1$$anonfun$apply$1.apply(ArrayOps.scala:101)
  at scala.collection.IndexedSeqOptimized$class.foreach(IndexedSeqOptimized.scala:33)
  at scala.collection.mutable.ArrayOps$ofInt.foreach(ArrayOps.scala:234)
  at scala.collection.mutable.ArrayOps$$anonfun$transpose$1.apply(ArrayOps.scala:101)
  at scala.collection.mutable.ArrayOps$$anonfun$transpose$1.apply(ArrayOps.scala:99)
  at scala.collection.IndexedSeqOptimized$class.foreach(IndexedSeqOptimized.scala:33)
  at scala.collection.mutable.ArrayOps$ofRef.foreach(ArrayOps.scala:186)
  at scala.collection.mutable.ArrayOps$class.transpose(ArrayOps.scala:99)
  at scala.collection.mutable.ArrayOps$ofRef.transpose(ArrayOps.scala:186)
  ... 32 elided

scala> Array(Array(1,2,3,4), Array(1,2,3)).transpose
res5: Array[Array[Int]] = Array(Array(1, 1), Array(2, 2), Array(3, 3), Array(4))

If that can happen in your case you could always sort the outer array by the inner arrays length (in descending order):

scala> Array(Array(1,2,3), Array(1,2,3,4)).sortBy(-_.length).transpose
res6: Array[Array[Int]] = Array(Array(1, 1), Array(2, 2), Array(3, 3), Array(4))

Answer 2

The transpose answer is correct. For the sake of completeness, there exists a zipAll function. The fold+zip version would look like this:

A1.reduceLeft((x1, x2) =>
  x1.zipAll(x2, Int.MinValue, Int.MinValue)
    .map { case (x, y) => x max y }
)

you can write a parallel version easily because max is a commutative monoid and you can use reduce (not left or right)

A1.par.reduce((x1, x2) =>
  x1.zipAll(x2, Int.MinValue, Int.MinValue)
    .map { case (x, y) => x max y }
)

You were on the right track, this version is definitely faster and uses much less memory than the sort+transpose one for large arrays, e.g.

val A1 = Array.fill(100000)(Array.fill(Random.nextInt(100000))(Random.nextInt()))

your idea is definitely the way to go, if you only need to calculate a max you don't want to store intermediate results (i.e. sort, then transpose) in memory. If your matrix was on a disk, you wouldn't even need to load it, you could just iterate once over the rows