1

I am having a large array and I want to to multiply every element of array with a given number N. I can do this in following way

val arr  =  Array.fill(100000)(math.random)
val N    =  5.0 
val newArr  =  arr.map (  _ * N )

So this will return me new array as i want. An other way could be

def demo (arr :Array [Double]  , value : Double  ) : Array[Double] ={
var res : Array[Double] = Array()
if (  arr.length == 1  )
  res =  Array (  arr.head  + value  )
else
  res = demo  (  arr.slice(0, arr.length/2) , value   )   ++   demo  (   arr.slice  (  arr.length / 2  ,  arr.length  )  ,  value  )
res
}

I my case I have larger array and I have to perform this operation for Thousands of iterations. I want to ask is there any faster way to get same output? Will tail recursion will increase speed? Or any other technique?

Asif
  • 763
  • 8
  • 18

3 Answers3

6

Presumably you mean arr.head * value.

Neither of these are "faster" in big-O terms; they're both O(N), which makes sense because it's right there in the description: you need to multiply "every" number by some constant.

The only difference is that in the second case you spend a bunch of time slicing and concatenating arrays. So the first one is likely going to be faster. Tail recursion isn't going to help you because this isn't a recursive problem. All you need to do is loop once through the array.

If you have a really huge number of numbers in your array, you could parallelize the multiplication across the available processors (if more than one) by using arr.par.map.

Willis Blackburn
  • 8,068
  • 19
  • 36
2

Tail recursion will be better than regular recursion if you're writing your own function to recursively loop over the list, since tail recursion doesn't fall into Stack issues like regular recursion does.

arr.map(_ * N) should be fine for you though.

Whatever you do, try not to use var. Mutable variables are a code smell in Scala.

Also, when you're dealing with thousands of values it might be worth looking into different collection types like Vector over Array; different collections are efficient at different things. For more information on the performance of collections, check out the official Scala Collections Performance Characteristics page.

James Whiteley
  • 3,363
  • 1
  • 19
  • 46
  • Sometimes `var` is used in libraries or even in Scala Standart Library for optimization purposes – Duelist Dec 11 '19 at 13:11
  • @Duelist I know there are good use cases for using `var`, but it should be used sparingly. Over-use of it is usually a sign of bad code smells so it should be avoided wherever possible as a good habit to get into. – James Whiteley Dec 11 '19 at 13:14
  • `Array` is by far the most efficient collection for multiplying doubles. It's a regular Java array of primitive doubles. It's going to be much more efficient than `Vector`, which has to box/unbox every value. – Willis Blackburn Dec 11 '19 at 13:22
  • @JamesWhiteley Instead of just saying something is a "code smell," it would be more helpful to explain why you think it should be avoided. – Willis Blackburn Dec 11 '19 at 13:35
  • @WillisBlackburn in my experience, over-reliance on `var`s to do simple stuff is often the sign of inefficient or difficult to test code. Keeping everything immutable as much as possible, at least in my experience, leads to easier testing and debugging. [It is not always bad to use `var`](https://stackoverflow.com/a/13097723), but it's a best practice to [*prefer* vals, immutable objects, and methods without side effects. Reach for them first](https://alvinalexander.com/scala/best-practice-prefer-immutable-variables-values-in-scala). – James Whiteley Dec 11 '19 at 13:57
  • You're probably right that Arrays are quicker than Vectors for something like this; I haven't tested it myself, I was just suggesting that it was worth checking that an Array is the best collection to use for your use-case. Nothing more. – James Whiteley Dec 11 '19 at 14:01
0

For multiplying the elements of an array with a number N, the time complexity will be O(N) as you will have to evaluate all the elements of the array. 

arr.map (  _ * N )

IMHO the above code is the optimal solution evaluating it in O(N). But now if your array is very huge, I would recommend you to convert the list to a stream and then perform your transformation.

For example 

arr.toStream.map{ _ * 2}
Chaitanya
  • 3,590
  • 14
  • 33
  • How does `toStream` make it faster? – Willis Blackburn Dec 11 '19 at 13:25
  • 2
    You may have noticed that `arr.toStream.map{_*2}` returns almost instantaneously. That's because it doesn't actually do the multiplication. It just sets up a new collection that will perform the multiplication on demand. If your goal is to do the multiplication for each number, this is a roundabout and much slower way of doing it. – Willis Blackburn Dec 11 '19 at 13:33
  • @WillisBlackburn This avoids creating a new `Array`, so if these are only temporary results it could be a lot faster than a straight `map`. There are also cache advantages when processing very large amounts of data. – Tim Dec 11 '19 at 14:03
  • If the poster just wants to multiply each array element but not retain the result, then simply iterating over the array would be the fastest strategy. Doing the same thing with a stream would be 5 or 10 times slower. – Willis Blackburn Dec 11 '19 at 14:48
  • The array is already in memory, the poster indicates he wants to multiply *every* element, and the sample code suggests he wants to accumulate the results into another array. Lazy streams just aren’t appropriate here. – Willis Blackburn Dec 11 '19 at 14:51