search

scala / scala-library-next

backwards-binary-compatible Scala standard library additions
Apache License 2.0
67 stars 17 forks source link

Logarithmic reduce #34

Open soronpo opened 3 years ago

soronpo commented 3 years ago

In my use-cases I often found myself requiring a logarithmic reduce that applies LogN operations on a collection, instead of N-1 operations. What do you think? Is this a worthy addition?

NthPortal commented 3 years ago

What do you mean by logarithmic reduce?

Do you mean that it reduces pairs of elements, and the pairs those results and reduces them, until you have a single result? If so, that ends up being n-1 anyway. And even if I'm wrong on that, the first round is n/2, which is O(n) anyway.

I'm pretty sure you can't do better than O(n) for a reduce - it has to touch all of the elements.

soronpo commented 3 years ago

Oh, yes you're right, I'm sorry, I was looking at it from a concurrent perspective where I build a balanced tree of operations to run later. So a regular reduce will be a left/right-side biased. A logarithmic reduce will create a balanced construction of the tree, LogN in height, so with N/2 workers at most each execution unit takes in LogN steps to complete.

NthPortal commented 3 years ago

I think that's more of a parallel collections thing (although it might be doable just with Stepper?)

soronpo commented 3 years ago

There is nothing parallel in the reduce itself. The traversal just needs to be logarithmic.

NthPortal commented 3 years ago

I guess I'm not understanding the value of a method that creates a balanced construction (which inevitably takes up more memory) for O(log(n)) steps if there's no way to parallelise it

Sciss commented 3 years ago

you mean like a finger tree?