This is sort of a silly question that's been bugging me.

I have a list of 100k numbers that I am calculating some statistics for. Specifically, I am computing the mean, minimum, maximum, and sum of these numbers. I'm doing it using a fold. In JavaScript:

// define folding functions:
let mean = (a, b, index, array) => a + b / array.length
let max = (a, b) => Math.max(a, b)
let min = (a, b) => Math.min(a, b)
let sum = (a, b) => a + b

let fold = initial => f => data =>
  Math.round(data.reduce(f, initial))

// functions we can consume:
let averageDistance = fold(0)(mean)
let maxDistance = fold(-Infinity)(max)
let minDistance = fold(Infinity)(min)
let totalDistance = fold(0)(sum)

// compute stats:
let data = [1, 2, 3, ...]
let a = averageDistance(data)
let b = maxDistance(data)
let c = minDistance(data)
let d = totalDistance(data)

The time complexity of this is clearly O(n) for each statistic averageDistance, maxDistance, etc. Computed over all 4 statistics, the complexity is O(4n).

Now, I can instead compute all 4 statistics in a single loop, using either a transducer (a similar optimization to Haskell's fusion), or by inlining eveything into a for loop:

let a = 0
let b = -Infinity
let c = Infinity
let d = 0

for (let i = 0; i < data.length; i++) {
  a = mean(a, averageDistance(data[i]), i, data)
  b = max(b, maxDistance(data[i]))
  c = min(c, minDistance(data[i]))
  d = sum(d, totalDistance(data[i]))

This solution only does a single loop, so intuitively it does it in O(n) time (an improvement over 4n from before).

But it still does the same amount of work as before: (100k integers)*(4 statistics) = 400k computations.

Is one solution really faster than another? Is the difference in space complexity (not in time)? If no to both of these, why bother with transducers or fusion at all?

  • 4
    $\begingroup$ Asymptotically (in big O) there is no difference because $O(n) = O(4n)$. If you're looking for the lower bound on exact number of operations, that's a more interesting question. You could shortcut computing the mean explicitly by calculating sum first, then $mean = sum \div n$. This reduces it to $3n$ basic statistic operations. You might be able to reduce it further. $\endgroup$ – ryan Nov 3 '17 at 19:13
  • 2
    $\begingroup$ What is your question? Using Landau notation there is no difference, using exact calculations, there is 3n saving on counter incrementation and test in the loop condition. Going further if your computation does not depend on order going from data.length - 1 to 0 gives cheaper test of condition. Besides, the actual execution depends on compilator, function overhead and produced code. $\endgroup$ – Evil Nov 3 '17 at 22:24
  • $\begingroup$ Here is my silly negligible micro-optimization upon a silly (in fact, interesting) question. Only when you find the number is not bigger than the current $max$, you will test whether it is smaller than the current $min$. This will shove off about $O(\log_2 n)$ operations on average. $\endgroup$ – John L. Aug 8 '18 at 1:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.