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 :)
