Unterschiedliche Ergebnisse Nulldurchgänge einer großen Sequenz

Question

Diese Frage zu zählen stammen aus Blick auf den zu this Frage gibt Antworten in Bezug auf die Anzahl des zero crossings zu zählen. Es wurden mehrere Antworten gegeben, die das Problem lösen, aber die NumPy appproach zerstörte die anderen bezüglich der Zeit.

Wenn ich vier der Antworten verglichen habe, stelle ich jedoch fest, dass die NumPy-Lösung für große Sequenzen ein anderes Ergebnis liefert. Die vier Antworten sind loop and simple generator, better generator expression und NumPy solution.

Frage: Warum liefert die NumPy-Lösung ein anderes Ergebnis als die anderen drei? (und das ist richtig?)

Hier die Ergebnisse für das Zählen der Anzahl der Nulldurchgänge sind:

Blazing fast NumPy solution 
total time: 0.303605794907 sec 
Zero Crossings Small: 8 
Zero Crossings Med: 54464 
Zero Crossings Big: 5449071 

Loop solution 
total time: 15.6818780899 sec 
Zero Crossings Small: 8 
Zero Crossings Med: 44960 
Zero Crossings Big: 4496847 

Simple generator expression solution 
total time: 16.3374049664 sec 
Zero Crossings Small: 8 
Zero Crossings Med: 44960 
Zero Crossings Big: 4496847 

Modified generator expression solution 
total time: 13.6596589088 sec 
Zero Crossings Small: 8 
Zero Crossings Med: 44960 
Zero Crossings Big: 4496847 

Und den Code verwendet, um die Ergebnisse zu erhalten:

import time 
import numpy as np 

def zero_crossings_loop(sequence): 
    s = 0 
    for ind, _ in enumerate(sequence): 
     if ind+1 < len(sequence): 
      if sequence[ind]*sequence[ind+1] < 0: 
       s += 1 
    return s 

def print_three_results(r1, r2, r3): 
    print 'Zero Crossings Small:', r1 
    print 'Zero Crossings Med:', r2 
    print 'Zero Crossings Big:', r3 
    print '\n' 

small = [80.6, 120.8, -115.6, -76.1, 131.3, 105.1, 138.4, -81.3, -95.3, 89.2, -154.1, 121.4, -85.1, 96.8, 68.2] 
med = np.random.randint(-10, 10, size=100000) 
big = np.random.randint(-10, 10, size=10000000) 

print 'Blazing fast NumPy solution' 
tic = time.time() 
z1 = (np.diff(np.sign(small)) != 0).sum() 
z2 = (np.diff(np.sign(med)) != 0).sum() 
z3 = (np.diff(np.sign(big)) != 0).sum() 
print 'total time: {0} sec'.format(time.time()-tic) 
print_three_results(z1, z2, z3) 

print 'Loop solution' 
tic = time.time() 
z1 = zero_crossings_loop(small) 
z2 = zero_crossings_loop(med) 
z3 = zero_crossings_loop(big) 
print 'total time: {0} sec'.format(time.time()-tic) 
print_three_results(z1, z2, z3) 

print 'Simple generator expression solution' 
tic = time.time() 
z1 = sum(1 for i, _ in enumerate(small) if (i+1 < len(small)) if small[i]*small[i+1] < 0) 
z2 = sum(1 for i, _ in enumerate(med) if (i+1 < len(med)) if med[i]*med[i+1] < 0) 
z3 = sum(1 for i, _ in enumerate(big) if (i+1 < len(big)) if big[i]*big[i+1] < 0) 
print 'total time: {0} sec'.format(time.time()-tic) 
print_three_results(z1, z2, z3) 

print 'Modified generator expression solution' 
tic = time.time() 
z1 = sum(1 for i in xrange(1, len(small)) if small[i-1]*small[i] < 0) 
z2 = sum(1 for i in xrange(1, len(med)) if med[i-1]*med[i] < 0) 
z3 = sum(1 for i in xrange(1, len(big)) if big[i-1]*big[i] < 0) 
print 'total time: {0} sec'.format(time.time()-tic) 
print_three_results(z1, z2, z3) 

Answer 1

Ihre Lösungen unterscheiden in ihrer Behandlung von Null. Die numpy.diff-Lösung gibt immer noch einen Diff von -1 nach 0 oder 1 nach 0 zurück und zählt diese als Nulldurchgang, während Ihre iterativen Lösungen dies nicht tun, weil sie das Produkt als Kriterium verwenden, das kleiner als Null ist. Testen Sie stattdessen für <= 0, und die Nummern werden gleichwertig sein.

Answer 2

Sowohl die iterative als auch die numpy Lösung sind nicht gut beim Zählen von Kreuzungen, wenn ein Datenelement gleich Null ist. Für die Daten [1,0, -1] ergibt die iterative Lösung 0 Kreuzungen und die numpige Lösung 2 Kreuzungen, von denen keine korrekt zu sein scheint.

Eine Lösung wäre, Datenelemente gleich Null zu löschen.In NumPy Sie so etwas wie

def numpy_zero_crossings(data): 
    return (np.diff(np.sign(data)[np.nonzero(data)]) != 0).sum() 

jedoch versuchen könnte, stellt dies eine weitere Iteration durch das Array, so wird es Laufzeit von einem anderen O (n)

Answer 3

Ich erhalte die gleichen Ergebnisse wie die Schleife erhöhen mit:

((array[:-1] * array[1:]) < 0).sum() 

folgt aus:

small = np.array([80.6, 120.8, -115.6, -76.1, 131.3, 105.1, 138.4, -81.3, 
       -95.3, 89.2, -154.1, 121.4, -85.1, 96.8, 68.2]) 
med = np.random.randint(-10, 10, size=100000) 
big = np.random.randint(-10, 10, size=10000000) 

for name, array in [('small', small), ('med', med), ('big', big)]: 
    print('loop ', name, zero_crossings_loop(array)) 
    print('Numpy', name, ((array[:-1] * array[1:]) < 0).sum()) 

druckt:

loop small 8 
Numpy small 8 
loop med 44901 
Numpy med 44901 
loop big 4496911 
Numpy big 4496911 

UDPATE

Diese Version vermeidet das Problem mit Nullen:

def numpy_zero_crossings2(array): 
    nonzero_array = array[np.nonzero(array)] 
    return ((nonzero_array[:-1] * nonzero_array[1:]) < 0).sum() 

Es gibt das gleiche Ergebnis wie die Antwort von @djsutton:

>>> numpy_zero_crossings2(big) == numpy_zero_crossings(big)  
True 

aber seesm ein etwas schneller:

%timeit numpy_zero_crossings2(big) 
1 loops, best of 3: 194 ms per loop 

vs:

%timeit numpy_zero_crossings(big) 
1 loops, best of 3: 227 ms per loop