Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
1  
When the client does not display the whole dataset at once. Sorting is filtering then. –  Patrick Jan 15 '13 at 15:12
    
Excellent observation. This is also something I'll need to look into. –  Christopher Harris Jan 15 '13 at 15:12
1  
Sorting may be a preprocessing to filtering: think of sort -u –  mouviciel Jan 15 '13 at 15:22
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
Definitely. I appreciate the response. I'm looking for more of a client-side scenario with clear performance benefits, rather than a server-side scenario where every micro-second might count. Most of my lookups will be using a filter function, rather than a dictionary (that's just the nature of the beast I'm working with, for now). –  Christopher Harris Jan 15 '13 at 15:04
    
"One assumes that FRP means you probably aren't using array like structures in the first place." - That's basically what I'm addressing with this question. I'm attempting to create an observable collection which yields all of it's items to all subscribers, but all of it's items are "lifetime" observables which should be "removed" from the subscriber when they complete/dispose. I'm wondering if I should yield those items in order, and provide some sorting functionality, or simply pass the sorting function to the subscriber along with the items in the collection. –  Christopher Harris Jan 15 '13 at 15:09
    
This answer has been revealing and thought provoking. I'll most likely mark this as the answer, unless another answer blindsides me with some kind of revelation. ;) –  Christopher Harris Jan 15 '13 at 15:14
    
assuming the all your subscribers need the same sort I think you could view it as a possible optimization technique there too. of course if different subscribers need different sort orders then this is no longer possible. –  jk. Jan 15 '13 at 15:16
    
The only problem I'm thinking about when assuming all subscribers will have the same sort function, is figuring what to do when the sort function changes. Should all "lifetime" observables be removed and reissued in a sorted manner, should each lifetime have some kind of sorting observable associated with it (number indicating it's place in the sort, for instance), or some other kind of handling. The idea is to make this as "push"-based as possible, and as efficient as possible (within reason, obviously), because this will all be put into a reusable library. –  Christopher Harris Jan 15 '13 at 16:19
add comment

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.

share|improve this answer
1  
+1 yes min/max is another obvious one, of course if you only need min/max then just caching this is probably better which suggests that any data transformation is sort of a caching strategy for the views which use it. –  jk. Jan 15 '13 at 15:44
    
Of course, if min/max is all you need, a linear traversal of the unsorted list (O(n)) is cheaper than sorting (O(n log n)) plus fetching first and last element (O(1) or O(n), depending on the list data structure used). –  tdammers Jan 15 '13 at 17:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.