Ich habe ein 1D-Array in numpy und möchte die Position des Index ermitteln, an der ein Wert den Wert in numpy-Array überschreitet.

Z.B

aa = range(-10,10)

Suchen Sie die Position aa, an der der Wert 5überschritten wird.

Dies ist etwas schneller (und sieht besser aus)

np.argmax(aa>5)

Da argmaxwird beim ersten TrueAuftreten gestoppt ("Bei mehrfachem Auftreten der Maximalwerte werden die dem ersten Auftreten entsprechenden Indizes zurückgegeben.") Und speichert keine weitere Liste.

In [2]: N = 10000

In [3]: aa = np.arange(-N,N)

In [4]: timeit np.argmax(aa>N/2)
100000 loops, best of 3: 52.3 us per loop

In [5]: timeit np.where(aa>N/2)[0][0]
10000 loops, best of 3: 141 us per loop

In [6]: timeit np.nonzero(aa>N/2)[0][0]
10000 loops, best of 3: 142 us per loop

Angesichts des sortierten Inhalts Ihres Arrays gibt es eine noch schnellere Methode: durchsucht .

import time
N = 10000
aa = np.arange(-N,N)
%timeit np.searchsorted(aa, N/2)+1
%timeit np.argmax(aa>N/2)
%timeit np.where(aa>N/2)[0][0]
%timeit np.nonzero(aa>N/2)[0][0]

# Output
100000 loops, best of 3: 5.97 µs per loop
10000 loops, best of 3: 46.3 µs per loop
10000 loops, best of 3: 154 µs per loop
10000 loops, best of 3: 154 µs per loop

Das hat mich auch interessiert und ich habe alle vorgeschlagenen Antworten mit perfplot verglichen . (Haftungsausschluss: Ich bin der Autor von perfplot.)

Wenn Sie wissen, dass das Array, das Sie durchsuchen, bereits sortiert ist , dann

numpy.searchsorted(a, alpha)

ist für Sie. Es handelt sich um eine Operation mit konstanter Zeit, dh die Geschwindigkeit hängt nicht von der Größe des Arrays ab. Schneller geht es nicht.

Wenn Sie nichts über Ihr Array wissen, können Sie nichts falsch machen

numpy.argmax(a > alpha)

Bereits sortiert:

Unsortiert:

Code zur Reproduktion der Handlung:

import numpy
import perfplot


alpha = 0.5

def argmax(data):
    return numpy.argmax(data > alpha)

def where(data):
    return numpy.where(data > alpha)[0][0]

def nonzero(data):
    return numpy.nonzero(data > alpha)[0][0]

def searchsorted(data):
    return numpy.searchsorted(data, alpha)

out = perfplot.show(
    # setup=numpy.random.rand,
    setup=lambda n: numpy.sort(numpy.random.rand(n)),
    kernels=[
        argmax, where,
        nonzero,
        searchsorted
        ],
    n_range=[2**k for k in range(2, 20)],
    logx=True,
    logy=True,
    xlabel='len(array)'
    )

In [34]: a=np.arange(-10,10)

In [35]: a
Out[35]:
array([-10,  -9,  -8,  -7,  -6,  -5,  -4,  -3,  -2,  -1,   0,   1,   2,
         3,   4,   5,   6,   7,   8,   9])

In [36]: np.where(a>5)
Out[36]: (array([16, 17, 18, 19]),)

In [37]: np.where(a>5)[0][0]
Out[37]: 16

Arrays, die einen konstanten Schritt zwischen Elementen haben

Im Falle eines rangeoder eines anderen linear ansteigenden Arrays können Sie den Index einfach programmgesteuert berechnen, ohne dass Sie das Array tatsächlich durchlaufen müssen:

def first_index_calculate_range_like(val, arr):
    if len(arr) == 0:
        raise ValueError('no value greater than {}'.format(val))
    elif len(arr) == 1:
        if arr[0] > val:
            return 0
        else:
            raise ValueError('no value greater than {}'.format(val))

    first_value = arr[0]
    step = arr[1] - first_value
    # For linearly decreasing arrays or constant arrays we only need to check
    # the first element, because if that does not satisfy the condition
    # no other element will.
    if step <= 0:
        if first_value > val:
            return 0
        else:
            raise ValueError('no value greater than {}'.format(val))

    calculated_position = (val - first_value) / step

    if calculated_position < 0:
        return 0
    elif calculated_position > len(arr) - 1:
        raise ValueError('no value greater than {}'.format(val))

    return int(calculated_position) + 1

Das könnte man wohl etwas verbessern. Ich habe sichergestellt, dass es für einige Beispiel-Arrays und -Werte korrekt funktioniert, aber das bedeutet nicht, dass dort keine Fehler auftreten können, insbesondere wenn man bedenkt, dass Floats verwendet werden ...

>>> import numpy as np
>>> first_index_calculate_range_like(5, np.arange(-10, 10))
16
>>> np.arange(-10, 10)[16]  # double check
6

>>> first_index_calculate_range_like(4.8, np.arange(-10, 10))
15

Da es die Position ohne Iteration berechnen kann, ist es eine konstante Zeit ( O(1)) und kann wahrscheinlich alle anderen genannten Ansätze übertreffen. Es erfordert jedoch einen konstanten Schritt im Array, da sonst falsche Ergebnisse erzielt werden.

Allgemeine Lösung mit numba

Ein allgemeinerer Ansatz wäre die Verwendung einer Numba-Funktion:

@nb.njit
def first_index_numba(val, arr):
    for idx in range(len(arr)):
        if arr[idx] > val:
            return idx
    return -1

Das funktioniert für jedes Array, muss jedoch über das Array iteriert werden. Im Durchschnitt ist dies also O(n):

