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$
3
$\begingroup$

Why use Intersection at all?

Map[Complement[#, a]&, b] // Cases[{_}]
| improve this answer | |
$\endgroup$
  • $\begingroup$ Why didn't I think of this? Thanks! $\endgroup$ – Jerry Guern Dec 14 '18 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"].

| improve this answer | |
$\endgroup$
  • 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$ – Daniel Lichtblau Dec 15 '18 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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