I have an array of objects which all have a timestamp marking when they were last updated. I want to get a subset of the array which has only the most recently updated items. I will be retrieving only 5 elements out of an array of 50 to 100 and performance is my top priority so I am apposed to sorting the entire array with one of the classes methods. What's the best way of doing this?
2
-
1Is the array of fixed size? or is there a stream of objects being pushed on top? Why are you opposed to sorting the array?Samy Arous– Samy Arous2012-06-02 04:28:52 +00:00Commented Jun 2, 2012 at 4:28
-
The array will be fixed in size by the time it's being sorted, but I don't know how large it will be before hand. I'm opposed to sorting the whole thing, not sorting it. I just want it to sort five elements to the top then break. There's no need to sort the rest of the elements because they won't be getting used and the array won't persist so I will see no future performance gains.evanmcdonnal– evanmcdonnal2012-06-02 04:32:35 +00:00Commented Jun 2, 2012 at 4:32
Add a comment
|
2 Answers
I would use a insertion sort and break out once you've selected the required number of elements. This solution have an O(k*n) complexity where k is the number of elements to be extracted.
There are also algorithm that find the Kth largest element in an unsorted array in O(n)
How to find the kth largest element in an unsorted array of length n in O(n)?
Once you have found the Kth largest element X, you can traverse the array and pick all the elements that are greater than X. You are guaranteed to have exactly k-1 element superior to X.
1 Comment
evanmcdonnal
This looks pretty good. I'll accept if no one posts a better answer in the next few hours.
If you have only a 100 elements, then i'd simply sort them. Otherwise, I'd use a heap-based priority queue implementation. O(n) to create, every insert/delete from then on has a O(logn) cost associated with it.
