python - numpy min

numpy: función para max() y min() simultáneos

Question

numpy.amax() encontrará el valor máximo en una matriz, y numpy.amin() hará lo mismo para el valor mínimo. Si quiero encontrar tanto max como min, tengo que llamar a ambas funciones, lo que requiere pasar dos veces sobre la matriz (muy grande), lo que parece lento.

¿Hay una función en la API numpy que encuentre tanto max como min con solo una pasada a través de los datos?

Answer 1

¿Hay una función en la API numpy que encuentre tanto max como min con solo una pasada a través de los datos?

No. En el momento de escribir esto, no hay tal función. (Y sí, si hubiera tal función, su rendimiento sería significativamente mejor que llamar numpy.amin() y numpy.amax() sucesivamente en una matriz grande).

Answer 2

A primera vista, numpy.histogram parece hacer el truco:

count, (amin, amax) = numpy.histogram(a, bins=1)

... pero si nos fijamos en la source de esa función, simplemente llama a.min() y a.max() independiente, y por lo tanto no puede evitar las preocupaciones de rendimiento abordadas en esta pregunta. :-(

Del mismo modo, scipy.ndimage.measurements.extrema parece una posibilidad, pero también llama simplemente a.min() y a.max() independiente.

Answer 3

En general, puede reducir la cantidad de comparaciones para un algoritmo minmax procesando dos elementos a la vez y solo comparando el más pequeño con el mínimo temporal y el más grande con el máximo temporal. En promedio, solo se necesitan 3/4 de las comparaciones que un enfoque ingenuo.

Esto podría implementarse en c o fortran (o en cualquier otro lenguaje de bajo nivel) y debería ser casi insuperable en términos de rendimiento. Estoy usando numba para ilustrar el principio y obtener una implementación muy rápida e independiente de los tipos:

import numba as nb
import numpy as np
@nb.njit
def minmax(array):
# Ravel the array and return early if it''s empty
array = array.ravel()
length = array.size
if not length:
return
# We want to process two elements at once so we need
# an even sized array, but we preprocess the first and
# start with the second element, so we want it "odd"
odd = length % 2
if not odd:
length -= 1
# Initialize min and max with the first item
minimum = maximum = array[0]
i = 1
while i < length:
# Get the next two items and swap them if necessary
x = array[i]
y = array[i+1]
if x > y:
x, y = y, x
# Compare the min with the smaller one and the max
# with the bigger one
minimum = min(x, minimum)
maximum = max(y, maximum)
i += 2
# If we had an even sized array we need to compare the
# one remaining item too.
if not odd:
x = array[length]
minimum = min(x, minimum)
maximum = max(x, maximum)
return minimum, maximum

Es definitivamente más rápido que el enfoque ingenuo que presentó Peque :

arr = np.random.random(3000000)
assert minmax(arr) == minmax_peque(arr) # warmup and making sure they are identical
%timeit minmax(arr) # 100 loops, best of 3: 2.1 ms per loop
%timeit minmax_peque(arr) # 100 loops, best of 3: 2.75 ms per loop

Como era de esperar, la nueva implementación de minmax solo toma aproximadamente 3/4 del tiempo que tomó la implementación ingenua ( 2.1 / 2.75 = 0.7636363636363637 )

Answer 4

Este es un hilo viejo, pero de todos modos, si alguien mira esto de nuevo ...

Al buscar el mínimo y máximo simultáneamente, es posible reducir el número de comparaciones. Si está flotando está comparando (lo que supongo que es) esto podría ahorrarle algo de tiempo, aunque no la complejidad computacional.

En lugar de (código de Python):

_max = ar[0]
_min= ar[0]
for ii in xrange(len(ar)):
if _max > ar[ii]: _max = ar[ii]
if _min < ar[ii]: _min = ar[ii]

primero puede comparar dos valores adyacentes en el conjunto, y luego solo comparar el más pequeño contra el mínimo actual, y el más grande contra el máximo actual:

## for an even-sized array
_max = ar[0]
_min = ar[0]
for ii in xrange(0, len(ar), 2)): ## iterate over every other value in the array
f1 = ar[ii]
f2 = ar[ii+1]
if (f1 < f2):
if f1 < _min: _min = f1
if f2 > _max: _max = f2
else:
if f2 < _min: _min = f2
if f1 > _max: _max = f1

El código aquí está escrito en Python, claramente para la velocidad que usaría C o Fortran o Cython, pero de esta manera usted hace 3 comparaciones por iteración, con len (ar) / 2 iteraciones, dando 3/2 * len (ar) comparaciones. A diferencia de eso, al hacer la comparación "de la manera más obvia" se hacen dos comparaciones por iteración, lo que da lugar a comparaciones de 2 * len (ar). Le ahorra el 25% del tiempo de comparación.

Quizás alguien algún día lo encuentre útil.

Answer 5

Hay una función para encontrar (max-min) llamada numpy.ptp si eso es útil para usted:

>>> import numpy
>>> x = numpy.array([1,2,3,4,5,6])
>>> x.ptp()
5

pero no creo que haya una forma de encontrar tanto el mínimo como el máximo con un recorrido transversal.

EDITAR: ptp solo llama a min y max bajo el capó

Answer 6

