19
$\begingroup$

As a simple example of what I would like to do, suppose I have a list a of all real numbers. I would like to perform a simple check to see if some element of a is positive. Of course, I could do this with a simple loop, but I feel as if Mathematica would have a more efficient way of doing this, in the spirit of functional programming. Is there, or do I just have to do this with a clumsy loop:

test=False; For[counter=1;counter<=Length[a];counter++;If[a[[counter]]>0,test=True;];];
$\endgroup$
4
  • 1
    $\begingroup$ A general guidance for how to "map" loop constructions to functional ones is found in this question, see "alternatives to loops" $\endgroup$
    – FredrikD
    Jul 24, 2012 at 5:41
  • $\begingroup$ Thanks for the Accept. You've been away some while. $\endgroup$
    – Mr.Wizard
    Mar 8, 2013 at 3:24
  • $\begingroup$ @Mr.Wizard Sorry about that. Quite honestly, for some reason I thought I had accepted an answer awhile ago, and didn't realize that was not the case until yesterday when I got a notification that I had received a badge for the question. My bad. $\endgroup$ Mar 8, 2013 at 18:46
  • 1
    $\begingroup$ Jonathan, my comment wasn't meant to complain. Frankly I didn't expect to see you on the site again as you had been away for a while. I appreciated you taking the effort to Accept an answer despite the fact that you're apparently not spending a lot of time on the site these days. So thanks again, and welcome back. $\endgroup$
    – Mr.Wizard
    Mar 8, 2013 at 22:29

7 Answers 7

27
$\begingroup$

If I understand you correctly, simply test if the maximum value in the list is Positive:

Positive @ Max @ a

Speed comparison with other methods that were posted:

timeAvg = 
  Function[func,
    Do[If[# > 0.3, Return[#/5^i]] & @@ Timing@Do[func, {5^i}], {i, 0, 15}],
    HoldFirst];

a = RandomInteger[{-1*^7, 2}, 1*^7];

MemberQ[a, _?Positive] // timeAvg

Total@UnitStep[-a] =!= Length@a // timeAvg

Positive@Max@a // timeAvg

0.593

0.0624

0.01148


Early-exit methods

Although very fast, especially with packed lists, the method above does scan the entire list with no possibility for an early exit when a positive elements occurs near the front of the list. In that case a test that does not scan the entire list may be faster, such as the one that R.M posted. Exploring such methods I propose this:

! VectorQ[a, NonPositive]

Unlike MemberQ, VectorQ does not unpack a packed list.

Timings compared to MemberQ and Max, first with an early positive appearance:

SeedRandom[1]
a = RandomReal[{-1*^7, 1000}, 1*^7];

Positive @ Max @ a        // timeAvg
! VectorQ[a, NonPositive] // timeAvg
MemberQ[a, _?Positive]    // timeAvg
0.008736

0.00013984

0.2528

(Most of the MemberQ time is spent unpacking the list.)

Then no positive appearance (full scan):

a = RandomInteger[{-1*^7, 0}, 1*^7];

Positive @ Max @ a        // timeAvg
! VectorQ[a, NonPositive] // timeAvg
MemberQ[a, _?Positive]    // timeAvg
0.01148

1.544

2.528

Finally a mid-range appearance of a positive value in an unpacked list:

a = RandomReal[{-50, 0}, 1*^7];
a[[5*^6]] = 1;

Positive @ Max @ a        // timeAvg
! VectorQ[a, NonPositive] // timeAvg
MemberQ[a, _?Positive]    // timeAvg
0.212

0.702

1.045
$\endgroup$
7
  • 1
    $\begingroup$ You got me, +1 ;) $\endgroup$
    – Rojo
    Jul 24, 2012 at 3:42
  • $\begingroup$ @Rojo you'll get me next time. $\endgroup$
    – Mr.Wizard
    Jul 24, 2012 at 3:44
  • $\begingroup$ You surprised me, didn't know you were prowling around $\endgroup$
    – Rojo
    Jul 24, 2012 at 3:45
  • $\begingroup$ @Rojo prowling now is it? :^) $\endgroup$
    – Mr.Wizard
    Jul 24, 2012 at 3:45
  • $\begingroup$ @Mr.Wizard nice timing - fast machine, is it? $\endgroup$
    – Yves Klett
    Jul 29, 2012 at 13:05
21
$\begingroup$

I think the canonical way would be to use an "any" function which you can find in this question. Using a variant of my answer, you can use

MemberQ[list, _?Positive]

to check if any element is positive.

