0
$\begingroup$

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]}]]
$\endgroup$

2 Answers 2

3
$\begingroup$

Why use Intersection at all?

Map[Complement[#, a]&, b] // Cases[{_}]
$\endgroup$
1
  • $\begingroup$ Why didn't I think of this? Thanks! $\endgroup$ Dec 14, 2018 at 23:34
1
$\begingroup$

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][[2]]; // AbsoluteTiming // First
c[[2, 1]] == d["Complements"]

1.05426

0.011678

True

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

$\endgroup$
1
  • 1
    $\begingroup$ 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 &] $\endgroup$ Dec 15, 2018 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.