8

I can do elementwise operation like sum using Zipped function. Let I have two Lists L1 and L2 as shown below

val L1 = List(1,2,3,4)
val L2 = List(5,6,7,8)

I can take element wise sum in following way

(L1,L2).zipped.map(_+_)

and result is 

List(6, 8, 10, 12)

as expected.

I am using Zipped function in my actual code but it takes too much time. In reality My List Size is more than 1000 and I have more than 1000 Lists and my algorithm is iterative where iterations could be up to one billion.

In code I have to do following stuff

list =( (L1,L2).zipped.map(_+_).map (_  * math.random) , L3).zipped.map(_+_)

size of L1,L2 and L3 is same. Moreover I have to execute my actual code on a cluster.

What is the fastest way to take elementwise sum of Lists in Scala?

Lasf
  • 2,536
  • 1
  • 16
  • 35
Asif
  • 763
  • 8
  • 18
  • 1
    If you are looking for runtime efficiency then consider using arrays instead of lists. – Andriy Plokhotnyuk Dec 01 '19 at 13:34
  • @AndriyPlokhotnyuk I try to change List with Array but I do not think that will increase speed. – Asif Dec 01 '19 at 13:37
  • To squeeze more efficiency use pre-allocated arrays to store temporary results and do operations on them using while loops and access by index. – Andriy Plokhotnyuk Dec 01 '19 at 14:26
  • 1
    Moreover, instead of inventing the wheel I would recommend using some efficient linear algebra library like: https://github.com/scalanlp/breeze – Andriy Plokhotnyuk Dec 01 '19 at 15:59
  • 1
    And, in case if you will not be satisfied by performance then try SIMD-based solutions like: https://astojanov.github.io/blog/2017/12/20/scala-simd.html – Andriy Plokhotnyuk Dec 01 '19 at 16:07
  • Also since you said that you would have many big lists and you need to execute this on a cluster, you may consider implement this on a cluster framework like **Spark**. Or simple consider other language instead of **Scala**. – Luis Miguel Mejía Suárez Dec 02 '19 at 11:43
  • @LuisMiguelMejíaSuárez I am using Spark. and inside MapPartitionWithIndex i am converting Iterator to List and performing operation on that List – Asif Dec 02 '19 at 12:08
  • @user12140540 It would be good if you open a new question involving **Spark** also I would not convert the **Iterator** to a **List** you already do an expensive operation there for creating a low performance datastructure. – Luis Miguel Mejía Suárez Dec 02 '19 at 12:14
  • @LuisMiguelMejíaSuárez Thanks and goof recommendation of opening a new question . – Asif Dec 02 '19 at 12:26

1 Answers1

3

One option would be to use a Streaming implementation, taking advantage of the lazyness may increase the performance.

An example using LazyList (introduced in Scala 2.13).

def usingLazyList(l1: LazyList[Double], l2: LazyList[Double], l3: LazyList[Double]): LazyList[Double] =
  ((l1 zip l2) zip l3).map {
    case ((a, b), c) =>
      ((a + b) * math.random()) + c
  }

And an example using fs2.Stream (introduced by the fs2 library).

import fs2.Stream
import cats.effect.IO

def usingFs2Stream(s1: Stream[IO, Double], s2: Stream[IO, Double], s3: Stream[IO, Double]): Stream[IO, Double] =
  s1.zipWith(s2) {
    case (a, b) =>
      (a + b) * math.random()
  }.zipWith(s3) {
    case (acc, c) =>
      acc + c
  }

However, if those are still too slow, the best alternative would be to use plain arrays.

Here is an example using ArraySeq (introduced in Scala 2.13 too) which at least will preserve immutability. You may use raw arrays if you prefer but take care.
(if you want, you may also use the collections-parallel module to be even more performant)

import scala.collection.immutable.ArraySeq
import scala.collection.parallel.CollectionConverters._

def usingArraySeq(a1: ArraySeq[Double], a2: ArraySeq[Double], a3: ArraySeq[Double]): ArraySeq[Double] = {
  val length = a1.length

  val arr = Array.ofDim[Double](length)

  (0 until length).par.foreach { i =>
    arr(i) = ((a1(i) + a2(i)) * math.random()) + a3(i)
  }

  ArraySeq.unsafeWrapArray(arr)
}
Luis Miguel Mejía Suárez
  • 21,686
  • 3
  • 28
  • 45
  • Zipped is faster than Zip. – Asif Dec 02 '19 at 06:07
  • @user12140540 in the **LazyList** example? I doubt it. The advantage of `zipped` over `zip` is that the former is lazy whereas the last is strict. But, since a **LazyList** is already lazy both should behave the same. I supposed that the problem with your code was that each `map` call was actually strict, thus you iterated every list a couple of times, that is why I proposed the use of full _lazy_ collections that will guarantee only one traversal at the end. Or if that wasn't enough for the performance you need, there is nothing that can surpass plain **Array** operations. – Luis Miguel Mejía Suárez Dec 02 '19 at 11:40