Una manera rápida de encontrar las más importantes N elementos de un array numpy

Question

sé que puedo hacerlo como los siguientes:

import numpy as np 
N=10 
a=np.arange(1,100,1) 
np.argsort()[-N:] 

Sin embargo, es muy lento, ya que hizo una especie completa.

Me pregunto si numpy proporciona algunos métodos para hacerlo rápido.

Answer 1

El módulo bottleneck tiene un método rápido de ordenación parcial que funciona directamente con las matrices Numpy: bottleneck.partition().

Tenga en cuenta que bottleneck.partition() devuelve los valores reales ordenados, si desea los índices de los valores ordenados (lo que numpy.argsort() devuelve) debe usar bottleneck.argpartition().

he Benchmarked:

• z = -bottleneck.partition(-a, 10)[:10]
• z = a.argsort()[-10:]
• z = heapq.nlargest(10, a)

donde a es una matriz 1000000-elemento aleatorio.

Los tiempos fueron los siguientes:

• bottleneck.partition(): 25,6 ms por bucle
• np.argsort(): 198 ms por bucle
• heapq.nlargest(): 358 ms por bucle

Answer 2

Quizás heapq.nlargest

import numpy as np 
import heapq 

x = np.array([1,-5,4,6,-3,3]) 

z = heapq.nlargest(3,x) 

Resultado:

>>> z 
[6, 4, 3] 

Si usted quiere encontrar los índices de los elementos más grandes que utilizan nbottleneck podría utilizar bottleneck.argpartsort

