Trouver maximum dans une « colonne sage » tableau à deux dimensions

Question

Supposons que j'ai un tableau à deux dimensions, par exemple comme ceci:

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

Maintenant, je voudrais avoir un maximum d'éléments dans chaque position.

Si j'écris le tableau ci-dessus sous la forme de matrice, alors il est évident que je veux dire par « en colonne » maximale:

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

La réponse dans ce cas serait Array(50,4,40,1) (valeurs vides seraient ignorées).

Je peux le faire comme ceci:

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

mais en quelque sorte cela se sent tout à fait hardcore pour une chose simple comme ça. Donc j'apprécierais une manière plus simple de faire ceci.

Peut-être est

1) Certaines fonctions pour le faire directement?

2) Un moyen de faire ce "zipping avec la valeur par défaut": x1.padTo(x2.length, Int.MinValue).zip(x2.padTo(x1.length,Int.MinValue)) mieux?

3) Une autre façon d'améliorer cela?

Answer 1

Utilisez .tranpose pour obtenir les 'colonnes' de votre Array[Array[Int]], puis appelez .map(_.max) pour obtenir la valeur maximale de tous ceux:

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) 

---

Modifier: .tranpose peut jeter une exception si Array s rencontrés plus tard dans le Array[Array[T]] sont plus longs que les premiers:

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

Si cela peut se produire dans votre cas, vous pouvez toujours trier le tableau extérieur par la longueur des réseaux intérieure (en ordre décroissant):

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

La transpose réponse est correcte. Par souci d'exhaustivité, il existe une fonction zipAll. La version double + zip ressemblerait à ceci:

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

vous pouvez écrire une version parallèle facilement parce que max est un monoïde commutatif et vous pouvez utiliser reduce (pas à gauche ou à droite)

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

Vous étiez sur la bonne voie, cette version est nettement plus rapide et utilise beaucoup moins de mémoire que le tri + Transpose un pour les grands tableaux, par exemple

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

votre idée est certainement le chemin à parcourir, si vous avez seulement besoin de calculer un max vous ne voulez pas stocker les résultats intermédiaires (à savoir trier puis transposer) dans la mémoire.Si votre matrice était sur un disque, vous n'auriez même pas besoin de le charger, vous pourriez juste itérer une fois sur les lignes