Numpy: Finden Sie schnell den ersten Wertindex

Wie finde ich den Index des ersten Auftretens einer Zahl in einem Numpy-Array? Geschwindigkeit ist mir wichtig. Die folgenden Antworten interessieren mich nicht, da sie das gesamte Array scannen und nicht aufhören, wenn sie das erste Vorkommen finden:

itemindex = numpy.where(array==item)[0][0]
nonzero(array == item)[0][0]

Anmerkung 1: Keine der Antworten auf diese Frage scheint relevant zu sein. Gibt es eine Numpy-Funktion, um den ersten Index von etwas in einem Array zurückzugeben?

Hinweis 2: Die Verwendung einer C-kompilierten Methode wird einer Python-Schleife vorgezogen.

Für Numpy 2.0.0 ist eine Funktionsanforderung geplant: https://github.com/numpy/numpy/issues/2269

Es ist zwar viel zu spät für Sie, aber für zukünftige Referenz: Die Verwendung von numba ( 1 ) ist der einfachste Weg, bis numpy es implementiert. Wenn Sie eine Anaconda-Python-Distribution verwenden, sollte diese bereits installiert sein. Der Code wird so kompiliert, dass er schnell ist.

@jit(nopython=True)
def find_first(item, vec):
    """return the index of the first occurence of item in vec"""
    for i in xrange(len(vec)):
        if item == vec[i]:
            return i
    return -1

und dann:

>>> a = array([1,7,8,32])
>>> find_first(8,a)
2

Ich habe einen Benchmark für verschiedene Methoden erstellt:

• argwhere
• nonzero wie in der Frage
• .tostring() wie in der Antwort von @Rob Reilink
• Python-Schleife
• Fortran-Schleife

Der Python- und Fortran- Code ist verfügbar. Ich habe die vielversprechenden wie das Konvertieren in eine Liste übersprungen.

Die Ergebnisse im Protokollmaßstab. Die X-Achse ist die Position der Nadel (es dauert länger, um festzustellen, ob sie sich weiter unten im Array befindet). Der letzte Wert ist eine Nadel, die nicht im Array enthalten ist. Die Y-Achse ist die Zeit, um sie zu finden.

Das Array hatte 1 Million Elemente und die Tests wurden 100 Mal ausgeführt. Die Ergebnisse schwanken immer noch ein wenig, aber der qualitative Trend ist klar: Python und f2py werden beim ersten Element beendet, sodass sie unterschiedlich skalieren. Python wird zu langsam, wenn sich die Nadel nicht in den ersten 1% befindet, während f2pyes schnell ist (aber Sie müssen es kompilieren).

Zusammenfassend ist f2py die schnellste Lösung , insbesondere wenn die Nadel ziemlich früh erscheint.

Es ist nicht eingebaut, was nervt, aber es sind wirklich nur 2 Minuten Arbeit. Fügen Sie dies einer Datei mit dem Namen hinzu search.f90:

subroutine find_first(needle, haystack, haystack_length, index)
    implicit none
    integer, intent(in) :: needle
    integer, intent(in) :: haystack_length
    integer, intent(in), dimension(haystack_length) :: haystack
!f2py intent(inplace) haystack
    integer, intent(out) :: index
    integer :: k
    index = -1
    do k = 1, haystack_length
        if (haystack(k)==needle) then
            index = k - 1
            exit
        endif
    enddo
end

Wenn Sie nach etwas anderem suchen integer, ändern Sie einfach den Typ. Dann kompilieren Sie mit:

f2py -c -m search search.f90

Danach können Sie (aus Python):

import search
print(search.find_first.__doc__)
a = search.find_first(your_int_needle, your_int_array)

Sie können ein boolesches Array array.tostring()mithilfe der find () -Methode in einen Python-String konvertieren :

(array==item).tostring().find('\x01')

Dies beinhaltet jedoch das Kopieren der Daten, da Python-Zeichenfolgen unveränderlich sein müssen. Ein Vorteil ist, dass Sie auch zB nach einer steigenden Flanke suchen können\x00\x01

Bei sortierten Arrays np.searchsortedfunktioniert.

Ich denke, Sie sind auf ein Problem gestoßen, bei dem eine andere Methode und einige a priori Kenntnisse des Arrays wirklich helfen würden. Die Art von Dingen, bei denen Sie eine X-Wahrscheinlichkeit haben, Ihre Antwort im ersten Y-Prozent der Daten zu finden. Die Aufteilung des Problems in der Hoffnung, Glück zu haben, dann in Python mit einem verschachtelten Listenverständnis oder so.

