49

I want to do exactly what this guy did:

Python - count sign changes

However I need to optimize it to run super fast. In brief I want to take a time series and tell every time it crosses crosses zero (changes sign). I want to record the time in between zero crossings. Since this is real data (32 bit float) I doubt I'll every have a number which is exactly zero, so that is not important. I currently have a timing program in place so I'll time your results to see who wins.

My solution gives (micro seconds):

open data       8384
sign data       8123
zcd data        415466

As you can see the zero-crossing detector is the slow part. Here's my code.

import numpy, datetime

class timer():
    def __init__(self):
        self.t0 = datetime.datetime.now()
        self.t = datetime.datetime.now()
    def __call__(self,text='unknown'):
        print text,'\t',(datetime.datetime.now()-self.t).microseconds
        self.t=datetime.datetime.now()

def zcd(data,t):
    sign_array=numpy.sign(data)
    t('sign data')
    out=[]
    current = sign_array[0]
    count=0
    for i in sign_array[1:]:
        if i!=current:
            out.append(count)
            current=i
            count=0
        else: count+=1
    t('zcd data')
    return out

def main():
    t = timer()
    data = numpy.fromfile('deci.dat',dtype=numpy.float32)
    t('open data')
    zcd(data,t)

if __name__=='__main__':
    main()
Improve this question
5
  • 2
    There is a 'timeit' module, you know? :) Commented Oct 1, 2010 at 21:04
  • Interesting... I like mine better because it can be put throughout a function. You can drop a t() every couple of lines and find bottle necks quickly. If I just wanted to time my function I would have used the linux $ time python zcd.py Commented Oct 1, 2010 at 21:10
  • I am guessing the line time('sign data') is meant to be t('sign data'). Is it? Commented Oct 1, 2010 at 21:23
  • @Muhammad Alkarouri - yeah, thanks. I'll fix that. Commented Oct 4, 2010 at 19:19
  • Possible duplicate of Python - counting sign changes Commented Nov 25, 2016 at 10:17

7 Answers 7

Reset to default
103

What about:

import numpy
a = [1, 2, 1, 1, -3, -4, 7, 8, 9, 10, -2, 1, -3, 5, 6, 7, -10]
zero_crossings = numpy.where(numpy.diff(numpy.sign(a)))[0]

Output:

> zero_crossings
array([ 3,  5,  9, 10, 11, 12, 15])

I.e., zero_crossings will contain the indices of elements before which a zero crossing occurs. If you want the elements after, just add 1 to that array.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

I think you have it backwards; zero_crossings contains the lidices of elements before which a zero crossing occurs, and if you want the elements after you add 1 to the array. Otherwise, excellent, concise answer!
This doesn't work when there is a zero in the array. It will detect them twice! Example: a = [2,1,0,-1,2] will give array([1, 2, 3])
If you're interested only in the count (not in indices), removing all 0s will do. np.where(np.diff(np.sign( [i for i in a if i] )))[0].shape[0]
This almost works as numpy.sign(0) = 0 and numpy.sign(2) = 1 and numpy.sign(-2) = -1. So you likely want numpy.where(numpy.diff(numpy.sign(a) >= 0))[0].
How could this logic be applied to find only the negative-to-positive sign changes? e.g. from the series [-2, -4, -2, 1, 2, 8, -1, -1, 0] I need the output [0, 0, 0, 1, 0 ,0 ,0 ,0, 1]
|
49

As remarked by Jay Borseth the accepted answer does not handle arrays containing 0 correctly.

I propose using:

import numpy as np
a = np.array([-2, -1, 0, 1, 2])
zero_crossings = np.where(np.diff(np.signbit(a)))[0]
print(zero_crossings)
# output: [1]

Since a) using numpy.signbit() is a little bit quicker than numpy.sign(), since it's implementation is simpler, I guess and b) it deals correctly with zeros in the input array.

However there is one drawback, maybe: If your input array starts and stops with zeros, it will find a zero crossing at the beginning, but not at the end...

import numpy as np
a = np.array([0, -2, -1, 0, 1, 2, 0])
zero_crossings = np.where(np.diff(np.signbit(a)))[0]
print(zero_crossings)
# output: [0 2]
Improve this answer

2 Comments

Hmmm, what about $[-2,-1,0,-1,-2,0]$....no crossings just touching, yet an answer. Counting zero as positive is not the final solution either, I guess.
@mikuszefski You are right! [ 1, 2, 0, -1, 0, 0, -1, 2] should yield 2 zero crossings, which it does not.
15

Another way to count zero crossings and squeeze just a few more milliseconds out of the code is to use nonzero and compute the signs directly. Assuming you have a one-dimensional array of data:

def crossings_nonzero_all(data):
    pos = data > 0
    npos = ~pos
    return ((pos[:-1] & npos[1:]) | (npos[:-1] & pos[1:])).nonzero()[0]

Alternatively, if you just want to count the zero crossings for a particular direction of crossing zero (e.g., from positive to negative), this is even faster:

def crossings_nonzero_pos2neg(data):
    pos = data > 0
    return (pos[:-1] & ~pos[1:]).nonzero()[0]

On my machine these are a bit faster than the where(diff(sign)) method (timings for an array of 10000 sine samples containing 20 cycles, 40 crossings in all):

$ python -mtimeit 'crossings_where(data)'
10000 loops, best of 3: 119 usec per loop

