3
$\begingroup$

In general

I know to try to use Reap and Sow over Append or AppendTo due to superior performance. However, Reap and Sow are notorious for being difficult to understand how to use and how they work behind the scenes. They really shine when you want to successively accumulate many elements in a list. However, is there any boost in performance in cases where you want to sow/append once into each of many lists?

I know Reap and Sow are good for "vertical" accumulation in relatively few lists. But as the total number of things being sowed approaches the number of things being sowed onto, I expect performance to decrease. If there are as many tags as there are lists (which seems to be what is needed), and there's only one sowing for each list, I don't see how there can be a performance increase over Append, in theory.

In particular

I ask in general, if there is an answer, but I am also looking at optimizing a particular program.

Let list be a list of pairs and let pair be a pair. If pair shares no element with any pair in list, append pair to the end of list. Else, output Nothing.

For example, if list={{18, 2}, {4, 20}, {12, 19}, {6, 15}, {18, 2}} and pair={9, 2}, then the output is Nothing because the 2 appears in some pair in list and in pair. But if pair={5, 3}, then the output is {{18, 2}, {4, 20}, {12, 19}, {6, 15}, {18, 2}, {5, 3}} because no element in pair is shared with any element in any pair in list. The following accomplishes this.

If[DisjointQ[Flatten[list], pair], Append[list, pair], Nothing]

Now, I want to do this with a collection of lists of pairs collectionOfListsOfPairs and a list of pairs listOfPairs, whereby the comparison above is performed between every list of pairs in the collection and every pair in the list. I have a program which accomplishes this.

Table[If[DisjointQ[Flatten[list], pair], Append[list, pair], 
  Nothing],
 {list, collectionOfListsOfPairs}, {pair, listOfPairs}]

So given

collectionOfListsOfPairs = 
{{{18, 2}, {4, 20}, {12, 19}, {6, 15}, {18, 2}}, 
{{7, 9}, {19, 3}, {16, 8}, {11, 12}, {13, 8}}, 
{{16, 8}, {4, 5}, {8, 8}, {4, 5}, {4, 10}}};

listOfPairs = {{9, 2}, {5, 3}, {15, 13}};

my program outputs

{{{{18, 2}, {4, 20}, {12, 19}, {6, 15}, {18, 2}, {5, 3}}}, {}, {{{16, 
    8}, {4, 5}, {8, 8}, {4, 5}, {4, 10}, {9, 2}}, {{16, 8}, {4, 
    5}, {8, 8}, {4, 5}, {4, 10}, {15, 13}}}}

Would using Reap and Sow give better performance than than Append? If so, how would I be able to accomplish this? I am having trouble because I understand how Sow can build lists, but it is more difficult for me to see how Sow can add on to already given lists.

Are there other paradigms available to optimize my program?

Improve this question
$\endgroup$
11
  • $\begingroup$ hmmm...are you given collectionOfListsOfPairs to begin with, or are you constructing it from scratch and we just don't see it here? if you're given it, your problem might not really be amenable to Sow and Reap. However, in any case, your code might be amenable to more functional/built-in improvements, like mapping (/@) and Select, though whether this would actually increase performance or not would need to be tested! $\endgroup$
    – thorimur
    May 25, 2021 at 0:14
  • $\begingroup$ Your thoughts are the same as mine. I can probably uncomfortably tweak things to make collectionOfListsOfPairs using Sow from scratch, but I'm wondering if it is worth it. Even if I could, if there's no performance increase over Append in sowing once into each of many lists (the fundamental question), then there's no point in trying. $\endgroup$
    – Just Some Old Man
    May 25, 2021 at 0:21
  • $\begingroup$ I think it also depends on whether your construction process happens at the same-ish point in time as this appending process, or if this is a "separate" process done to collectionOfListsOfPairs. If the latter, I think it would be hard to make it nice. If the former, though, Sowing each pair with a tag(s) corresponding to which list(s) of pairs it should be included in, and constructing collectionOfListsOfPairs that way from the get-go, might help. It's hard to say without the rest of the code, though—and sometimes performance surprises you even when some paradigm "should" be faster! $\endgroup$
    – thorimur
    May 25, 2021 at 0:28
  • 1
    $\begingroup$ It seems using two MemberQ is faster than DisjointQ and sometimes ContainsAny for your case, Table[With[{l = Flatten[list], p1 = First@pair, p2 = Last@pair}, If[MemberQ[l, p1] || MemberQ[l, p2], Nothing, Append[list, pair]]], {list, collectionOfListsOfPairs}, {pair, listOfPairs}] $\endgroup$
    – Ben Izd
    May 25, 2021 at 5:21
  • 1
    $\begingroup$ @JustSomeOldMan it was a mistake. You're right, it doesn't have any advantage. $\endgroup$
    – Ben Izd
    May 26, 2021 at 18:50

0

Reset to default

Your Answer

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