Intersection of two sets

[Jan Hönig]

On Wednesday, 4 December 2019 at 08:01:59 UTC, Per Nordlöw wrote:
> On Tuesday, 3 December 2019 at 13:43:26 UTC, Jan Hönig wrote:
>> pseudocode:
>> alias set = bool[<something>]
>> set foo = ...
>> set bar = ...
>> set result;
>
> One simple optimization is to
>
> set* smallest;
> set* largest;
>
> if (foo.length < bar.length)
> {
>     smallest = &foo;
>     largest = &bar;
> }
> else
> {
>     smallest = &bar;
>     largest = &foo;
> }
>
>> foreach(key; *smallest)
>> {
>>   if (key in *largest)
>>   {
>>     result[key] = true;
>>   }
>> }
>> return result;
>
> Provided that your set type has an `in`-operator with 
> time-complexity O(1), this will, in the worst case, reduce time 
> complexity from
>
>     O(max(foo.length, bar.length))
>
> to
>
>     O(min(foo.length, bar.length))

Thanks!
I didn't even thought about optimizations like this :)