python - log - Numpy: encuentre el primer índice de valor rápido

numpy power

Question

¿Cómo puedo encontrar el índice de la primera aparición de un número en una matriz Numpy? La velocidad es importante para mí. No estoy interesado en las siguientes respuestas porque escanean toda la matriz y no se detienen cuando encuentran la primera aparición:

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

Nota 1: ninguna de las respuestas de esa pregunta parece relevante ¿Hay una función Numpy para devolver el primer índice de algo en una matriz?

Nota 2: el uso de un método compilado en C es preferible a un ciclo de Python.

Answer 1

@tal ya presentó una función numba para encontrar el primer índice, pero eso solo funciona para matrices 1D. Con np.ndenumerate también puede encontrar el primer índice en una matriz arbitarly dimensional:

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

Muestra de caso:

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

Los tiempos muestran que es similar en rendimiento a la solución de tals :

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

Answer 2

Aunque es demasiado tarde para ti, pero para futuras referencias: Usar numba ( 1 ) es la forma más fácil hasta que numpy lo implemente. Si usa la distribución anaconda python, ya debería estar instalado. El código será compilado así que será rápido.

@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

y entonces:

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

Answer 3

Creo que has encontrado un problema en el que un método diferente y un conocimiento a priori de la matriz realmente ayudaría. El tipo de cosa donde tienes una X probabilidad de encontrar tu respuesta en el primer Y por ciento de los datos. La división del problema con la esperanza de tener suerte y luego hacer esto en Python con una lista anidada de comprensión o algo así.

Escribir una función C para hacer esta fuerza bruta no es demasiado difícil usando ctypes tampoco.

El código C que pirateé juntos (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);
}

y el pitón:

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

y obtengo 92

Envuelva la pitón en una función adecuada y listo.

La versión C es mucho (~ 20x) más rápida para esta semilla (advirtiendo que no soy bueno con el tiempo)

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

Answer 4

En el caso de arreglos ordenados, np.searchsorted funciona.

Answer 5

Hay una solicitud de función para esto programada para Numpy 2.0.0: https://github.com/numpy/numpy/issues/2269

Answer 6

He hecho un punto de referencia para varios métodos:

• argwhere
• nonzero como en la pregunta
• .tostring() como en la respuesta de @Rob Reilink
• ciclo python
• Fortran loop

El código Python y Fortran están disponibles. Me salté los poco prometedores como convertir a una lista.

Los resultados en la escala de registro. El eje X es la posición de la aguja (lleva más tiempo encontrarla si está más abajo en la matriz); el último valor es una aguja que no está en la matriz. El eje Y es el momento de encontrarlo.

La matriz tenía 1 millón de elementos y las pruebas se realizaron 100 veces. Los resultados aún fluctúan un poco, pero la tendencia cualitativa es clara: Python y f2py se dan por vencidos en el primer elemento, por lo que se escalan de manera diferente. Python se vuelve demasiado lento si la aguja no está en el primer 1%, mientras que f2py es rápido (pero debe compilarlo).

En resumen, f2py es la solución más rápida , especialmente si la aguja aparece bastante temprano.

No está construido en lo que es molesto, pero en realidad es solo 2 minutos de trabajo. Agregue Fortran a un archivo llamado 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

Si está buscando algo que no sea integer , simplemente cambie el tipo. Luego compila usando:

f2py -c -m search search.f90

después de lo cual puedes hacer (desde Python):

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

Answer 7

Necesitaba esto para mi trabajo, así que me enseñé la interfaz C de Python y Numpy y escribí la mía. http://pastebin.com/GtcXuLyd Es solo para matrices de 1-D, pero funciona para la mayoría de los tipos de datos (int, float o strings) y las pruebas han demostrado que es de nuevo aproximadamente 20 veces más rápido que el enfoque esperado en Python puro. numpy

Answer 8

Por lo que yo sé, solo np.any np.all en matrices booleanas están en cortocircuito.

En su caso, numpy tiene que pasar por toda la matriz dos veces, una para crear la condición booleana y una segunda vez para encontrar los índices.

Mi recomendación en este caso sería usar cython. Creo que debería ser fácil ajustar un ejemplo para este caso, especialmente si no necesita mucha flexibilidad para diferentes tipos y formas.

Answer 9

Puede convertir una matriz booleana en una cadena de Python usando array.tostring() y luego usando el método find ():

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

Sin embargo, esto implica copiar los datos, ya que las cadenas de Python deben ser inmutables. Una ventaja es que también puedes buscar, por ejemplo, un flanco ascendente encontrando /x00/x01

Answer 10

Puede encubrir su matriz en una list y usar su método index() :

i = list(array).index(item)

Hasta donde yo sé, este es un método compilado en C.

Answer 11

Qué tal esto

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

Answer 12

Si su lista está ordenada , puede lograr una búsqueda muy rápida del índice con el paquete ''bisect''. Es O (log (n)) en lugar de O (n).

bisect.bisect(a, x)

encuentra x en la matriz a, definitivamente más rápido en el caso ordenado que cualquier rutina C que pase por todos los primeros elementos (para listas lo suficientemente largas).

Es bueno saberlo a veces.

Answer 13

Solo una nota que si está haciendo una secuencia de búsquedas, el rendimiento obtenido al hacer algo inteligente como convertir a cadena, podría perderse en el bucle externo si la dimensión de búsqueda no es lo suficientemente grande. Vea cómo el rendimiento de iterar find1 que utiliza el truco de conversión de cadena propuesto anteriormente y find2 que usa argmax a lo largo del eje interno (más un ajuste para asegurar que un no coincidente regrese como -1)

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)

salidas

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

Dicho esto, un hallazgo escrito en C sería al menos un poco más rápido que cualquiera de estos enfoques