2

As a continuation of my previous question, Simon's method to find the list product of a PackedArray is fast, but it does not work with negative values.

This can be "fixed" by Abs with minimal time penalty, but the sign is lost, so I will need to find the product sign separately.

The fastest method that I tried is EvenQ @ Total @ UnitStep[-lst]

lst = RandomReal[{-2, 2}, 5000000];

Do[
  EvenQ@Total@UnitStep[-lst],
  {30}
] // Timing

Out[]= {3.062, Null}

Is there a faster way?

Community
  • 1
  • 1
Mr.Wizard
  • 24,179
  • 5
  • 44
  • 125

2 Answers2

3

This is a little over two times faster than your solution and apart from the nonsense of using Rule@@@ to extract the relevant term, I find it more clear - it simply counts the number elements with each sign.

EvenQ[-1 /. Rule@@@Tally@Sign[lst]]

To compare timings (and outputs)

In[1]:= lst=RandomReal[{-2,2},5000000];
        s=t={};
        Do[AppendTo[s,EvenQ@Total@UnitStep[-lst]],{10}];//Timing
        Do[AppendTo[t,EvenQ[-1/.Rule@@@Tally@Sign[lst]]],{10}];//Timing
        s==t
Out[3]= {2.11,Null}
Out[4]= {0.96,Null}
Out[5]= True
Simon
  • 14,631
  • 4
  • 41
  • 101
  • Well done again, Simon. I tried `Count` but it was slow. I didn't get around to trying `Tally` before I chose to post this question. This site and its helpful people could make me lazy. – Mr.Wizard Mar 15 '11 at 06:09
  • @Mr.Wizard: This site makes me lazy too! Sometimes I spend more time solving other peoples Mma problems than I take before posting mine. (Luckily, in this case, `Tally` was the 2nd thing I tried). – Simon Mar 15 '11 at 06:15
  • @Mr.Wizard: I guess it just shows that basic model of a StackExchange site is a good match to human psychology. (Stupid, lazy humans....) – Simon Mar 15 '11 at 06:26
1

A bit late-to-the-party post: if you are ultimately interested in speed, Compile with the C compilation target seems to be about twice faster than the fastest solution posted so far (Tally - Sign based):

fn = Compile[{{l, _Real, 1}},
  Module[{sumneg = 0},
    Do[If[i < 0, sumneg++], {i, l}];
     EvenQ[sumneg]], CompilationTarget -> "C", 
     RuntimeOptions -> "Speed"];

Here are the timings on my machine:

In[85]:= lst = RandomReal[{-2, 2}, 5000000];
s = t = q = {};
Do[AppendTo[s, EvenQ@Total@UnitStep[-lst]], {10}]; // Timing
Do[AppendTo[t, EvenQ[-1 /. Rule @@@ Tally@Sign[lst]]], {10}]; // Timing
Do[AppendTo[q, fn [lst]], {10}]; // Timing
s == t == q

Out[87]= {0.813, Null}

Out[88]= {0.515, Null}

Out[89]= {0.266, Null}

Out[90]= True
Leonid Shifrin
  • 22,449
  • 4
  • 68
  • 100
  • One of the nice things about Mma is that you normally don't have to write imperative style code... using `Compile` inevitably breaks that - but I guess that it's worth it. Anyway, I've used up my votes for today, but will upvote you soon! – Simon Mar 15 '11 at 23:52
  • 1
    @Simon For a long time I also found the most fun in avoiding procedural constructs in mma, pretty much at all costs. But then, as I started coding more in C and Java, and at the same time I still often had to get the maximal speed out of my mma, my perception changed. The ultimate elegance for me is doing the least work. In mma, it may appear so, since lots is hidden behind the generic functions. But in this problem, for instance, applying Tally and Sign is clearly more (CPU) work than the primitive counting done in C, thus a speed-up (this is not to diminish your truly beautiful solution). – Leonid Shifrin Mar 16 '11 at 22:34
  • @I did not specify, but this method is slow in Mma 7, so I cannot give it the checkmark. – Mr.Wizard Mar 19 '11 at 01:08