Eliminación rápida de duplicados en numpy y python

Question

¿Hay alguna manera rápida de obtener elementos únicos en numpy? Tengo un código similar a esto (la última línea)

tab = numpy.arange(100000000) 

indices1 = numpy.random.permutation(10000) 
indices2 = indices1.copy() 
indices3 = indices1.copy() 
indices4 = indices1.copy() 

result = numpy.unique(numpy.array([tab[indices1], tab[indices2], tab[indices3], tab[indices4]])) 

Esto es sólo un ejemplo y en mi situación indices1, indices2,...,indices4 contiene un conjunto diferente de índices y tienen diferentes tamaños. La última línea se ejecuta muchas veces y me di cuenta de que en realidad es el cuello de botella en mi código ({numpy.core.multiarray.arange} precesivo). Además, el orden no es importante y el elemento en la matriz de índices es del tipo int32. Estaba pensando en usar hashtable con valor de elemento como clave y lo intenté:

seq = itertools.chain(tab[indices1].flatten(), tab[indices2].flatten(), tab[indices3].flatten(), tab[indices4].flatten()) 
myset = {} 
map(myset.__setitem__, seq, []) 
result = numpy.array(myset.keys()) 

pero era aún peor.

¿Hay alguna manera de acelerar esto? Supongo que la penalización de rendimiento proviene de una "indexación elegante" que copia la matriz, pero necesito el elemento resultante solo para leer (no modifico nada).

Answer 1

Lo siento, no entiendo por completo su pregunta, pero Haré todo lo posible para ayudar.

Fist {numpy.core.multiarray.arange} numpy.arange no es una indexación elegante, desafortunadamente la indexación sofisticada no se muestra como una línea separada en el generador de perfiles. Si llama a np.arange en el bucle, debería ver si puede moverlo fuera.

In [27]: prun tab[tab] 
    2 function calls in 1.551 CPU seconds 

Ordered by: internal time 

ncalls tottime percall cumtime percall filename:lineno(function) 
    1 1.551 1.551 1.551 1.551 <string>:1(<module>) 
    1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 

In [28]: prun numpy.arange(10000000) 
    3 function calls in 0.051 CPU seconds 

Ordered by: internal time 

ncalls tottime percall cumtime percall filename:lineno(function) 
    1 0.047 0.047 0.047 0.047 {numpy.core.multiarray.arange} 
    1 0.003 0.003 0.051 0.051 <string>:1(<module>) 
    1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 

Segunda Asumo que no es tabnp.arange(a, b) en su código, porque si es que tab[index] == index + a, pero supongo que era sólo por su ejemplo.

En tercer lugar, np.concatenate es aproximadamente 10 veces más rápido que np.array

In [47]: timeit numpy.array([tab[indices1], tab[indices2], tab[indices3], tab[indices4]]) 
100 loops, best of 3: 5.11 ms per loop 

In [48]: timeit numpy.concatenate([tab[indices1], tab[indices2], tab[indices3],  tab[indices4]]) 
1000 loops, best of 3: 544 us per loop 

(También da np.concatenate un 4 * n,) array (y np.array da una (4, n) array, donde n es la longitud si los índices [1-4]. El último solo funcionará si los índices1-4 tienen la misma longitud.)

Y por último, también podría ahorrar aún más tiempo si puede hacer el siguiente:

indices = np.unique(np.concatenate((indices1, indices2, indices3, indices4))) 
result = tab[indices] 

Hacerlo i n este orden es más rápido porque reduce la cantidad de índices que necesita buscar en la pestaña, pero solo funcionará si sabe que los elementos de la pestaña son únicos (de lo contrario, podría obtener repeticiones en el resultado incluso si los índices son únicos)

Espero que ayude

Answer 2

[Lo que sigue es en realidad parcialmente incorrecta (ver el PS):]

La siguiente forma de obtener los elementos únicos en todas las sub-series es muy rápido:

seq = itertools.chain(tab[indices1].flat, tab[indices2].flat, tab[indices3].flat, tab[indices4].flat) 
result = set(seq) 

Tenga en cuenta que flat (que devuelve un iterador) se usa en lugar de flatten() (que devuelve una matriz completa), y se puede llamar directamente a set() (en lugar de usar map() y un diccionario, como en su segundo método).

Estos son los resultados de temporización (obtenido en la cáscara IPython):

>>> %timeit result = numpy.unique(numpy.array([tab[indices1], tab[indices2], tab[indices3], tab[indices4]])) 
100 loops, best of 3: 8.04 ms per loop 
>>> seq = itertools.chain(tab[indices1].flat, tab[indices2].flat, tab[indices3].flat, tab[indices4].flat) 
>>> %timeit set(seq) 
1000000 loops, best of 3: 223 ns per loop 

El conjunto método/apartamento es por tanto 40 veces más rápido en este ejemplo.

PS: El tiempo de set(seq) no es en realidad representativo. De hecho, el primer ciclo de temporización vacía el iterador seq y las posteriores evaluaciones set() devuelven un conjunto vacío. La prueba de tiempo correcta es la siguiente

>>> %timeit set(itertools.chain(tab[indices1].flat, tab[indices2].flat, tab[indices3].flat, tab[indices4].flat)) 
100 loops, best of 3: 9.12 ms per loop 

que muestra que el método set/flat no es más rápido.

PPS: aquí hay una exploración (infructuosa) de la sugerencia de mtrw; la búsqueda de los índices únicos de antemano podría ser una buena idea, pero no puedo encontrar la manera de ponerla en práctica, que es más rápido que el enfoque anterior:

>>> %timeit set(indices1).union(indices2).union(indices3).union(indices4) 
100 loops, best of 3: 11.9 ms per loop 
>>> %timeit set(itertools.chain(indices1.flat, indices2.flat, indices3.flat, indices4.flat)) 
100 loops, best of 3: 10.8 ms per loop 

Por lo tanto, encontrar el conjunto de todos los índices distintos es en sí bastante lento .

PPP: numpy.unique(<concatenated array of indices>) es realmente 2-3 veces más rápido que set(<concatenated array of indices>). Esto es clave para la aceleración obtenida en la respuesta de Bago (unique(concatenate((…)))). La razón probablemente sea que dejar que NumPy maneje sus matrices por sí mismo es generalmente más rápido que interconectar Python puro (set) con matrices NumPy.

Conclusión: esta respuesta, por tanto, sólo los documentos intentos fallidos que no deben seguirse totalmente, así como una observación posiblemente útil sobre la sincronización de código con iteradores ...