Das Schreiben einer C-Funktion für diese Brute Force ist auch mit ctypes nicht allzu schwierig .

Der C-Code, den ich zusammen gehackt habe (index.c):

long index(long val, long *data, long length){
    long ans, i;
    for(i=0;i<length;i++){
        if (data[i] == val)
            return(i);
    }
    return(-999);
}

und die Python:

# to compile (mac)
# gcc -shared index.c -o index.dylib
import ctypes
lib = ctypes.CDLL('index.dylib')
lib.index.restype = ctypes.c_long
lib.index.argtypes = (ctypes.c_long, ctypes.POINTER(ctypes.c_long), ctypes.c_long)

import numpy as np
np.random.seed(8675309)
a = np.random.random_integers(0, 100, 10000)
print lib.index(57, a.ctypes.data_as(ctypes.POINTER(ctypes.c_long)), len(a))

und ich bekomme 92.

Wickeln Sie die Python in eine richtige Funktion und los geht's.

Die C-Version ist für diesen Samen viel (~ 20x) schneller (Warnung, ich bin nicht gut mit Timeit)

import timeit
t = timeit.Timer('np.where(a==57)[0][0]', 'import numpy as np; np.random.seed(1); a = np.random.random_integers(0, 1000000, 10000000)')
t.timeit(100)/100
# 0.09761879920959472
t2 = timeit.Timer('lib.index(57, a.ctypes.data_as(ctypes.POINTER(ctypes.c_long)), len(a))', 'import numpy as np; np.random.seed(1); a = np.random.random_integers(0, 1000000, 10000000); import ctypes; lib = ctypes.CDLL("index.dylib"); lib.index.restype = ctypes.c_long; lib.index.argtypes = (ctypes.c_long, ctypes.POINTER(ctypes.c_long), ctypes.c_long) ')
t2.timeit(100)/100
# 0.005288000106811523

@tal hat bereits eine numbaFunktion zum Auffinden des ersten Index vorgestellt, die jedoch nur für 1D-Arrays funktioniert. Mit finden np.ndenumerateSie auch den ersten Index in einem arbitarisch dimensionierten Array:

from numba import njit
import numpy as np

@njit
def index(array, item):
    for idx, val in np.ndenumerate(array):
        if val == item:
            return idx
    return None

Beispielfall:

>>> arr = np.arange(9).reshape(3,3)
>>> index(arr, 3)
(1, 0)

Das Timing zeigt, dass die Leistung der Tals- Lösung ähnlich ist :

arr = np.arange(100000)
%timeit index(arr, 5)           # 1000000 loops, best of 3: 1.88 µs per loop
%timeit find_first(5, arr)      # 1000000 loops, best of 3: 1.7 µs per loop

%timeit index(arr, 99999)       # 10000 loops, best of 3: 118 µs per loop
%timeit find_first(99999, arr)  # 10000 loops, best of 3: 96 µs per loop

Wenn Ihre Liste sortiert ist , können Sie mit dem Paket 'bisect' eine sehr schnelle Indexsuche durchführen. Es ist O (log (n)) anstelle von O (n).

bisect.bisect(a, x)

Findet x im Array a, im sortierten Fall definitiv schneller als jede C-Routine, die alle ersten Elemente durchläuft (für ausreichend lange Listen).

Es ist manchmal gut zu wissen.

Soweit ich weiß, sind nur np.any und np.all auf booleschen Arrays kurzgeschlossen.

In Ihrem Fall muss numpy das gesamte Array zweimal durchlaufen, einmal, um die boolesche Bedingung zu erstellen, und ein zweites Mal, um die Indizes zu finden.

Meine Empfehlung in diesem Fall wäre, Cython zu verwenden. Ich denke, es sollte einfach sein, ein Beispiel für diesen Fall anzupassen, insbesondere wenn Sie nicht viel Flexibilität für verschiedene d-Typen und Formen benötigen.

Ich brauchte das für meinen Job, also brachte ich mir Python und Numpys C-Oberfläche bei und schrieb meine eigene. http://pastebin.com/GtcXuLyd Es ist nur für 1-D-Arrays geeignet, funktioniert jedoch für die meisten Datentypen (int, float oder string). Tests haben gezeigt, dass es erneut etwa 20-mal schneller ist als der erwartete Ansatz in reinem Python- numpy.

Dieses Problem kann in reiner Zahl effektiv gelöst werden, indem das Array in Blöcken verarbeitet wird:

