On Friday, 8 March 2013 at 15:04:32 UTC, Ivan Kazmenko wrote:
For a finite range, you can iterate over the range while maintaining a collection of the top n elements and discarding duplicates as you find them. For example, using a RedBlackTree as the collection, you will get O(log(n) * range.length) total time and O(n) total memory used. If n is small (on the order of 10s), an array will suffice, resulting in O(n * range.length) total time but with lower constant factor.
You can also use an array if you use a BinaryHeap. If you use a heap then it should have a much lower constant factor than a red-black tree so, even though they would both have O(m*log(n)) (where n is the number of elements you want the top of and m is the size of the collection) running time, a heap would be faster.
