On Friday, 8 March 2013 at 19:36:04 UTC, bearophile wrote:
auto firstDistinct(Range)(Range r, in size_t n)
if (isInputRange!Range) {
bool[ForeachType!Range] mySet;
return r.filter!((k) {
if (k in mySet)
return false;
mySet[k] = true;
return true;
}).take(n);
}
I think the standard library of Ada2012 has bounded containers,
so you can use them to stack-allocate a hash set that can
contain up to n items (plus some more free cells to keep its
load factor low enough).
In Rust there are fully safe stack-allocated closures.
Combining the two things it's possible to create a function
like that firstDistinct() with zero heap allocations, that is
probably fast.
Bye,
bearophile
Something goes wrong by the way. I removed "n" template params
and "take(n)" (i can do after distinct() call, isn't it the
same?).
Try this (sorted for better reading):
iota(100).map!((x) =>
uniform(0,10))().distinct().array.sort.writeln;
iota(100).map!((x) =>
uniform(0,10))().array.distinct().array.sort.writeln;
output:
[0, 0, 3, 3, 4, 4, 4, 6, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
