Meilleur type de collection Scala pour le calcul numérique vectorisé

Question

Vous recherchez le bon type de données (par exemple IndexedSeq[Double]) à utiliser lors de la conception d'une bibliothèque de calcul numérique spécifique au domaine. Pour cette question, je limite la portée à travailler avec des tableaux 1-Dimensionnels de Double. La bibliothèque définira un nombre de fonctions qui sont généralement appliquées pour chaque élément du tableau 1D.

Considérations:

• Préférez les types de données immuables, telles que Vector ou IndexedSeq
• Vous voulez minimiser les conversions de données
• Raisonnablement efficaces dans l'espace et le temps
• bienvenus pour d'autres personnes utilisant le bibliothèque
• API élégante et propre

Dois-je utiliser quelque chose plus haut dans la hiérarchie des collections, comme Seq?

Ou est-il préférable de définir simplement les fonctions à un seul élément et laisser la cartographie/itérer à l'utilisateur final?

Cela semble moins efficace (puisque certains calculs peuvent être effectuées une fois par ensemble d'appels), mais en même temps une API plus souple, car il travaillerait avec tout type de collection.

Des recommandations?

Answer 1

Si vos calculs sont à faire quoi que ce soit à distance de calculs, utilisez Array, cru ou enveloppé dans vos propres classes. Vous pouvez fournir un wrapper compatible avec la collection, mais en faire un wrapper explicite pour l'interopérabilité uniquement. Tout autre que Array est générique et donc en boîte et donc relativement lent et volumineux.

Si vous n'utilisez pas Array, les utilisateurs seront forcés d'abandonner tout ce que vous avez et il vous suffit d'utiliser Array à la place lorsque les performances sont importantes.Peut-être que c'est bon. Peut-être que vous voulez que les calculs soient là pour plus de commodité et non d'efficacité. Dans ce cas, je suggère d'utiliser IndexedSeq pour l'interface, en supposant que vous voulez faire savoir aux gens que l'indexation n'est pas excessivement lente (par exemple, n'est pas List), et utilisez Vector sous le capot. Vous utiliserez environ 4 fois plus de mémoire que Array[Double], et 3-10x plus lent pour la plupart des opérations à faible effort (par exemple, la multiplication).

Par exemple, ceci:

val u = v.map(1.0/_) // v is Vector[Double] 

est environ trois fois plus lent que ceci:

val u = new Array[Double](v.length) 
var j = 0 
while (j<u.length) { 
    u(j) = 1.0/v(j)  // v is Array[Double] 
    j += 1 
} 

Si vous utilisez la méthode map sur Array, il est tout aussi lent que le chemin Vector[Double]; Les opérations sur Array sont génériques et donc encadrées. (Et c'est là que la majorité de la pénalité vient.)

Answer 2

J'utilise des vecteurs tout le temps quand je traite avec des valeurs numériques, car il offre un accès aléatoire très efficace, ainsi que append/précédez. Notez également que la collection par défaut actuelle pour les séquences indexées immuables est Vector, de sorte que si vous écrivez du code comme for (i <- 0 until n) yield {...}, elle renvoie IndexedSeq[...] mais le type d'exécution est Vector. Il peut donc être judicieux d'utiliser toujours des vecteurs, car certains opérateurs binaires prenant deux séquences en entrée peuvent bénéficier du fait que les deux arguments sont du même type d'implémentation. (Ce n'est pas vraiment le cas maintenant, mais quelqu'un a souligné que la concaténation vectorielle pourrait être en temps log (N), par opposition au temps linéaire actuel du fait que le second paramètre est simplement traité comme une séquence générale.)

Néanmoins, je crois que Seq[Double] devrait déjà fournir la plupart des interfaces de fonctions dont vous avez besoin. Et puisque les résultats de mappage de Range ne donnent pas Vector directement, je mets généralement Seq[Double] comme type d'argument comme mon entrée, de sorte qu'il a une certaine généralité. Je m'attendrais à ce que l'efficacité soit optimisée dans l'implémentation sous-jacente.

Espérons que ça aide.