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

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.

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)

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.

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