Context
I’m currently working on a personal project involving functional reactive JavaScript, and I’ve come up with an odd question. Note that this question is not JavaScript specific, but that is the context in which I am asking it.
Scenario
When filtering a collection of data, you end up with a smaller set of data. Therefore, correctly filtering your data earlier (rather than later) ends up optimizing your later code, as it does not need to iterate through the portion of data which will not be used. (think filtering before mapping, instead of visa-versa)
However, I was wondering if there’s a scenario in which sorting provides similar benefits, or if sorting is generally used as a way of formatting data to be displayed, so that an end user may more easily absorb it (sort by name, city, state, etc).
Question
When is sorting your data more desirable than sorting the corresponding views of that data?
3
Well the obvious answer is that for some data structures knowing that the data is already sorted changes lookups from O(n) to O(log n) e.g. finding an element in an array using binary search rather than linear.
I’m not sure how useful this is to you if you are doing FRP though, one assumes that FRP means you probably aren’t using array like structures in the first place?
I’d also point out that this is a bit different than filter then map. the map gains the benefit of a previous filter without needing any knowledge of the filter. binary search however requires knowing the data is sorted.
5
Various scenarios spring to mind, the textbook ones being searches and finding minimum / maximum values; on a sorted list, searching is typically O(log n) and min/max is O(1), while on an unsorted list, you’ll get O(n) for both.
Besides that, depending on what you need to do with your data, other optimizations may be possible that exploit sortedness of a list – think of things like axis sorting in collision detection.
2