Struct TopN
Given a set of data points entered through the put function, this output range
maintains the invariant that the top N according to compFun will be
contained in the data structure. Uses a heap internally, O(log N) insertion
time. Good for finding the largest/smallest N elements of a very large
dataset that cannot be sorted quickly in its entirety, and may not even fit
in memory. If less than N datapoints have been entered, all are contained in
the structure.
struct TopN(T, alias compFun)
;
Constructors
Name | Description |
this
|
The variable ntop controls how many elements are retained.
|
Methods
Name | Description |
getElements
|
Get the elements currently in the struct. Returns a reference to
internal state, elements will be in an arbitrary order. Cheap.
|
getSorted
|
Returns the elements sorted by compFun. The array returned is a
duplicate of the input array. Not cheap.
|
put
|
Insert an element into the topN struct.
|
Examples
Random gen;
gen.seed(unpredictableSeed);
uint[] nums = seq(0U, 100U);
auto less = TopN!(uint, "a < b")(10);
auto more = TopN!(uint, "a > b")(10);
randomShuffle(nums, gen);
foreach(n; nums) {
less.put(n);
more.put(n);
}
assert(less.getSorted == [0U, 1,2,3,4,5,6,7,8,9]);
assert(more.getSorted == [99U, 98, 97, 96, 95, 94, 93, 92, 91, 90]);