Nadie mencionó numpy.percentile , así que pensé que lo haría. Si solicita percentiles [0, 100] , le dará una matriz de dos elementos, el mínimo (percentil 0) y el máximo (percentil 100).

Sin embargo, no cumple el propósito del OP: no es más rápido que el mínimo y máximo por separado. Probablemente se deba a alguna maquinaria que permitiría percentiles no extremos (un problema más difícil, que debería llevar más tiempo).

In [1]: import numpy
In [2]: a = numpy.random.normal(0, 1, 1000000)
In [3]: %%timeit
...: lo, hi = numpy.amin(a), numpy.amax(a)
...:
100 loops, best of 3: 4.08 ms per loop
In [4]: %%timeit
...: lo, hi = numpy.percentile(a, [0, 100])
...:
100 loops, best of 3: 17.2 ms per loop
In [5]: numpy.__version__
Out[5]: ''1.14.4''

Una versión futura de Numpy podría incluir un caso especial para omitir el cálculo del percentil normal si solo se solicita [0, 100] . Sin agregar nada a la interfaz, hay una manera de preguntar a Numpy por el mínimo y máximo en una llamada (a diferencia de lo que se dijo en la respuesta aceptada), pero la implementación estándar de la biblioteca no aprovecha este caso para hacerlo vale la pena.

Answer 7

Podría usar Numba , que es un compilador de Python dinámico con NumPy que usa LLVM. La implementación resultante es bastante simple y clara:

import numpy
import numba
@numba.jit
def minmax(x):
maximum = x[0]
minimum = x[0]
for i in x[1:]:
if i > maximum:
maximum = i
elif i < minimum:
minimum = i
return (minimum, maximum)
numpy.random.seed(1)
x = numpy.random.rand(1000000)
print(minmax(x) == (x.min(), x.max()))

También debería ser más rápido que la implementación de min() & max() Numpy. Y todo sin tener que escribir una sola línea de código C / Fortran.

Haga sus propias pruebas de rendimiento, ya que siempre depende de su arquitectura, sus datos, sus versiones de paquetes ...

Answer 8

No creo que pasar el conjunto dos veces sea un problema. Considere el siguiente pseudo-código:

minval = array[0]
maxval = array[0]
for i in array:
if i < minval:
minval = i
if i > maxval:
maxval = i

Si bien solo hay 1 ciclo aquí, todavía hay 2 controles. (En lugar de tener 2 bucles con 1, marque cada uno). En realidad, lo único que ahorras es la sobrecarga de 1 ciclo. Si las matrices son realmente grandes como usted dice, esa sobrecarga es pequeña en comparación con la carga de trabajo real del ciclo. (Tenga en cuenta que todo esto se implementa en C, por lo que los bucles son más o menos libres de todos modos).

EDITAR Perdón por los 4 que ascendieron y tuvieron fe en mí. Definitivamente puedes optimizar esto.

Aquí hay un código fortran que se puede compilar en un módulo de python a través de f2py (tal vez un gurú de Cython puede venir y comparar esto con una versión C optimizada ...):

subroutine minmax1(a,n,amin,amax)
implicit none
!f2py intent(hidden) :: n
!f2py intent(out) :: amin,amax
!f2py intent(in) :: a
integer n
real a(n),amin,amax
integer i
amin = a(1)
amax = a(1)
do i=2, n
if(a(i) > amax)then
amax = a(i)
elseif(a(i) < amin) then
amin = a(i)
endif
enddo
end subroutine minmax1
subroutine minmax2(a,n,amin,amax)
implicit none
!f2py intent(hidden) :: n
!f2py intent(out) :: amin,amax
!f2py intent(in) :: a
integer n
real a(n),amin,amax
amin = minval(a)
amax = maxval(a)
end subroutine minmax2

Compilarlo a través de:

f2py -m untitled -c fortran_code.f90

Y ahora estamos en un lugar donde podemos probarlo:

import timeit
size = 100000
repeat = 10000
print timeit.timeit(
''np.min(a); np.max(a)'',
setup=''import numpy as np; a = np.arange(%d, dtype=np.float32)'' % size,
number=repeat), " # numpy min/max"
print timeit.timeit(
''untitled.minmax1(a)'',
setup=''import numpy as np; import untitled; a = np.arange(%d, dtype=np.float32)'' % size,
number=repeat), ''# minmax1''
print timeit.timeit(
''untitled.minmax2(a)'',
setup=''import numpy as np; import untitled; a = np.arange(%d, dtype=np.float32)'' % size,
number=repeat), ''# minmax2''

Los resultados son un poco asombrosos para mí:

8.61869883537 # numpy min/max
1.60417699814 # minmax1
2.30169081688 # minmax2

Debo decir que no lo entiendo completamente. Comparar solo np.min versus minmax1 y minmax2 sigue siendo una batalla perdida, por lo que no es solo un problema de memoria ...

notas - Incrementando el tamaño por un factor de 10**a y disminuyendo la repetición por un factor de 10**a (manteniendo el tamaño del problema constante) cambia el rendimiento, pero no de una manera aparentemente consistente que muestra que hay algo de interacción entre el rendimiento de la memoria y la sobrecarga de llamadas de función en python. Incluso comparando una implementación min simple en fortran beats numpy por un factor de aproximadamente 2 ...