>>> x = np.array([1,-5,4,6,-3,3]) 
>>> z = bottleneck.argpartsort(-x, 3)[:3] 
>>> z 
array([3, 2, 5] 

Answer 3

Si el almacenamiento de la matriz como una lista de números no es problemático, puede utilizar

import heapq 
heapq.nlargest(N, a) 

para obtener los N miembros más grandes.

Answer 4

Cada signo negativo en la solución de cuello de botella propuesta

-bottleneck.partsort(-a, 10)[:10] 

realiza una copia de los datos.Podemos eliminar las copias haciendo

bottleneck.partsort(a, a.size-10)[-10:] 

también la solución propuesta numpy

a.argsort()[-10:] 

devoluciones no índices de valores. La solución es utilizar los índices para encontrar los valores:

a[a.argsort()[-10:]] 

La velocidad relativa de las dos soluciones de cuello de botella depende de la ordenación de los elementos de la matriz inicial, porque los dos enfoques dividir los datos en diferentes puntos.

En otras palabras, el tiempo con una matriz aleatoria particular puede hacer que cualquiera de los métodos se vea más rápido.

Promediando la sincronización a través de 100 matrices aleatorios, cada uno con 1.000.000 de elementos, da

-bn.partsort(-a, 10)[:10]: 1.76 ms per loop 
bn.partsort(a, a.size-10)[-10:]: 0.92 ms per loop 
a[a.argsort()[-10:]]: 15.34 ms per loop 

donde el código de sincronización es como sigue:

import time 
import numpy as np 
import bottleneck as bn 

def bottleneck_1(a): 
    return -bn.partsort(-a, 10)[:10] 

def bottleneck_2(a): 
    return bn.partsort(a, a.size-10)[-10:] 

def numpy(a): 
    return a[a.argsort()[-10:]] 

def do_nothing(a): 
    return a 

def benchmark(func, size=1000000, ntimes=100): 
    t1 = time.time() 
    for n in range(ntimes): 
     a = np.random.rand(size) 
     func(a) 
    t2 = time.time() 
    ms_per_loop = 1000000 * (t2 - t1)/size 
    return ms_per_loop 

t1 = benchmark(bottleneck_1) 
t2 = benchmark(bottleneck_2) 
t3 = benchmark(numpy) 
t4 = benchmark(do_nothing) 

print "-bn.partsort(-a, 10)[:10]: %0.2f ms per loop" % (t1 - t4) 
print "bn.partsort(a, a.size-10)[-10:]: %0.2f ms per loop" % (t2 - t4) 
print "a[a.argsort()[-10:]]: %0.2f ms per loop" % (t3 - t4) 

Answer 5

numpy 1.8 implementa partition y argpartition que realizan especie parcial (en O (n) tiempo en oposición al tipo completo que es O (n) * log (n)).

import numpy as np 

test = np.array([9,1,3,4,8,7,2,5,6,0]) 

temp = np.argpartition(-test, 4) 
result_args = temp[:4] 

temp = np.partition(-test, 4) 
result = -temp[:4] 

Resultado:

Tiempo:

In [16]: a = np.arange(10000) 

In [17]: np.random.shuffle(a) 

In [18]: %timeit np.argsort(a) 
1000 loops, best of 3: 1.02 ms per loop 

In [19]: %timeit np.argpartition(a, 100) 
10000 loops, best of 3: 139 us per loop 

In [20]: %timeit np.argpartition(a, 1000) 
10000 loops, best of 3: 141 us per loop 

Answer 6

También puede utilizar la función percentil de numpy. En mi caso fue ligeramente más rápido que bottleneck.partsort():

import timeit 
import bottleneck as bn 

N,M,K = 10,1000000,100 

start = timeit.default_timer() 
for k in range(K): 
    a=np.random.uniform(size=M) 
    tmp=-bn.partsort(-a, N)[:N] 
stop = timeit.default_timer() 
print (stop - start)/K 

start = timeit.default_timer() 
perc = (np.arange(M-N,M)+1.0)/M*100 
for k in range(K): 
    a=np.random.uniform(size=M) 
    tmp=np.percentile(a,perc) 
stop = timeit.default_timer() 
print (stop - start)/K 

Tiempo medio por bucle:

• bottleneck.partsort(): 59 ms
• np.percentile(): 54 MS

Answer 7

tuve este problema y, puesto que esta cuestión es de 5 años de edad, tuve que volver a hacer todos los puntos de referencia y cambiar la sintaxis de cuello de botella (no hay partsort más, es partition ahora).

Usé los mismos argumentos que kwgoodman, excepto el número de elementos recuperados, que aumenté a 50 (para ajustarse mejor a mi situación particular).

me dieron estos resultados:

bottleneck 1: 01.12 ms per loop 
bottleneck 2: 00.95 ms per loop 
pandas  : 01.65 ms per loop 
heapq  : 08.61 ms per loop 
numpy  : 12.37 ms per loop 
numpy 2  : 00.95 ms per loop 

Así, bottleneck_2 y numpy_2 (solución de ADAS) fueron atados. Pero, usando np.percentile (numpy_2) tiene esos elementos topN ya ordenados, que no es el caso para las otras soluciones. Por otro lado, si también está interesado en los índices de esos elementos, el percentil no es útil.

Añadí pandas también, que usa cuello de botella debajo, si está disponible (http://pandas.pydata.org/pandas-docs/stable/install.html#recommended-dependencies).Si ya tiene una serie de pandas o un DataFrame para empezar, está en buenas manos, simplemente use nlargest y listo.

El código utilizado para el punto de referencia es el siguiente (Python 3, por favor):

import time 
import numpy as np 
import bottleneck as bn 
import pandas as pd 
import heapq 

def bottleneck_1(a, n): 
    return -bn.partition(-a, n)[:n] 

def bottleneck_2(a, n): 
    return bn.partition(a, a.size-n)[-n:] 

def numpy(a, n): 
    return a[a.argsort()[-n:]] 

def numpy_2(a, n): 
    M = a.shape[0] 
    perc = (np.arange(M-n,M)+1.0)/M*100 
    return np.percentile(a,perc) 

def pandas(a, n): 
    return pd.Series(a).nlargest(n) 

def hpq(a, n): 
    return heapq.nlargest(n, a) 

def do_nothing(a, n): 
    return a[:n] 

def benchmark(func, size=1000000, ntimes=100, topn=50): 
    t1 = time.time() 
    for n in range(ntimes): 
     a = np.random.rand(size) 
     func(a, topn) 
    t2 = time.time() 
    ms_per_loop = 1000000 * (t2 - t1)/size 
    return ms_per_loop 

t1 = benchmark(bottleneck_1) 
t2 = benchmark(bottleneck_2) 
t3 = benchmark(pandas) 
t4 = benchmark(hpq) 
t5 = benchmark(numpy) 
t6 = benchmark(numpy_2) 
t0 = benchmark(do_nothing) 

print("bottleneck 1: {:05.2f} ms per loop".format(t1 - t0)) 
print("bottleneck 2: {:05.2f} ms per loop".format(t2 - t0)) 
print("pandas  : {:05.2f} ms per loop".format(t3 - t0)) 
print("heapq  : {:05.2f} ms per loop".format(t4 - t0)) 
print("numpy  : {:05.2f} ms per loop".format(t5 - t0)) 
print("numpy 2  : {:05.2f} ms per loop".format(t6 - t0))