Leistung von numpy.searchsorted ist schlecht auf strukturierten Arrays

Question

_{Sorry im Voraus, wenn ich irgendwelche Begriffe missbrauche, fühlen Sie sich frei, das zu korrigieren.}

Ich habe eine sortierte Array mit dtype'<f16, |S30'. Wenn ich searchsorted auf seinem ersten Feld verwende, arbeitet es wirklich langsam (ungefähr 0,4 Sekunden für 3 Million Einzelteile). Das ist viel länger als bisect dauert, um dasselbe auf einer einfachen Python-Liste von Tupeln zu tun.

%timeit a['f0'].searchsorted(400.) 
1 loops, best of 3: 398 ms per loop 

Allerdings, wenn ich den Schwimmer Teil zum anderen, separaten Array zu kopieren, ist die Suche schneller als bisect:

b = a['f0'].copy() 

%timeit b.searchsorted(400.) 
1000000 loops, best of 3: 945 ns per loop 

Meine Fragen sind:

1. Mache ich etwas falsch oder ist es eine Regression in NumPy?
2. Gibt es eine Möglichkeit, dies zu umgehen, ohne die Daten zu duplizieren?

Answer 1

Ich erinnere mich, das vor einiger Zeit zu sehen. Wenn ich mich richtig erinnere, denke ich, dass searchsorted eine temporäre Kopie der Daten erstellt, wenn die Daten nicht zusammenhängend sind. Wenn ich später Zeit habe, schaue ich mir den Code an, um zu bestätigen, dass das passiert (oder jemand, der mit dem Code vertrauter ist, kann dies bestätigen).

Wenn Sie in der Zwischenzeit Ihren Code nicht restrukturieren möchten, um die Verwendung eines strukturierten Arrays zu vermeiden, verwenden Sie am besten bisect_left(a['f0'], 400.). Auf meinem Rechner ist es 8x langsamer als die Suche in einem zusammenhängenden Array, aber 1000x schneller als in einem nicht zusammenhängenden Array.

In [5]: a = np.arange((6e6)).view([('f0', float), ('f1', float)]) 

In [6]: timeit a['f0'].searchsorted(400.) 
10 loops, best of 3: 51.1 ms per loop 

In [7]: timeit a['f0'].copy() 
10 loops, best of 3: 51 ms per loop 

In [8]: timeit bisect_left(a['f0'], 400.) 
10000 loops, best of 3: 52.8 us per loop 

In [9]: f0 = a['f0'].copy() 

In [10]: timeit f0.searchsorted(400.) 
100000 loops, best of 3: 7.85 us per loop 

Answer 2

Hier ist ein Code, um die Größe des Problems (ab dem 11. Mai 2015) zu veranschaulichen und zu beheben.

import numpy as np 
import bisect 
import timeit 
from random import randint 

dtype = np.dtype([ ('pos','<I'),('sig','<H') ])    # my data is unsigned 32bit, and unsigned 16bit 
data1 = np.fromfile('./all2/840d.0a9b45e8c5344abf6ac761017e93b5bb.2.1bp.binary', dtype) 

dtype2 = np.dtype([('pos',np.uint32),('sig',np.uint32)]) # convert data to both unsigned 32bit 
data2 = data1.astype(dtype2) 

data3 = data2.view(('uint32', len(data2.dtype.names))) # convert above to a normal array (not structured array) 

print data1.dtype.descr # [('pos', '<u4'), ('sig', '<u2')] 
print data2.dtype.descr # [('pos', '<u4'), ('sig', '<u4')] 
print data3.dtype.descr # [('', '<u4')] 

print data1.nbytes # 50344494 
print data2.nbytes # 67125992 
print data3.nbytes # 67125992 

print data1['pos'].max() # 2099257376 
print data2['pos'].max() # 2099257376 
print data3[:,0].max() # 2099257376 

def b1(): return bisect.bisect_left(data1['pos'],   randint(100000000,200000000)) 
def b2(): return bisect.bisect_left(data2['pos'],   randint(100000000,200000000)) 
def b3(): return bisect.bisect_left(data3[:,0],    randint(100000000,200000000)) 
def ss1(): return np.searchsorted(data1['pos'],    randint(100000000,200000000)) 
def ss2(): return np.searchsorted(data2['pos'],    randint(100000000,200000000)) 
def ss3(): return np.searchsorted(data3[:,0],    randint(100000000,200000000)) 

def ricob1(): return bisect.bisect_left(data1['pos'], np.uint32(randint(100000000,200000000))) 
def ricob2(): return bisect.bisect_left(data2['pos'], np.uint32(randint(100000000,200000000))) 
def ricob3(): return bisect.bisect_left(data3[:,0], np.uint32(randint(100000000,200000000))) 
def ricoss1(): return np.searchsorted(data1['pos'], np.uint32(randint(100000000,200000000))) 
def ricoss2(): return np.searchsorted(data2['pos'], np.uint32(randint(100000000,200000000))) 
def ricoss3(): return np.searchsorted(data3[:,0],  np.uint32(randint(100000000,200000000))) 

print timeit.timeit(b1,number=300) # 0.0085117816925 
print timeit.timeit(b2,number=300) # 0.00826191902161 
print timeit.timeit(b3,number=300) # 0.00828003883362 
print timeit.timeit(ss1,number=300) # 6.57477498055 
print timeit.timeit(ss2,number=300) # 5.95308589935 
print timeit.timeit(ss3,number=300) # 5.92483091354 

print timeit.timeit(ricob1,number=300) # 0.00120902061462 
print timeit.timeit(ricob2,number=300) # 0.00120401382446 
print timeit.timeit(ricob3,number=300) # 0.00120711326599 
print timeit.timeit(ricoss1,number=300) # 4.39265394211 
print timeit.timeit(ricoss2,number=300) # 0.00116586685181 
print timeit.timeit(ricoss3,number=300) # 0.00108909606934 

Update! Also dank Ricos Kommentaren scheint es, als würde man den Typ für die Nummer festlegen, die man suchen will. Jedoch auf dem strukturierten Array mit 32bit und 16bit Ints, ist es immer noch langsam (obwohl nein wo fast so langsam wie zuvor)