# How to get Intersection and Complement at the same time?

In the following example, a is a list of integers, and b is a list of integer triplets. If any triple has two elements in a, I want the 3rd element Sow'd into c. This code works, but every time if finds an intersection of 2 elements, it has to search that long list a again to get the compliment. Is there a way to be more efficient?

a = RandomInteger[10000, 10000];
b = RandomInteger[1000, {300, 3}];
c = Reap[Do[
If[Length[Intersection[a, b[[i]]]] == 2,
Sow[Complement[b[[i]], a]]], {i, 1, Length[b]}]]


## 2 Answers

Why use Intersection at all?

Map[Complement[#, a]&, b] // Cases[{_}]

• Why didn't I think of this? Thanks! – Jerry Guern Dec 14 '18 at 23:34

Better?

a = RandomInteger[30000, 30000];
b = RandomInteger[1000, {300, 3}];
c = Reap[
Do[
If[
Length[Intersection[a, b[[i]]]] == 2,
Sow[Complement[b[[i]], a]]
],
{i, 1, Length[b]}]
]; // AbsoluteTiming // First

nf = Nearest[DeleteDuplicates[a]];
d = Association@Reap[
Do[
intersection = Union @@ nf[x, {1, 0}];
If[Length[intersection] == 2,
Sow[intersection, "Intersections"];
Sow[Complement[x, intersection], "Complements"];
],
{x, b}],
_, Rule][]; // AbsoluteTiming // First
c[[2, 1]] == d["Complements"]


1.05426

0.011678

True

The intersections can be obtained by d["Intersections"].

• To state the underlying principle, if the a list is going to remain the same for many such queries, it is typically more efficient to use a method that preprocesses the long list. An alternative to making a NearestFunction, not quite as fast, is to use Dispatch: removals = Dispatch[Thread[a -> Nothing]]; c2 = Select[b /. removals, Length[#] == 1 &] – Daniel Lichtblau Dec 15 '18 at 16:30