Numpy: trouver les premier indice de la valeur rapide

Bien qu'il est trop tard pour vous, mais pour une référence future:
À l'aide de numba (Un) est la façon la plus simple jusqu'à ce que numpy la met en œuvre. Si vous utilisez anaconda python de distribution, il devrait déjà être installé.
Le code sera compilé, donc il sera rapide.

@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

et puis:

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

Vous pouvez convertir une valeur de type boolean tableau à une chaîne Python à l'aide de array.tostring(), puis en utilisant la méthode find ():

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

Ceci implique la copie de données, bien que, depuis le Python cordes doivent être immuable. Un avantage est que vous pouvez également effectuer une recherche, par exemple, un front montant par trouver \x00\x01

Je pense que vous avez frappé un problème où une méthode différente et certains a priori la connaissance de la matrice serait vraiment aider. Le genre de chose où vous avez un X probabilité de trouver votre réponse dans la première Y pour cent des données. Le fractionnement le problème avec l'espoir d'obtenir de la chance alors, faire en python avec une liste imbriquée de compréhension ou de quelque chose.

Écrire une fonction C pour ce faire, la force brute n'est pas trop dur à l'aide de ctypes soit.

Le code C j'ai bidouillé (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);
}

et le 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))

et je reçois 92.

Envelopper le python dans une fonction appropriée et là vous allez.

La version C est beaucoup (~20x plus rapide de cette graine (attention je ne suis pas bon avec 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

Autant que je sache seulement np.tout et np.tous les booléens les tableaux sont court-circuitées.

Dans votre cas, numpy doit passer par l'ensemble de la matrice, une fois pour créer la condition booléenne et une deuxième fois pour trouver les indices.

Ma recommandation dans ce cas serait d'utiliser cython. Je pense qu'il devrait être facile à régler un exemple pour ce cas, surtout si vous n'avez pas besoin de beaucoup de flexibilité pour les différents dtypes et de formes.

Si votre liste est triés, vous pouvez obtenir très rapide de recherche de l'index avec le "coupent" paquet.
Il est O(log(n)) au lieu de O(n).

bisect.bisect(a, x)

trouve x dans le tableau a, certainement plus rapide dans le triées cas que tout C-routine passe en revue tous les éléments premiers (assez longtemps listes).

Il est bon de savoir parfois.

Juste une note que si vous faites une séquence de recherches, le gain de performances de faire quelque chose d'intelligent comme la conversion de chaînes de caractères, peut-être perdu dans la boucle externe si la recherche de la dimension n'est pas assez grand. Voir comment la performance de l'itération find1 qui utilise la chaîne de conversion astuce proposée ci-dessus et find2 qui utilise argmax le long de l'intérieur de l'axe (en plus d'un ajustement pour assurer un non-match retourne -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)

sorties

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

Cela dit, écrit en C serait au moins un peu plus vite que l'autre de ces approches

Ce problème peut être résolu dans le plus pur numpy par le traitement de la matrice en blocs:

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

Le tableau est transformé en morceau de la taille step. Le step plus l'étape est, le plus rapide est de traitement de remise à zéro-array (pire des cas). La plus petite, il est, au traitement plus rapide de tableau avec des non-zéro au début. Le truc est de commencer avec une petite step et de l'augmenter de façon exponentielle. En outre, il n'est pas nécessaire d'incrémenter au-dessus d'un certain seuil en raison des avantages limités.

J'ai comparé la solution avec de la pure ndarary.différent de zéro et numba solution contre 10 millions de tableau de float.

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

Et les résultats sur ma machine:

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

Pur ndarray.nonzero est certain assouplissement. Le numba solution est environ 5 fois plus rapide pour le meilleur des cas. Il est environ 3 fois plus rapide dans le pire des cas.