查找在二維陣列

Question

「列方向」最大假設我有一個二維陣列，例如是這樣的：

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

現在我想有最大中的每個位置的項目。

如果我寫在上面的矩陣形式排列，然後很明顯我的意思是「按列」最大：

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

因此，在這種情況下，答案是Array(50,4,40,1)（空值將被忽略）。

我能做到這一點是這樣的：

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

但不知何故，這種感覺對於這樣一個簡單的事情相當鐵桿。所以我會很感激一個更簡單的方法來做到這一點。

也許有

1）一些函數直接做到這一點？

2）某種方式可以做到「用默認值壓縮」：x1.padTo(x2.length, Int.MinValue).zip(x2.padTo(x1.length,Int.MinValue))更好？

3）改善這一點的其他方法？

Answer 1

使用.tranpose獲得「列」你Array[Array[Int]]的，然後調用.map(_.max)讓所有的最大值：

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) 

---

編輯： .tranpose可能拋出如有異常Array在後面遇到的Array[Array[T]]比第一個更長：

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

如果能在你的情況發生，你可以通過內部數組長度外陣列（按降序排列）總是排序：

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

的transpose答案是正確的。爲了完整起見，存在zipAll函數。摺疊+拉鍊的版本是這樣的：

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

，你可以很容易地編寫並行版本，因爲max是可交換幺，你可以使用reduce（不是左或右）

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

你是在正確的軌道上，這個版本肯定比較快，並且使用的內存比排序+用於大型數組的轉置要少得多，例如

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

你的想法肯定是要走的路，如果你只需要在內存計算max你不想來存儲中間結果（即排序，然後轉）。如果你的矩陣是在一個磁盤上，你甚至不需要加載它，你可以迭代一次行