2
$\begingroup$

My understanding is that Mathematica code executes faster when a list is operated on in a functional way (avoiding copies or splitting up the list).

I coded the following to toy with this idea, extracting the elements from a list of integers that satisfy a test-property (say Mod[x,7] == 0)

multiples7Test[x_] := (Mod[x, 7] == 0); myMapIndexed[f_, x_List] := MapIndexed[{f[#1], #2} &, x]; trueCase[x_] := TrueQ[x[[1]]]; pairs[x_] := myMapIndexed[multiples7Test, x]; multiples7Positions[x_] := Position[pairs[x], {_, {_}}?trueCase]; multiples7[x_] := Extract[x, multiples7Positions[x]]

multiples7[Range[30]] produces {7, 14, 21, 28}.

Such code seems to stay close to the "whole-list" approach to gain efficiency. Presumably there is a Mathematica function that efficiently produces a list of elements (from a list of integers) satisfying a given property? I'd like to compare the speeds of various options to check how far the above code is off the (no doubt) highly optimised Mathematica version.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ What about Select[Range[30], Mod[#, 7] == 0 &] ? $\endgroup$ Commented Sep 4, 2022 at 17:17
  • $\begingroup$ Thanks will check it out. $\endgroup$ Commented Sep 4, 2022 at 17:26

1 Answer 1

Reset to default
4
$\begingroup$

Let us consider the following base case:

list = Range[1000000]; AbsoluteTiming[base = multiples7[list];]

{2.34272, Null}

If at all possible, vectorize the test. Consider the following case with Select:

AbsoluteTiming[res1 = Select[list, Mod[#, 7] == 0 &];] res1 == base

{0.579586, Null}

True

If we instead use Mod on the list instead of each element on the list:

AbsoluteTiming[res2 = Pick[#, Mod[#, 7], 0]&[Range[1000000]];] res2 == base

{0.009911, Null}

True

From the inside out, Mod[#, 7] (where # is the range 1-1000000) finds the modulus of each element of the range without needing to call Mod as a function just shy of a million extra times. This is pretty much the entirety of the time savings. Pick is then used to pick everything from the whole range where the modulus turned out to be 0, and is quite fast.

So, if possible, write the test such that it can be vectorized over the whole range you are using it on. Otherwise for a large test range even just calling a simple function a few million times can be a huge time sink.

Also, if possible, consider filtering the range to exclude known bad candidates or constructing it so as to minimize the number of bad candidates from the get go.

AbsoluteTiming[res3 = Range[7, 1000000, 7];] res3 == base

{0.000111, Null}

True

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thanks eyorble. Can you clarify what "write the test such that it can be vectorized over the whole range" means? I am not sure how to interpret vectorized in this context. I looked up Pick in the language documentation, so have some idea of what vectorized could mean, but it is not sharp enough for me to apply it in other contexts. $\endgroup$ Commented Sep 4, 2022 at 19:09
  • $\begingroup$ In this context, vectorized means that the function can automatically map itself over the whole list, as in Mod[list, 7] automatically applying itself to each member of list automatically, and preferably also be evaluated using vectorized functions. To me, Pick isn't the prime example of the vectorization here, it's just a really fast way to pick from one list using another as a selector. $\endgroup$ Commented Sep 4, 2022 at 19:25
  • $\begingroup$ Am I correct in assuming that vectorizable is indicated by "Listable" in Mathematica? That would make sense and help me to identify the cases where we can assume speedy application of an operation to the whole list. $\endgroup$ Commented Sep 4, 2022 at 19:55
  • 1
    $\begingroup$ Listable is going to be the key property to avoiding needing to call the function extra times based on the length of the list, so it should always help with this, yes. Vectorization can refer to a bit more based on how the list actually gets handled at the lower levels, but that's something for Compile if you're going that far. I would expect that Listable has most of the gains, but without a less toy example it's probably harder to say. $\endgroup$ Commented Sep 4, 2022 at 20:14
  • $\begingroup$ Thanks, wonderful answer. It's a bit of a climb to assimilate Mathematica, but loving every step of it. Another insight gained, thanks again. $\endgroup$ Commented Sep 4, 2022 at 20:43

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.