Numpy première occurrence d'une valeur supérieure à la valeur existante

Question

J'ai un tableau 1D dans numpy et je veux trouver la position de l'index où une valeur dépasse la valeur dans le tableau numpy.

Par exemple

aa = range(-10,10)

Trouver une position dans aa où, la valeur 5 est dépassé.

Answer 1

C'est un peu plus rapide (et c'est plus joli).

np.argmax(aa>5)

Desde argmax s'arrêtera au premier True ("En cas d'occurrences multiples des valeurs maximales, les indices correspondant à la première occurrence sont retournés.") et n'enregistre pas une autre 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

Answer 2

Étant donné le contenu trié de votre tableau, il existe une méthode encore plus rapide : recherchetriée .

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

Answer 3

J'étais également intéressé par ce sujet et j'ai comparé toutes les réponses proposées avec perfplot . (Avertissement : je suis l'auteur de perfplot).

Si vous savez que le tableau que vous regardez est Déjà classé alors

numpy.searchsorted(a, alpha)

est pour vous. C'est une opération O(log(n)), c'est-à-dire que la vitesse dépend à peine de la taille du tableau. Vous ne pouvez pas faire plus rapide que cela.

Si vous ne savez rien de votre tableau, vous ne vous tromperez pas avec

numpy.argmax(a > alpha)

C'est déjà fait :

Non trié :

Code pour reproduire l'intrigue :

import numpy
import perfplot

alpha = 0.5
numpy.random.seed(0)

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)

perfplot.save(
    "out.png",
    # 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, 23)],
    xlabel="len(array)",
)

Answer 4

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

Answer 5

Les tableaux qui ont un pas constant entre les éléments

En cas de range ou tout autre tableau à croissance linéaire, vous pouvez simplement calculer l'indice par programme, sans avoir besoin d'itérer sur le tableau :

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

On pourrait probablement améliorer un peu cela. Je me suis assuré qu'il fonctionne correctement pour quelques exemples de tableaux et de valeurs, mais cela ne veut pas dire qu'il ne peut pas y avoir d'erreurs, surtout si l'on considère qu'il utilise des flottants...

>>> 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

Étant donné qu'il peut calculer la position sans aucune itération, le temps sera constant ( O(1) ) et peut probablement battre toutes les autres approches mentionnées. Cependant, elle nécessite un pas constant dans le tableau, sinon elle produira des résultats erronés.

Solution générale utilisant le numba

Une approche plus générale consisterait à utiliser une fonction numba :

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

Cela fonctionnera pour n'importe quel tableau mais il faut itérer sur le tableau, donc dans le cas moyen ce sera O(n) :

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

Point de repère

Bien que Nico Schlömer ait déjà fourni quelques points de référence, j'ai pensé qu'il pourrait être utile d'inclure mes nouvelles solutions et de tester différentes "valeurs".

L'installation de test :

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

et les graphiques ont été générés en utilisant :

%matplotlib notebook
b.plot()

l'article est au début

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

La fonction numba est la plus performante, suivie de la fonction calculate et de la fonction searchsorted. Les autres solutions sont beaucoup moins performantes.

l'élément est à la fin

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

Pour les petits tableaux, la fonction numba est incroyablement rapide, mais pour les tableaux plus grands, elle est surpassée par la fonction calculate et la fonction searchsorted.

l'élément est à 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")

C'est plus intéressant. Encore une fois, numba et la fonction calculate fonctionnent très bien, mais cela déclenche en fait le pire cas de searchsorted qui ne fonctionne pas vraiment bien dans ce cas.

Comparaison des fonctions lorsqu'aucune valeur ne satisfait à la condition

Un autre point intéressant est de savoir comment ces fonctions se comportent s'il n'y a pas de valeur dont l'indice doit être renvoyé :

arr = np.ones(100)
value = 2

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

Avec ce résultat :

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, et numba retournent simplement une valeur erronée. Cependant, searchsorted y numba retourne un index qui n'est pas un index valide pour le tableau.

Les fonctions where , min , nonzero y calculate lancer une exception. Cependant, seule l'exception pour calculate dit vraiment quelque chose d'utile.

Cela signifie qu'il faut en fait envelopper ces appels dans une fonction d'enveloppe appropriée qui détecte les exceptions ou les valeurs de retour invalides et les traite de manière appropriée, du moins si vous n'êtes pas sûr que la valeur puisse être dans le tableau.

---

Note : Le calcul et searchsorted Les options ne fonctionnent que dans des conditions particulières. La fonction "calculate" nécessite un pas constant et la fonction "searchsorted" exige que le tableau soit trié. Elles pourraient donc être utiles dans les bonnes circonstances, mais ne le sont pas. général des solutions à ce problème. Si vous avez affaire à trié Pour les listes Python, vous pouvez jeter un coup d'œil à l'outil bissecter au lieu d'utiliser le module Numpys searchsorted.