>>> first_index_numba(4.8, np.arange(-10, 10))
15
>>> first_index_numba(5, np.arange(-10, 10))
16

Benchmark

Obwohl Nico Schlömer bereits einige Benchmarks bereitgestellt hat, hielt ich es für nützlich, meine neuen Lösungen einzubeziehen und auf unterschiedliche "Werte" zu testen.

Der Testaufbau:

import numpy as np
import math
import numba as nb

def first_index_using_argmax(val, arr):
    return np.argmax(arr > val)

def first_index_using_where(val, arr):
    return np.where(arr > val)[0][0]

def first_index_using_nonzero(val, arr):
    return np.nonzero(arr > val)[0][0]

def first_index_using_searchsorted(val, arr):
    return np.searchsorted(arr, val) + 1

def first_index_using_min(val, arr):
    return np.min(np.where(arr > val))

def first_index_calculate_range_like(val, arr):
    if len(arr) == 0:
        raise ValueError('empty array')
    elif len(arr) == 1:
        if arr[0] > val:
            return 0
        else:
            raise ValueError('no value greater than {}'.format(val))

    first_value = arr[0]
    step = arr[1] - first_value
    if step <= 0:
        if first_value > val:
            return 0
        else:
            raise ValueError('no value greater than {}'.format(val))

    calculated_position = (val - first_value) / step

    if calculated_position < 0:
        return 0
    elif calculated_position > len(arr) - 1:
        raise ValueError('no value greater than {}'.format(val))

    return int(calculated_position) + 1

@nb.njit
def first_index_numba(val, arr):
    for idx in range(len(arr)):
        if arr[idx] > val:
            return idx
    return -1

funcs = [
    first_index_using_argmax, 
    first_index_using_min, 
    first_index_using_nonzero,
    first_index_calculate_range_like, 
    first_index_numba, 
    first_index_using_searchsorted, 
    first_index_using_where
]

from simple_benchmark import benchmark, MultiArgument

und die Diagramme wurden erstellt mit:

%matplotlib notebook
b.plot()

Artikel ist am Anfang

b = benchmark(
    funcs,
    {2**i: MultiArgument([0, np.arange(2**i)]) for i in range(2, 20)},
    argument_name="array size")

Die numba-Funktion funktioniert am besten, gefolgt von der Berechnungsfunktion und der suchsortierten Funktion. Die anderen Lösungen schneiden viel schlechter ab.

Artikel ist am Ende

b = benchmark(
    funcs,
    {2**i: MultiArgument([2**i-2, np.arange(2**i)]) for i in range(2, 20)},
    argument_name="array size")

Bei kleinen Arrays arbeitet die numba-Funktion erstaunlich schnell, bei größeren Arrays jedoch besser als die Berechnungsfunktion und die suchsortierte Funktion.

Artikel ist bei sqrt (len)

b = benchmark(
    funcs,
    {2**i: MultiArgument([np.sqrt(2**i), np.arange(2**i)]) for i in range(2, 20)},
    argument_name="array size")

Das ist interessanter. Wiederum funktionieren numba und die Berechnungsfunktion hervorragend, dies löst jedoch tatsächlich den schlimmsten Fall einer Suchsortierung aus, der in diesem Fall wirklich nicht gut funktioniert.

Vergleich der Funktionen, wenn kein Wert die Bedingung erfüllt

Ein weiterer interessanter Punkt ist, wie sich diese Funktionen verhalten, wenn es keinen Wert gibt, dessen Index zurückgegeben werden soll:

arr = np.ones(100)
value = 2

for func in funcs:
    print(func.__name__)
    try:
        print('-->', func(value, arr))
    except Exception as e:
        print('-->', e)

Mit diesem Ergebnis:

first_index_using_argmax
--> 0
first_index_using_min
--> zero-size array to reduction operation minimum which has no identity
first_index_using_nonzero
--> index 0 is out of bounds for axis 0 with size 0
first_index_calculate_range_like
--> no value greater than 2
first_index_numba
--> -1
first_index_using_searchsorted
--> 101
first_index_using_where
--> index 0 is out of bounds for axis 0 with size 0

Searchsorted, argmax und numba geben einfach einen falschen Wert zurück. Jedoch searchsortedund numbaRück einen Index, der kein gültiger Index für das Array ist.

Die Funktionen where, min, nonzeround calculateeine Ausnahme werfen. Allerdings calculatesagt nur die Ausnahme für eigentlich etwas hilfreiches.

Das bedeutet, dass diese Aufrufe tatsächlich in eine geeignete Wrapper-Funktion eingeschlossen werden müssen, die Ausnahmen oder ungültige Rückgabewerte abfängt und entsprechend behandelt, zumindest wenn Sie nicht sicher sind, ob der Wert im Array enthalten sein könnte.

Hinweis: Die Berechnungs- und searchsortedOptionsoptionen funktionieren nur unter besonderen Bedingungen. Die "Berechnen" -Funktion erfordert einen konstanten Schritt und die Suchsortierung erfordert das Sortieren des Arrays. Diese könnten unter den richtigen Umständen nützlich sein, sind jedoch keine allgemeinen Lösungen für dieses Problem. Wenn Sie es mit sortierten Python-Listen zu tun haben, sollten Sie sich das Bisect- Modul ansehen, anstatt Numpys searchsorted zu verwenden.

Ich würde gerne vorschlagen

np.min(np.append(np.where(aa>5)[0],np.inf))

Dies gibt den kleinsten Index zurück, in dem die Bedingung erfüllt ist, während unendlich zurückgegeben wird, wenn die Bedingung nie erfüllt ist (und whereein leeres Array zurückgibt).

Ich würde mit gehen

i = np.min(np.where(V >= x))

Dabei Vist der Vektor (1d-Array) xder Wert und ider resultierende Index.