$\endgroup$
9
  • 1
    $\begingroup$ A variation: MemberQ[Sign[list], 1] $\endgroup$ Jul 24, 2012 at 5:19
  • 2
    $\begingroup$ Very elegant..! $\endgroup$ Jul 24, 2012 at 5:55
  • $\begingroup$ Welcome to the 20K club. $\endgroup$
    – Mr.Wizard
    Jul 24, 2012 at 6:33
  • $\begingroup$ @J.M. I cannot find a case where that is best. Positive @ Max @ a is always faster. The strength of MemberQ[list, _?Positive] is with an unpacked list where a positive element occurs near the beginning. $\endgroup$
    – Mr.Wizard
    Jul 29, 2012 at 6:53
  • 1
    $\begingroup$ @JonathanGleason Yes, most *Q functions yield True or False. I don't know for sure if Q stands for "question", but that's kind of how I reasoned it too. Regarding _?, the relevant doc page is PatternTest. In short, it tests to see if the pattern (here Blank) satisfies the True/False test. Reading the related references and tutorials on this page will also be helpful $\endgroup$
    – rm -rf
    Jul 30, 2012 at 0:49
17
$\begingroup$
l = RandomChoice[Range[-100, 1], 50];

Simplest to understand is

Or @@ Positive[l]

Perhaps faster for long lists is

Total@UnitStep[-l] =!= Length@l
$\endgroup$
1
  • 1
    $\begingroup$ Damn, too quick for me $\endgroup$ Jul 24, 2012 at 3:17
9
$\begingroup$

The fastest I could come up with, using the undocumented Compile`GetElement for indexing (it's the fastest even without):

f = Compile[
  {{l, _Integer, 1}},
  Module[
   {max = -1},
   Do[
    If[max < Compile`GetElement[l, i], max = Compile`GetElement[l, i]],
    {i, 1, Length@l}];
   max > 0
   ],
  CompilationTarget -> "C"
  ]

Using timeAvg from Mr.Wizard's answer,

MemberQ[a, _?Positive] // timeAvg
Total@UnitStep[-a] =!= Length@a // timeAvg
Positive@Max@a // timeAvg
f[a] // timeAvg
(*
1.38034
0.114101
0.0187749
0.00830531
*)
$\endgroup$
5
  • $\begingroup$ No fair! Blasted v8 compile-to-C... $\endgroup$
    – Mr.Wizard
    Jul 30, 2012 at 19:44
  • $\begingroup$ I get error messages for RandomReal input. Should timing include Compileoverhead as well? $\endgroup$
    – Yves Klett
    Jul 31, 2012 at 6:47
  • 2
    $\begingroup$ @Yves he compiled for _Integer values; you'd need to compile a separate function for _Real values, then craft a function to select between them, as well as intelligently handle lists that are not packed and may contain mixed types. I don't think compilation overhead should be included in timings unless it uses pre-calculation. $\endgroup$
    – Mr.Wizard
    Jul 31, 2012 at 11:03
  • $\begingroup$ @YvesKlett As Mr.W says it's compiled for Integers, and would need to be recompiled for reals. I don't know if timing should include compilation overhead; to be honest, I offer this is what I'd do if I needed it to be as fast as possible. It's clearly not leveraging Mathematica's strengths, nor is particularly pretty or clever. $\endgroup$
    – acl
    Jul 31, 2012 at 13:25
  • $\begingroup$ How about a short-circuited version of the loop that keeps testing Compile`GetElement[l, i] until it fins something positive? (i.e., use Break[]) somewhere. $\endgroup$ Apr 17, 2013 at 4:41
6
$\begingroup$

This is even faster than acl's code, for data with positive elements appearing early on, because it stops as soon as it finds a positive.

