Matrices que tienen un paso constante entre elementos
En el caso de una rangeo cualquier otra matriz que aumente linealmente, simplemente puede calcular el índice mediante programación, sin necesidad de iterar sobre la matriz:
def first_index_calculate_range_like(val, arr):
if len(arr) == 0:
raise ValueError('no value greater than {}'.format(val))
elif len(arr) == 1:
if arr[0] > val:
return 0
else:
raise ValueError('no value greater than {}'.format(val))
first_value = arr[0]
step = arr[1] - first_value
# For linearly decreasing arrays or constant arrays we only need to check
# the first element, because if that does not satisfy the condition
# no other element will.
if step <= 0:
if first_value > val:
return 0
else:
raise ValueError('no value greater than {}'.format(val))
calculated_position = (val - first_value) / step
if calculated_position < 0:
return 0
elif calculated_position > len(arr) - 1:
raise ValueError('no value greater than {}'.format(val))
return int(calculated_position) + 1
Uno probablemente podría mejorar eso un poco. Me he asegurado de que funcione correctamente para algunas matrices y valores de muestra, pero eso no significa que no pueda haber errores allí, especialmente teniendo en cuenta que usa flotantes ...
>>> import numpy as np
>>> first_index_calculate_range_like(5, np.arange(-10, 10))
16
>>> np.arange(-10, 10)[16] # double check
6
>>> first_index_calculate_range_like(4.8, np.arange(-10, 10))
15
Dado que puede calcular la posición sin ninguna iteración, será un tiempo constante ( O(1)) y probablemente pueda vencer a todos los otros enfoques mencionados. Sin embargo, requiere un paso constante en la matriz, de lo contrario producirá resultados incorrectos.
Solución general usando numba
Un enfoque más general sería usar una función numba:
@nb.njit
def first_index_numba(val, arr):
for idx in range(len(arr)):
if arr[idx] > val:
return idx
return -1
Eso funcionará para cualquier matriz, pero tiene que iterar sobre la matriz, por lo que en el caso promedio será O(n):
>>> first_index_numba(4.8, np.arange(-10, 10))
15
>>> first_index_numba(5, np.arange(-10, 10))
16
Punto de referencia
Aunque Nico Schlömer ya proporcionó algunos puntos de referencia, pensé que podría ser útil incluir mis nuevas soluciones y probar diferentes "valores".
La configuración de prueba:
import numpy as np
import math
import numba as nb
def first_index_using_argmax(val, arr):
return np.argmax(arr > val)
def first_index_using_where(val, arr):
return np.where(arr > val)[0][0]
def first_index_using_nonzero(val, arr):
return np.nonzero(arr > val)[0][0]
def first_index_using_searchsorted(val, arr):
return np.searchsorted(arr, val) + 1
def first_index_using_min(val, arr):
return np.min(np.where(arr > val))
def first_index_calculate_range_like(val, arr):
if len(arr) == 0:
raise ValueError('empty array')
elif len(arr) == 1:
if arr[0] > val:
return 0
else:
raise ValueError('no value greater than {}'.format(val))
first_value = arr[0]
step = arr[1] - first_value
if step <= 0:
if first_value > val:
return 0
else:
raise ValueError('no value greater than {}'.format(val))
calculated_position = (val - first_value) / step
if calculated_position < 0:
return 0
elif calculated_position > len(arr) - 1:
raise ValueError('no value greater than {}'.format(val))
return int(calculated_position) + 1
@nb.njit
def first_index_numba(val, arr):
for idx in range(len(arr)):
if arr[idx] > val:
return idx
return -1
funcs = [
first_index_using_argmax,
first_index_using_min,
first_index_using_nonzero,
first_index_calculate_range_like,
first_index_numba,
first_index_using_searchsorted,
first_index_using_where
]
from simple_benchmark import benchmark, MultiArgument
y las parcelas se generaron usando:
%matplotlib notebook
b.plot()
el artículo está al principio
b = benchmark(
funcs,
{2**i: MultiArgument([0, np.arange(2**i)]) for i in range(2, 20)},
argument_name="array size")
La función numba funciona mejor seguida de la función de cálculo y la función de clasificación de búsqueda. Las otras soluciones funcionan mucho peor.
el artículo está al final
b = benchmark(
funcs,
{2**i: MultiArgument([2**i-2, np.arange(2**i)]) for i in range(2, 20)},
argument_name="array size")
Para las matrices pequeñas, la función numba funciona increíblemente rápido, sin embargo, para las matrices más grandes, la función de cálculo y la función ordenada de búsqueda la superan.
el artículo está en sqrt (len)
b = benchmark(
funcs,
{2**i: MultiArgument([np.sqrt(2**i), np.arange(2**i)]) for i in range(2, 20)},
argument_name="array size")
Esto es mas interesante. Nuevamente, numba y la función de cálculo funcionan muy bien, sin embargo, esto en realidad está desencadenando el peor caso de búsqueda ordenada, que realmente no funciona bien en este caso.
Comparación de las funciones cuando ningún valor satisface la condición
Otro punto interesante es cómo se comportan estas funciones si no hay ningún valor cuyo índice deba devolverse:
arr = np.ones(100)
value = 2
for func in funcs:
print(func.__name__)
try:
print('-->', func(value, arr))
except Exception as e:
print('-->', e)
Con este resultado:
first_index_using_argmax
--> 0
first_index_using_min
--> zero-size array to reduction operation minimum which has no identity
first_index_using_nonzero
--> index 0 is out of bounds for axis 0 with size 0
first_index_calculate_range_like
--> no value greater than 2
first_index_numba
--> -1
first_index_using_searchsorted
--> 101
first_index_using_where
--> index 0 is out of bounds for axis 0 with size 0
Searchsorted, argmax y numba simplemente devuelven un valor incorrecto. Sin embargo searchsortedynumba devolver un índice que no es un índice válido para la matriz.
Las funciones where, min, nonzeroy calculatelanzan una excepción. Sin embargo, solo la excepción paracalculate realmente dice algo útil.
Eso significa que uno realmente tiene que ajustar estas llamadas en una función de contenedor apropiada que capture excepciones o valores de retorno no válidos y manejar adecuadamente, al menos si no está seguro de si el valor podría estar en la matriz.
Nota: El cálculo y las searchsortedopciones solo funcionan en condiciones especiales. La función "calcular" requiere un paso constante y la búsqueda ordenada requiere que se ordene la matriz. Por lo tanto, estos podrían ser útiles en las circunstancias correctas, pero no son soluciones generales para este problema. En caso de que estés lidiando con ordenados listas de Python es posible que desee echar un vistazo a la bisect módulo en lugar de utilizar Numpys searchsorted.
