how to get top N distinct elements from range?

Ivan Kazmenko gassa at mail.ru
Fri Mar 8 07:04:31 PST 2013


> I wonder if exists a way to get top n distinct elements from a 
> range (infinite too!)

> A (not efficient) way to to this is 
> range.array.sort.uniq.take(n) but it's a bit overkill, it sorts 
> elements, and of course doesn't work with infinite ranges. Am i 
> missing any function?

For an arbitrary infinite range, it is impossible from the 
mathematical point of view.  An impossible example would be doing 
that with the infinite range of natural numbers, stored in 
bignums.

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.


More information about the Digitalmars-d-learn mailing list