It always messes with me: reducing across a specific axis always takes O(whole tensor) time, because there's no difference between "iterate over all dims, then collapse the final one" versus "iterate versus the first dim and do some cursed tensor accum" (and likewise for between)
Maybe there's just a better way to think about it and I'm still thinking about it way too much like a programmer
You "accumulate" an answer one item at a time, but there's no guarantee any dimensions are getting reduced.
You can easily duplicate the effects of map with reduce, for example, so the dims would stay the same. You could even expand dimensions, if you like, turning a 1-d array with n elements into an s X t 2-d array. If the reducing function tracks the total number of elements seen, it can easily know when to start a new row.
This is part of why people keep pointing out the name, "reduce", is a bit misleading.
It always messes with me: reducing across a specific axis always takes O(whole tensor) time, because there's no difference between "iterate over all dims, then collapse the final one" versus "iterate versus the first dim and do some cursed tensor accum" (and likewise for between)
Maybe there's just a better way to think about it and I'm still thinking about it way too much like a programmer
No, reduce has exactly the same time complexity as map and filter.
Sorry I changed problems a bit and started talking about me trying to understand matrices lol
But that's not actually guaranteed at all.
You "accumulate" an answer one item at a time, but there's no guarantee any dimensions are getting reduced.
You can easily duplicate the effects of map with reduce, for example, so the dims would stay the same. You could even expand dimensions, if you like, turning a 1-d array with n elements into an s X t 2-d array. If the reducing function tracks the total number of elements seen, it can easily know when to start a new row.
This is part of why people keep pointing out the name, "reduce", is a bit misleading.