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

79

Esta es una pregunta bastante conceptual, pero esperaba poder obtener buenos consejos al respecto. Gran parte de la programación que hago es con matrices ( NumPy ); A menudo tengo que hacer coincidir elementos en dos o más matrices que son de diferentes tamaños y lo primero que hago es un bucle for anidado 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 ¿tienes (como programadores más experimentados) un proceso de pensamiento general que se te ocurra cuando tienes que repetir algo?

Así que 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 varias formas diferentes de lograr esto en particular, pero estoy interesado en un método general de pensamiento, si existe.

nabo
fuente
10
Estás buscando programación funcional : expresiones lambda, funciones de orden superior, generación de expresiones, etc. Google.
Kilian Foth
42
I want to avoid for-loops as much as possible because they are slow (at least in Python).Parece que estás resolviendo el problema incorrecto aquí. Si necesita iterar sobre algo, necesita iterar sobre algo; obtendrá un rendimiento similar sin importar qué construcción de Python use. Si su código es lento no es porque tenga forbucles; es porque está haciendo un trabajo innecesario o está haciendo el trabajo en el lado de Python que podría hacerse en el lado C. En tu ejemplo estás haciendo un trabajo extra; podrías haberlo hecho con un bucle en lugar de dos.
Doval
24
@Doval Desafortunadamente no, en NumPy . Un Python para bucle que realiza la adición de elementos puede ser fácilmente varias veces (!) Más lento que el operador vectorizado NumPy (que no solo está escrito en C sino que usa instrucciones SSE y otros trucos) para obtener tamaños de matriz realistas.
46
Algunos de los comentarios anteriores parecen malinterpretar la pregunta. Al programar en NumPy, obtiene los mejores resultados si puede vectorizar su cálculo , es decir, reemplazar bucles explícitos en Python con operaciones de matriz completa en NumPy. Esto es conceptualmente muy diferente de la programación ordinaria en Python, y lleva tiempo aprender. Por lo tanto, creo que es razonable que el OP solicite asesoramiento sobre cómo aprender a hacerlo.
Gareth Rees
3
@PieterB: Sí, eso es correcto. "Vectorización" no es lo mismo que "elegir el mejor algoritmo". Son dos fuentes separadas de dificultad para lograr implementaciones eficientes, por lo que es mejor pensar en ellas una por una.
Gareth Rees

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 bajo el uso de memoria, para maximizar las oportunidades de paralelismo con el sistema de E / S y para proporcionar la reutilización y combinación de partes de algoritmos.

Pero NumPy pone todo eso al revés: el mejor enfoque es expresar el algoritmo como una secuencia de operaciones de matriz completa , para minimizar la cantidad de tiempo que se pasa en el intérprete lento de Python y maximizar la cantidad de tiempo que se pasa en las rutinas compiladas rápidas de NumPy.

Aquí está el enfoque general que tomo:

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

  2. Trabaje de adentro hacia afuera: es decir, comience con el bucle más interno y vea si se puede vectorizar; luego, cuando haya hecho eso, salga 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 un nombre brillante, por lo que vale la pena conocerlas. En particular, si te encuentras pensando, "si solo hubiera una función que hiciera tal y tal cosa", entonces vale la pena pasar diez minutos buscándola. Por lo general, está allí en alguna parte.

No hay sustituto para la práctica, así que te voy a dar algunos problemas de ejemplo. La meta para cada problema es volver a escribir la función de modo que quede totalmente vectorizado : es decir, para que consiste en una secuencia de operaciones NumPy las matrices de enteros, sin bucles naturales Python (sin foro whiledeclaraciones, no hay iteradores o por comprensión).

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 a continuación. ¡Obtendrá los mejores resultados si lo intenta antes de buscar 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 == faltante, valor, x)

Gareth Rees
fuente
Espera, ¿hay un error tipográfico en la última respuesta o NumPy modifica la forma en que Python interpreta el código?
Izkata
1
@Izkata No modifica nada per se, pero las operaciones lógicas aplicadas a las matrices se definen para devolver matrices booleanas.
sapi
@sapi Ah, me perdí lo que estaba pasando en los doctests, pensé que eran simpleslist
Izkata
Tal vez debería haber una manera de incrustar APL?
Me encanta cómo das la tarea.
Koray Tugay
8

Para acelerar las cosas, debe leer sobre sus estructuras de datos y utilizar las apropiadas.

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 la matriz grande y usar una búsqueda binaria para encontrar elementos coincidentes en la pequeña matriz

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

Sin embargo. qué estructuras de datos son más eficientes depende en gran medida del problema real.

Pieter B
fuente
-3

Puede usar un diccionario para optimizar el rendimiento significativamente

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
Jakub Bares
fuente
2
Esto claramente sigue usando la escuela de pensamiento "for-loop".
8bittree