3
$\begingroup$

I have a task, where I have to combine pairs with a function, but the number of pairs I actually need is much smaller than the number of all pairs. The condition to keep the element is some function of both elements. Originally, I used something like:

Select[Flatten@Outer[function,array1,array2],condition]

However, this creates a huge computational and memory overhead: it generates the entire matrix (which is quickly bigger than RAM, and also takes time to apply function when I'll just throw it away), and then also takes time to filter.

I was looking for a non-procedural way to do this, and it seems most builtins are oriented towards constructing everything and filtering later. Map is out of the question, so are Table and Array: Even leaving Nulls in the array is an overhead, and using Sequence appeared worse. I ended up writing

ApplyIf[f_, a_, b_, condition_] := 
  Module[{result = {}, n1 = Length[a], n2 = Length[b], i, j},
   For[i = 1, i < n1, i++,
    For[j = 1, j < n2, j++,
     r1 = a[[i]];
     r2 = b[[j]];
     If[condition[r1, r2],
      AppendTo[result, f[r1, r2]];
      ]
     ]
    ];
   result
   ];

which does solve the memory overhead problem, but being procedural, it's not in the spirit of Mathematica, and I'm also concerned with time complexity of AppendTo.

Is there a better way to do this?

Is Reap / Sow advisable in these situations?

Improve this question
$\endgroup$
9
  • $\begingroup$ "the number of pairs I actually need is much smaller than the number of all pairs" -- have you thought about SparseArray to reduce memory usage? $\endgroup$
    – Stitch
    Mar 10, 2017 at 15:49
  • $\begingroup$ @Stitch I still have to go over all pairs to figure out which ones I need. $\endgroup$
    – orion
    Mar 10, 2017 at 15:50
  • 5
    $\begingroup$ Forget about For for good and use Sow/Reap with Do. $\endgroup$
    – Szabolcs
    Mar 10, 2017 at 15:54
  • 1
    $\begingroup$ I often hit the memory limits of my kernels, crashing them. And effective trick I use to avoid both the time complexity of AppendTo and procedural programming is to simply chunk my arrays. Alternatively, Reap and Sow will indeed circumvent the time complexity of AppendTo and by using a Do loop instead of your For loops you can remove the time complexity from all those For tests and incrementations and whatnot. $\endgroup$
    – b3m2a1
    Mar 10, 2017 at 15:56
  • 1
    $\begingroup$ Not only does it avoid a double loop, it also avoids explicit indexing. Instead of Do[f[array[[i]]], {i, Length[array]}] you can use Do[f[elem], {elem, array}]. All this will effectively save you the Module, as you will not need local variables anymore. Reap@Do[If[condition[r1, r2], Sow@f[r1, r2]], {r1, a}, {r2, b}] $\endgroup$
    – Szabolcs
    Mar 10, 2017 at 18:41

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.

Browse other questions tagged or ask your own question.