functional programming efficiency vs imperative

Question

I'm new to functional programming and I just ran into something and was wondering if there was a way around this.

Suppose I have

myArray = [
  { a : 1 }
  { a : 4 }
  { a : 5 }
  { a : 6 }
  { a : 7 }
  { a : 8 }
]

Let say I need to do statistical operations on this data set such as

const median = myArray[ Math.ceil( myArray.length / 2 ) ]['a'] // Math.ceil .. Side Effect?
const fiveOrMore = myArray.filter( value => value.a >= 5 )
const lessThanFive = myArray.filter( value => value.a < 5 )

Some arbitrary examples. The problem with this as of right now is that with increasing amount of statistical operations I need to do, the efficiency decreases.

With imperative style, I could do everything in ONE for loop. Is this the wrong approach to functional programming that I am taking or is it a trade off of functional programming paradigm itself?

Answer 1

This is of course less performant. And the performance hit is a trade off of the style you chose.

One may argue that it's not a big deal since the time complexity is O(n), the only difference is the constant. I'd say make sure you preformance-test your app. If it's slow -- it's time to optimize certain blocks of code.

Premature optimization is evil. There will be many cases where imperative code works faster or much faster of muchly much faster than the functional one, and depending on the case you may or may not be okay with that.

Also, there are various techniques to improve the performance. You don't necessarily want to change the style. Say, in some cases memoization can drastically boost the speed of the function, while keeping the code functional. Just think outside the box.

Answer 2

With functional style you could have done it in one reduce too. Just have a function that checks the element is below and the accumulator would be a structure with two lists you are adding elements to.

If you are thinking about passing a list through a series of higher order functions then you can reduce overhead with Trancducers which basically works like individual map, filter but with no lists between the operations.

There are streams which employ lazy evaluation if perhaps you will not be using all the elements in your result.

And there are generators. Basically you can make several for loops and use ỳield to "return" a value and you can chain these since all generators can be iterated with for of. Also here you can halt whenever you have enough data.

So for all these there are pros and cons. Performance wise if you are going to calculate all the elements anyway using generators and streams will have a bit overhead. Transducers is perhaps the better option that gives composability with little list making, but the loop will of course be faster.

Testing is easier with functional implementations and you can test individual stages isolated. One very large loop that rules the whole app is often difficult to debug. This also goes when you have one reduce which just rewrites one loop in a functional style.