Elegant way to test if members of array A are present in array B?

[Robert M. Münch]

On 2019-06-11 17:34:00 +0000, Paul Backus said:

> It's a space/time tradeoff. foreach with canFind is O(n^2) time and O(1) space.

Yes, that's why I asekd. They haystack is most likely >10 times larger 
than the needles. Speed has priority.

> If you use an associative array or a set, it's O(n) time and O(n) space.

I don't see how this is the case. The AA itself has some overhead too. 
So, the checking loop is O(n) but the AA lookups not.

> If you sort the arrays and use std.algorithm.setops.setDifference it's 
> O(n*log(n)) time and either O(1) or O(n) space, depending on whether 
> you use an in-place sorting algorithm.

I think I will need some testing to see the effect of different approaches...

-- 
Robert M. Münch
http://www.saphirion.com
smarter | better | faster