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