¿Cómo me alejo de la escuela de pensamiento "for-loop"?

78

Esta es una pregunta bastante conceptual, pero esperaba poder obtener un buen consejo al respecto. Mucha de la programación que hago es con arrays ( NumPy ); A menudo tengo que hacer coincidir elementos en dos o más arreglos que son de diferentes tamaños y lo primero que hago es un bucle for o, peor aún, un bucle for anidado. Quiero evitar los bucles for tanto como sea posible, porque son lentos (al menos en Python).

Sé que para muchas cosas con NumPy hay comandos predefinidos que solo necesito investigar, pero usted (como programadores más experimentados) tiene un proceso de pensamiento general que viene a la mente cuando tiene ¿Para iterar algo?

A menudo tengo algo como esto, lo cual es horrible y quiero evitarlo:

small_array = np.array(["one", "two"])
big_array = np.array(["one", "two", "three", "one"])

for i in range(len(small_array)):
    for p in range(len(big_array)):
        if small_array[i] == big_array[p]:
            print "This item is matched: ", small_array[i]

Sé que hay muchas formas diferentes de lograr esto en particular, pero me interesa un método general de pensamiento, si existe.

    
pregunta turnip 26.08.2014 - 14:02
fuente

3 respuestas

89

Esta es una dificultad conceptual común cuando se aprende a usar NumPy de manera efectiva. Normalmente, el procesamiento de datos en Python se expresa mejor en términos de iteradores , para mantener el uso de memoria bajo, para maximizar las oportunidades de paralelismo con el sistema de E / S y para reutilizar y combinar partes de algoritmos .

Pero NumPy hace que todo sea al revés: el mejor enfoque es expresar el algoritmo como una secuencia de operaciones de todo el conjunto , para minimizar la cantidad de tiempo empleado en el lento intérprete de Python y maximizar el cantidad de tiempo empleado en rutinas NumPy compiladas rápidamente.

Aquí está el enfoque general que tomo:

  1. Mantenga la versión original de la función (que está seguro de que es correcta) para que pueda probarla en comparación con sus versiones mejoradas, tanto en cuanto a corrección como en velocidad.

  2. Trabaja desde adentro hacia afuera: es decir, comienza con el bucle más interno y ve si se puede vectorizar; luego, cuando haya hecho eso, salga de un nivel y continúe.

  3. Pase mucho tiempo leyendo la documentación de NumPy . Hay muchas funciones y operaciones allí y no siempre tienen nombres brillantes, por lo que vale la pena conocerlas. En particular, si se encuentra pensando, "si solo hubiera una función que hiciera tal o cual cosa", entonces vale la pena dedicar diez minutos a buscarla. Por lo general, está en algún lugar.

No hay sustituto para la práctica, así que voy a darte algunos problemas de ejemplo. El objetivo de cada problema es volver a escribir la función para que esté completamente vectorizada : es decir, para que consista en una secuencia de operaciones NumPy en arrays completos, sin bucles nativos de Python (sin for o while de declaraciones, sin iteradores ni comprensiones).

Problema 1

def sumproducts(x, y):
    """Return the sum of x[i] * y[j] for all pairs of indices i, j.

    >>> sumproducts(np.arange(3000), np.arange(3000))
    20236502250000

    """
    result = 0
    for i in range(len(x)):
        for j in range(len(y)):
            result += x[i] * y[j]
    return result

Problema 2

def countlower(x, y):
    """Return the number of pairs i, j such that x[i] < y[j].

    >>> countlower(np.arange(0, 200, 2), np.arange(40, 140))
    4500

    """
    result = 0
    for i in range(len(x)):
        for j in range(len(y)):
            if x[i] < y[j]:
                result += 1
    return result

Problema 3

def cleanup(x, missing=-1, value=0):
    """Return an array that's the same as x, except that where x ==
    missing, it has value instead.

    >>> cleanup(np.arange(-3, 3), value=10)
    ... # doctest: +NORMALIZE_WHITESPACE
    array([-3, -2, 10, 0, 1, 2])

    """
    result = []
    for i in range(len(x)):
        if x[i] == missing:
            result.append(value)
        else:
            result.append(x[i])
    return np.array(result)

Spoilers abajo. ¡Obtendrá los mejores resultados si lo hace antes de ver mis soluciones!

Respuesta 1

  

np.sum (x) * np.sum (y)

Respuesta 2

  

np.sum (np.searchsorted (np.sort (x), y))

Respuesta 3

  

np.where (x == falta, valor, x)

    
respondido por el Gareth Rees 26.08.2014 - 16:16
fuente
8

Para que las cosas sean más rápidas, debe leer sus estructuras de datos y usar las adecuadas.

Para tamaños no triviales de matriz pequeña y matriz grande (digamos pequeño = 100 elementos y grande = 10.000 elementos) una forma de hacerlo es ordenar la matriz pequeña, luego iterar sobre matriz grande y usar una búsqueda binaria para encontrar elementos coincidentes en la pequeña matriz.

Esto haría que la complejidad del tiempo sea máxima, O (N log N) (y para arreglos pequeños pequeños y arrays muy grandes está más cerca de O (N)) donde su solución de bucle anidado es O (N ^ 2)

Sin embargo. Las estructuras de datos más eficientes dependen en gran medida del problema real.

    
respondido por el Pieter B 26.08.2014 - 15:08
fuente
-3

Puedes usar un diccionario para optimizar el rendimiento de forma significativa

Este es otro ejemplo:

locations = {}
for i in range(len(airports)):
    locations[airports["abb"][i][1:-1]] = (airports["height"][i], airports["width"][i])

for i in range(len(uniqueData)):
    h, w = locations[uniqueData["dept_apt"][i]]
    uniqueData["dept_apt_height"][i] = h
    uniqueData["dept_apt_width"][i] = w
    
respondido por el Jakub Bares 12.10.2016 - 11:48
fuente

Lea otras preguntas en las etiquetas