Fast list-product sign for PackedArray?

Question

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?

Unmanned

Answer 1

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

Obstruction

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. – Unmanned

@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). – Obstruction

@Mr.Wizard: I guess it just shows that basic model of a StackExchange site is a good match to human psychology. (Stupid, lazy humans....) – Obstruction

Answer 2

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

Mettle

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! – Obstruction

@Obstruction 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). – Mettle

@I did not specify, but this method is slow in Mma 7, so I cannot give it the checkmark. – Unmanned