100
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ For completeness in comparisons, the below might be included. Extract[test, Position[test[[All, 2]], _?Positive]] Note its near identity, but for the bracketing of the list of positions, with Part[test, Flatten[Position[test[[All, 2]], _?Positive]]] $\endgroup$ Commented Nov 16, 2017 at 17:53

4 Answers 4

Reset to default
61
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ I have a question. As a frequently used built-in function, why select is so slow compared to compiled select even for Select[lst, #[[2]] > 0 &] such a simple and useful case? Select[RandomReal[{-7., 7.}, 10000000], # < 0 &] takes 10 sec, while the compiled version takes 0.37 sec on my computer, it is almost 30 times speed up!! Is Select written in C code? $\endgroup$ Commented Oct 25, 2015 at 15:48
  • $\begingroup$ @matheorem The problem is that non-compiled Select has to make a round-trip through the main evaluator for every element it tests. Top-level evaluation is expensive, so this is slow. When you compile Select together with the predicate passed to it, there is no such round-trip, everything happens in compiled code, at much lower level. This is the reason for the speed-up you see. $\endgroup$ Commented Oct 25, 2015 at 18:02
  • 2
    $\begingroup$ Thank you for your explanation. But I don't understand why mathematica didn't optimize this? At least for such kind of simple implementation that everyone will use, it could add an internal branch as many other built-in function does. In this way, users won't have such a annoying performance issue. What is your opinion? $\endgroup$ Commented Oct 26, 2015 at 0:21
  • 3
    $\begingroup$ @matheorem In this particular case and similar, I agree that Mathematica could try to optimize / autocompile. I don't know why it doesn't do this, it would be a nice improvement if it did. I may file a suggestion for this some time soon. $\endgroup$ Commented Oct 26, 2015 at 8:03
42
$\begingroup$

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
Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ I should have mentioned that this is using version 8. In version 7 and before, Pick was not optimized for packed arrays. $\endgroup$ Commented Jan 17, 2012 at 21:33
11
$\begingroup$

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)

Improve this answer
$\endgroup$
9
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Note that AbsoluteTiming[Length[Select[test, Positive[#[[2]]] &]]] runs slightly faster than the current version. Better to use Positive so as to compare apples to apples I think. $\endgroup$ Commented Jan 17, 2012 at 22:13

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.