Re: how to get top N distinct elements from range?

[Andrea Fontana]

On Friday, 8 March 2013 at 23:37:20 UTC, Andrea Fontana wrote:
On Friday, 8 March 2013 at 22:36:35 UTC, Andrea Fontana wrote:
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]

Here the answer:

auto r=iota(100).map!((x) => uniform(0,10))();
writeln(r.front," ", r.front, " ", r.front, " ", r.front);

But i think "front" was "cached", but it seems not...
        

This is my "struct" version that helped me to findout that 
problem.

auto distinct(Range)(Range rs) if (isInputRange!(Unqual!Range))
{
        return DistinctResult!Range(rs);
}

struct DistinctResult(Range) if (isInputRange!(Unqual!Range))
{
        alias Unqual!Range T;
        
        T range;
        bool[ElementType!T] justSeen;

        @property front() { return range.front; }
        @property empty() { return range.empty; }
        
        void popFront()
        {
                justSeen[range.front] = true;

                while(true)
                {
                        range.popFront();
                        if (range.empty || range.front !in justSeen) break;
                }
        }

}