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

Robert M. Münch robert.muench at saphirion.com
Wed Jun 12 06:57:55 UTC 2019


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



More information about the Digitalmars-d-learn mailing list