how to get top N distinct elements from range?

Andrea Fontana nospam at example.com
Fri Mar 8 15:41:09 PST 2013


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;
		}
	}

}



More information about the Digitalmars-d-learn mailing list