def find_first(x):
    idx, step = 0, 32
    while idx < x.size:
        nz, = x[idx: idx + step].nonzero()
        if len(nz): # found non-zero, return it
            return nz[0] + idx
        # move to the next chunk, increase step
        idx += step
        step = min(9600, step + step // 2)
    return -1

Das Array wird in großen Teilen verarbeitet step. Je steplänger der Schritt ist, desto schneller wird das Null-Array verarbeitet (Worst-Case). Je kleiner es ist, desto schneller wird das Array mit Null ungleich verarbeitet. Der Trick besteht darin, mit einem kleinen zu beginnen stepund es exponentiell zu erhöhen. Darüber hinaus ist es aufgrund begrenzter Vorteile nicht erforderlich, diese Schwelle zu überschreiten.

Ich habe die Lösung mit der reinen Lösung ndarary.nonzero und numba mit 10 Millionen Floats verglichen.

import numpy as np
from numba import jit
from timeit import timeit

def find_first(x):
    idx, step = 0, 32
    while idx < x.size:
        nz, = x[idx: idx + step].nonzero()
        if len(nz):
            return nz[0] + idx
        idx += step
        step = min(9600, step + step // 2)
    return -1

@jit(nopython=True)
def find_first_numba(vec):
    """return the index of the first occurence of item in vec"""
    for i in range(len(vec)):
        if vec[i]:
            return i
    return -1


SIZE = 10_000_000
# First only
x = np.empty(SIZE)

find_first_numba(x[:10])

print('---- FIRST ----')
x[:] = 0
x[0] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=1000), 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=1000), 'ms')

print('---- LAST ----')
x[:] = 0
x[-1] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

print('---- NONE ----')
x[:] = 0
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

print('---- ALL ----')
x[:] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

Und Ergebnisse auf meiner Maschine:

---- FIRST ----
ndarray.nonzero 54.733994480002366 ms
find_first 0.0013148509997336078 ms
find_first_numba 0.0002839310000126716 ms
---- LAST ----
ndarray.nonzero 54.56336712999928 ms
find_first 25.38929685000312 ms
find_first_numba 8.022820680002951 ms
---- NONE ----
ndarray.nonzero 24.13432420999925 ms
find_first 25.345200140000088 ms
find_first_numba 8.154927100003988 ms
---- ALL ----
ndarray.nonzero 55.753537260002304 ms
find_first 0.0014760300018679118 ms
find_first_numba 0.0004358099977253005 ms

Pure ndarray.nonzeroist definitiv lockerer. Die Numba-Lösung ist im besten Fall etwa fünfmal schneller. Im schlimmsten Fall ist es ungefähr dreimal schneller.

Wenn Sie nach dem ersten Nicht-Null-Element suchen, können Sie einen folgenden Hack verwenden:

idx = x.view(bool).argmax() // x.itemsize
idx = idx if x[idx] else -1

Es ist eine sehr schnelle "numpy-pure" Lösung, die jedoch in einigen unten diskutierten Fällen fehlschlägt.

Die Lösung nutzt die Tatsache, dass so gut wie die gesamte Darstellung von Null für numerische Typen aus 0Bytes besteht . Dies gilt auch für Numpys bool. In neueren Versionen von numpy argmax()verwendet die Funktion bei der Verarbeitung des boolTyps eine Kurzschlusslogik . Die Größe von boolist 1 Byte.

Man muss also:

• Erstellen Sie eine Ansicht des Arrays als bool. Es wird keine Kopie erstellt
• Verwenden Sie argmax()diese Option, um das erste Byte ungleich Null mithilfe der Kurzschlusslogik zu finden
• Berechnen Sie den Versatz dieses Bytes zum Index des ersten Nicht-Null-Elements durch ganzzahlige Division (Operator //) des Versatzes durch die Größe eines einzelnen Elements, ausgedrückt in Bytes ( x.itemsize).
• Überprüfen Sie, ob x[idx]tatsächlich nicht Null ist, um den Fall zu identifizieren, in dem keine Nicht-Null vorhanden ist

Ich habe einen Benchmark gegen die Numba-Lösung erstellt und sie erstellt np.nonzero.

import numpy as np
from numba import jit
from timeit import timeit

def find_first(x):
    idx = x.view(bool).argmax() // x.itemsize
    return idx if x[idx] else -1

@jit(nopython=True)
def find_first_numba(vec):
    """return the index of the first occurence of item in vec"""
    for i in range(len(vec)):
        if vec[i]:
            return i
    return -1


SIZE = 10_000_000
# First only
x = np.empty(SIZE)

find_first_numba(x[:10])

print('---- FIRST ----')
x[:] = 0
x[0] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=1000), 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=1000), 'ms')