ff = Compile[{{l, _Real, 1}},
Module[{i = 1, n = Length@l},
While[Compile`GetElement[l, i] <= 0. && i <= n, i = i + 1];
i <= n], "RuntimeOptions" -> "Speed", CompilationTarget -> "C"];

Since the OP specifies real numbers I've changed acl's function to take reals:

f = Compile[{{l, _Real, 1}}, 
Module[{max = -1.},
Do[If[max < Compile`GetElement[l, i], max = Compile`GetElement[l, i]], {i, 1, Length@l}];
max > 0], "RuntimeOptions" -> "Speed", CompilationTarget -> "C"];

Here is some timing data where I've inserted a single positive element into the list at varying positions:

b = RandomReal[{-1*^7, 0}, 1*^7];

timedata = Table[
a = b; a[[10^j]] = 1.0; {10^j,
{MemberQ[a, _?Positive] // timeAvg,
Total@UnitStep[-a] =!= Length@a // timeAvg,
Positive@Max@a // timeAvg,
f[a] // timeAvg,
ff[a] // timeAvg}}
, {j, 1, 7}];

ListLogLogPlot[Transpose[Thread /@ timedata], Joined -> True]

enter image description here

$\endgroup$
7
  • $\begingroup$ This is surely the optimal way to approach this problem (though likely overkill for the OP). Unfortunately I cannot test it in v7, and as a rule I don't vote for v8-only answers. Not because such answers are not good, but because I think it is important to test things, and it would be unfair to vote for some v8 answers and not others. $\endgroup$
    – Mr.Wizard
    Jul 31, 2012 at 12:08
  • $\begingroup$ Somehow after @Mr.Wizard's review no one likes my approach. I'll go and have a proper cry ;-) $\endgroup$
    – Yves Klett
    Jul 31, 2012 at 12:14
  • $\begingroup$ @Mr.Wizard, I agree that it's overkill :-) Especially as the OP was explicitly trying to avoid clumsy loops. $\endgroup$ Jul 31, 2012 at 12:34
  • $\begingroup$ @YvesKlett, it's not so much that I don't like your answer, I just thought it was essentially the same algorithm Rojo's UnitStep approach. By the way, why Tr and not Total ? $\endgroup$ Jul 31, 2012 at 12:39
  • $\begingroup$ Tr is shorter ;-) although similar in spirit the timing is different for Clip and UnitStep approaches. $\endgroup$
    – Yves Klett
    Jul 31, 2012 at 17:38
4
$\begingroup$

To add a bit variety, you could try:

l = RandomChoice[Range[-100, 1], 5000000];

Tr[Clip[l, {0, Infinity}]] > 0

The timing for different methods of input shows that, unsurprisingly, some solutions are very dependent on the average number of positive elements and others not so much. @Mr.Wizard´s Positive@Max@a and @acl´s compiled f[a] seem to win every time.

f = Compile[{{l, _Integer, 1}}, 
   Module[{max = -1}, 
    Do[If[max < Compile`GetElement[l, i], 
      max = Compile`GetElement[l, i]], {i, 1, Length@l}];
    max > 0], CompilationTarget -> "C"];

timeAvg = 
  Function[func, 
   Do[If[# > 0.3, Return[#/5^i]] & @@ Timing@Do[func, {5^i}], {i, 0, 
     15}], HoldFirst];

a = RandomInteger[{-1*^7, 1}, 1*^7];

MemberQ[a, _?Positive] // timeAvg
Or @@ Positive[a] // timeAvg
Total@UnitStep[-a] =!= Length@a // timeAvg
Tr[Clip[a, {0, Infinity}]] > 0 // timeAvg
Positive@Max@a // timeAvg
f[a] // timeAvg
4.072   
0.546     
0.0716     
0.04056     
0.01748     
0.01048
a = RandomInteger[{-1*^7, 1*^7}, 1*^7];

MemberQ[a, _?Positive] // timeAvg
Or @@ Positive[a] // timeAvg
Total@UnitStep[-a] =!= Length@a // timeAvg
Tr[Clip[a, {0, Infinity}]] > 0 // timeAvg
Positive@Max@a // timeAvg
f[a] // timeAvg
0.561     
0.359     
0.078     
1.748     
0.01684     
0.01048
$\endgroup$
4
  • $\begingroup$ If you can find a case where this is faster than Positive @ Max @ list you'll get my vote. If not it's just considerable complication, IMHO. $\endgroup$
    – Mr.Wizard
    Jul 29, 2012 at 19:02
  • $\begingroup$ @Mr.Wizard It definitely is a complication and I do not hold high hopes for getting that vote. $\endgroup$
    – Yves Klett
    Jul 29, 2012 at 21:37
  • $\begingroup$ @YvesKlett, the reason for the much longer timing for your code in the second example is that you are adding up a large number of large integers. If you set the upper bound of Clip to 1 instead of infinity it is quite a bit quicker. $\endgroup$ Jul 31, 2012 at 14:24
  • $\begingroup$ @SimonWoods I thought so too but the timings are not really conclusive. Using Reals for the bounds masssively slows Clip down, though. $\endgroup$
    – Yves Klett
    Jul 31, 2012 at 17:39
1
$\begingroup$

Here is a solution that uses LengthWhile:

test[list_] := Length@list != LengthWhile[list, NonPositive]

This test works well for lists that contain a positive element near the beginning of the list.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.