What best practices or performance considerations are there for choosing between Cases, Position, Pick and Select?

Question

Cases, Select,Pick and Position each have different syntaxes and purposes, but there are times when you can express the same calculation equivalently using either of them. So with this input:

test = RandomInteger[{-25, 25}, {20, 2}]

{{-15, 13}, {-8, 16}, {-8, -19}, {7, 6}, {-21, 9}, {-3, -25}, {21, -18}, {4, 4}, {2, -2}, {-24,  8}, {-17, -8}, {4, -18}, {22, -24}, {-4, -3}, {21, 0}, {19,    18}, {-23, -8}, {23, -25}, {14, -2}, {-1, -13}}

You can get the following equivalent results:

Cases[test, {_, _?Positive}]

 {{-15, 13}, {-8, 16}, {7, 6}, {-21, 9}, {4, 4}, {-24, 8}, {19, 18}}

Select[test, #[[2]] > 0 &]

 {{-15, 13}, {-8, 16}, {7, 6}, {-21, 9}, {4, 4}, {-24, 8}, {19, 18}}

Pick[test, Sign[test[[All, 2]] ], 1]

 {{-15, 13}, {-8, 16}, {7, 6}, {-21, 9}, {4, 4}, {-24, 8}, {19, 18}}


test[[Flatten@Position[test[[All, 2]], _?Positive] ]]

 {{-15, 13}, {-8, 16}, {7, 6}, {-21, 9}, {4, 4}, {-24, 8}, {19, 18}}

Are there performance or other considerations that should guide which you should use? For example, is the pattern-matching used in Cases likely to be slower than the functional tests used in Select? Are there any generic rules of thumb, or is testing the particular case you are using the only solution?

Answer 1

In my view, Cases and Position are in one camp (pattern-based functions used for general expression destructuring), while Select is in another: (more) special-purpose functions optimized to work on certain efficient data structures.

As was mentioned already, both Cases and Select do generally unpack when used with packed arrays. What wasn't mentioned is that Select can easily be compiled, including compilation to C:

sel = Compile[{{lst, _Integer, 2}}, Select[lst, #[[2]] > 0 &], 
        CompilationTarget -> "C", RuntimeOptions -> "Speed"];

In[98]:= (res3 = sel[test]);//Timing
Out[98]= {0.125,Null}

which gives an order of magnitude speed-up in the case at hand. Needless to say, Cases, being a general function using patterns, cannot be compiled and any attempt to do so will result in a callback to the main evaluator in the compiled code, which destroys the purpose.

Another difference is that Select can also work on sparse arrays, while Cases and Position can't.

OTOH, Cases and Position are more general in that they can work on arbitrary expressions (not necessarily packed or even regular arrays), and at an arbitrary level. If you happen to have an (even numerical) irregular nested list, where you can't utilize packing, Cases and Position may be able to do things Select can't (Select is limited to one level only). Performance-wise, Cases / Position can also be very efficient, if the test patterns are constructed properly (mostly syntactic patterns, with no Condition or PatternTest involved, and preferably not containing things like __, ___ etc as sub-parts).

There are instances when Cases (Position also, but not as much) are practially indispensable, and this is when you want to collect some information about the expression, while preventing its parts from evaluation. For example, getting all symbols involved in an expression expr, in unevaluated form, wrapped in HoldComplete (say), is as simple as this:

Cases[expr, s_Symbol :> HoldComplete[s], {0, Infinity}, Heads -> True]

and quite efficient as well. Generally, patterns and destructuring are very (perhaps most) powerful metaprogramming tools that Mathematica provides.

So, my final advice is this: when you have an expression with a fixed regular structure, or even better, numerical packed array, Select or other more precise operations (Pick etc) may be advantageous, and also more natural. When you have some general (perhaps symbolic) expression, and want to get some non-trivial information from it, Cases, Position and other pattern-based functions may be a natural choice.

Answer 2

Another useful thing to do when testing such things is to determine whether packed arrays are unpacking. For all of your cases there is a lot of unpacking going on (I've only shown the first of such messages...)

In[1]:= On["Packing"]

In[2]:= test = RandomInteger[{-25, 25}, {10^6, 2}];

In[3]:= (res1 = Cases[test, {_, _?Positive}]); // AbsoluteTiming

During evaluation of In[3]:= Developer`FromPackedArray::punpackl1: Unpacking array with dimensions {1000000,2} to level 1. >>

Out[3]= {1.060814, Null}

In[4]:= (res2 = Select[test, #[[2]] > 0 &]); // AbsoluteTiming

During evaluation of In[4]:= Developer`FromPackedArray::punpackl1: Unpacking array with dimensions {1000000,2} to level 1. >>

Out[4]= {1.856424, Null}

In[5]:= (res3 = 
    test[[Flatten@
       Position[test[[All, 2]], _?Positive]]]); // AbsoluteTiming

During evaluation of In[5]:= Developer`FromPackedArray::unpack: Unpacking array in call to Position. >>


Out[5]= {4.742461, Null}

Now Pick can be written so that it doesn't unpack...

In[6]:= (res4 = Pick[test, Sign[test[[All, 2]]], 1]); // AbsoluteTiming

Out[6]= {0.046801, Null}

In[8]:= Off["Packing"]

In[9]:= res1 == res2 == res3 == res4

Out[9]= True

Answer 3

I disagree with the way some of these tests have been constructed. Firstly test[[All,2]] for positives is quite different from testing test for positives in the second column. When you make these tests an apples v apples comparison the results are quite different:

test = RandomInteger[{-25, 25}, {10^6, 2}];

AbsoluteTiming[Length[test[[Flatten@Position[test[[All, 2]], _?Positive]]]]]
{3.304881, 489913}

IMO Position is the winner of other tests solely because you are only testing the second column.

AbsoluteTiming[Length[Select[test[[All, 2]], Positive]]]
{0.784350, 489913}

AbsoluteTiming[Length[Cases[test[[All, 2]], _?Positive]]]
{1.140218, 489913}

So an apples v apples comparison shows Position to be slowest for this example. More generally sometimes I find Cases a little bit faster than Select, sometimes a little bit slower. Worth testing both each time.

(Note that the above doesn't change the fact that Pick is the fastest answer for this)

Answer 4

A little testing says that at least in this case Position wins hands down:

test = RandomInteger[{-25, 25}, {10^6, 2}];

AbsoluteTiming[Length[Cases[test, {_, _?Positive}]]]
{2.087033, 489565}

AbsoluteTiming[Length[Select[test, #[[2]] > 0 &]]]
{2.265396, 489565}

AbsoluteTiming[Length[test[[Flatten@Position[test[[All, 2]], _?Positive]]]]]
{1.417782, 489565}

There's some variability in the results between runs of the test, but at most a few percent.