Extracting list elements satisfying a property

Question

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.

Answer 1

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