$ python -mtimeit 'crossings_nonzero_all(data)'
10000 loops, best of 3: 61.7 usec per loop

$ python -mtimeit 'crossings_nonzero_pos2neg(data)'
10000 loops, best of 3: 55.5 usec per loop
Improve this answer

3 Comments

You can shorten (pos[:-1] & npos[1:]) | (npos[:-1] & pos[1:]) to pos[:-1] ^ npos[1:], where ^ is the XOR operator.
crossings_nonzero_pos2neg([1,2,-1,1,2]) Traceback (most recent call last): File "<ipython-input-3-21f24f68064f>", line 1, in <module> crossings_nonzero_pos2neg([1,2,-1,1,2]) File "<ipython-input-2-80149113a324>", line 2, in crossings_nonzero_pos2neg pos = data > 0 TypeError: '>' not supported between instances of 'list' and 'int'
@Mainland Use "numpy.asarray()" to convert the list before passing it in.
13

Jim Brissom's answer fails if a contains the value 0:

import numpy  
a2 = [1, 2, 1, 1, 0, -3, -4, 7, 8, 9, 10, -2, 1, -3, 5, 6, 7, -10]  
zero_crossings2 = numpy.where(numpy.diff(numpy.sign(a2)))[0]  
print zero_crossings2  
print len(zero_crossings2)  # should be 7

Output:

[ 3  4  6 10 11 12 13 16]  
8

The number of zero crossing should be 7, but because sign() returns 0 if 0 is passed, 1 for positive, and -1 for negative values, diff() will count the transition containing zero twice.

An alternative might be:

a3 = [1, 2, 1, 1, 0, -3, -4, 7, 8, 9, 10, 0, -2, 0, 0, 1, 0, -3, 0, 5, 6, 7, -10]  
s3= numpy.sign(a3)  
s3[s3==0] = -1     # replace zeros with -1  
zero_crossings3 = numpy.where(numpy.diff(s3))[0]  
print s3  
print zero_crossings3  
print len(zero_crossings3)   # should be 7

which give the correct answer of:

[ 3  6 10 14 15 18 21]
7
Improve this answer

4 Comments

Thanks -- I just run into this answer. I wonder if there is an easy way of knowing the "sign" of the zero-crossing (going above 0, or going below 0)? The slope should probably help.
this does not take care of the case where the elements before and after a 0 are of the same sign.
Rather than use numpy.sign, which returns -1, 0, or 1 for negative, zero, or positive, you should just use numpy.where(numpy.diff(a2 > 0))[0]. Or use Dominik Neise's answer, np.signbit.
Unfortunately, this solution does not work with other Python container types, like dique for example. This other solution does, however.
4

Another way that might suit certain applications is to extend the evaluation of the expression np.diff(np.sign(a)).

If we compare how this expression reacts to certain cases:

  1. Rising crossing without zero: np.diff(np.sign([-10, 10])) returns array([2])
  2. Rising crossing with zero: np.diff(np.sign([-10, 0, 10])) returns array([1, 1])
  3. Falling crossing without zero: np.diff(np.sign([10, -10])) returns array([-2])
  4. Falling crossing with zero: np.diff(np.sign([10, 0, -10])) returns array([-1, -1])

So we have to evaluate np.diff(...) for the returned patterns in 1. and 2:

sdiff = np.diff(np.sign(a))
rising_1 = (sdiff == 2)
rising_2 = (sdiff[:-1] == 1) & (sdiff[1:] == 1)
rising_all = rising_1
rising_all[1:] = rising_all[1:] | rising_2

and for the cases 3. and 4.:

falling_1 = (sdiff == -2) #the signs need to be the opposite
falling_2 = (sdiff[:-1] == -1) & (sdiff[1:] == -1)
falling_all = falling_1
falling_all[1:] = falling_all[1:] | falling_2

After this we can easily find the indices with 

indices_rising = np.where(rising_all)[0]
indices_falling = np.where(falling_all)[0]
indices_both = np.where(rising_all | falling_all)[0]

This approach should be reasonable fast because it can manage without using a "slow" loop.

This combines the approach of several other answers.

Improve this answer

Comments

4

I see people using diff a lot in their solutions, but xor seems to be much faster and the result is the same for bools (a good pointer to that might also be the fact that using diff gives a deprecated warning.... :) ) Here is an example:

positive = a2 > 0
np.where(np.bitwise_xor(positive[1:], positive[:-1]))[0]

timeit measures it to be around one and a half faster to diff for me:)

If you do not care about edge cases it might be better to use

positive = np.signbit(a2)

but positive = a2 >0 seems faster (and cleaner) than signbit AND checking for 0s (e.g. positive = np.bitwise_or(np.signbit(a2),np.logical_not(a2)) is slower...)

Improve this answer

Comments

0

Using element-wise multiplication with the shifted array should be the fastest:

X = np.array([ -7,   5,  -9,   4, -10,   6,   3,   3,  -5,   5])
sign_changes = np.signbit(X[1:]*X[:-1]) 
#Prepend 0 to get array of the same size
sign_changes = np.insert(sign_changes, 0, 0)
Improve this answer

1 Comment

This won't find a crossing exactly through zero: [-1,0,1] -> [0,1]*[-1,0] -> [0,0] -> no change detected.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.