print('---- LAST ----')
x[:] = 0
x[-1] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

print('---- NONE ----')
x[:] = 0
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

print('---- ALL ----')
x[:] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

Das Ergebnis auf meiner Maschine sind:

---- FIRST ----
ndarray.nonzero 57.63976670001284 ms
find_first 0.0010841979965334758 ms
find_first_numba 0.0002308919938514009 ms
---- LAST ----
ndarray.nonzero 58.96685277999495 ms
find_first 5.923203580023255 ms
find_first_numba 8.762269750004634 ms
---- NONE ----
ndarray.nonzero 25.13398071998381 ms
find_first 5.924289370013867 ms
find_first_numba 8.810063839919167 ms
---- ALL ----
ndarray.nonzero 55.181210660084616 ms
find_first 0.001246920000994578 ms
find_first_numba 0.00028766007744707167 ms

Die Lösung ist 33% schneller als numba und "numpy-pure".

Die Nachteile:

• funktioniert nicht für numpy akzeptable Typen wie object
• schlägt fehl für negative Null, die gelegentlich in floatoder doubleBerechnungen erscheint

Als langjähriger Matlab-Benutzer habe ich schon seit einiger Zeit nach einer effizienten Lösung für dieses Problem gesucht. Schließlich habe ich , motiviert durch Diskussionen und Vorschläge in diesem Thread , versucht, eine Lösung zu finden, die eine API implementiert , die der hier vorgeschlagenen ähnlich ist und im Moment nur 1D-Arrays unterstützt.

Sie würden es so verwenden

import numpy as np
import utils_find_1st as utf1st
array = np.arange(100000)
item = 1000
ind = utf1st.find_1st(array, item, utf1st.cmp_larger_eq)

Die unterstützten Bedingungsoperatoren sind: cmp_equal, cmp_not_equal, cmp_larger, cmp_smaller, cmp_larger_eq, cmp_smaller_eq. Aus Effizienzgründen ist die Erweiterung in c geschrieben.

Die Quelle, Benchmarks und andere Details finden Sie hier:

https://pypi.python.org/pypi?name=py_find_1st&:action=display

Für die Verwendung in unserem Team (Anaconda unter Linux und MacOS) habe ich ein Anaconda-Installationsprogramm erstellt, das die Installation vereinfacht. Sie können es wie hier beschrieben verwenden

https://anaconda.org/roebel/py_find_1st

Nur ein Hinweis: Wenn Sie eine Sequenz von Suchvorgängen ausführen, kann der Leistungsgewinn durch clevere Aktionen wie das Konvertieren in Zeichenfolgen in der äußeren Schleife verloren gehen, wenn die Suchdimension nicht groß genug ist. Sehen Sie, wie die Leistung des Iterierens von find1, das den oben vorgeschlagenen String-Konvertierungstrick verwendet, und find2, das argmax entlang der inneren Achse verwendet (plus einer Anpassung, um sicherzustellen, dass eine Nichtübereinstimmung als -1 zurückgegeben wird).

import numpy,time
def find1(arr,value):
    return (arr==value).tostring().find('\x01')

def find2(arr,value): #find value over inner most axis, and return array of indices to the match
    b = arr==value
    return b.argmax(axis=-1) - ~(b.any())


for size in [(1,100000000),(10000,10000),(1000000,100),(10000000,10)]:
    print(size)
    values = numpy.random.choice([0,0,0,0,0,0,0,1],size=size)
    v = values>0

    t=time.time()
    numpy.apply_along_axis(find1,-1,v,1)
    print('find1',time.time()-t)

    t=time.time()
    find2(v,1)
    print('find2',time.time()-t)

Ausgänge

(1, 100000000)
('find1', 0.25300002098083496)
('find2', 0.2780001163482666)
(10000, 10000)
('find1', 0.46200013160705566)
('find2', 0.27300000190734863)
(1000000, 100)
('find1', 20.98099994659424)
('find2', 0.3040001392364502)
(10000000, 10)
('find1', 206.7590000629425)
('find2', 0.4830000400543213)

Ein in C geschriebener Fund wäre jedoch zumindest etwas schneller als jeder dieser Ansätze

Wie wäre es damit

import numpy as np
np.amin(np.where(array==item))

Sie können Ihr Array in ein Array umwandeln listund dessen index()Methode verwenden:

i = list(array).index(item)

Soweit mir bekannt ist, handelt es sich um eine C-kompilierte Methode.