python - Simplificando/optimizando una cadena de bucles for

dictionary filter

Question

Tengo una cadena de bucles for que funciona en una lista original de cadenas y luego, gradualmente, filtra la lista a medida que avanza en la cadena, por ejemplo:

import re

# Regex to check that a cap exist in string.
pattern1 = re.compile(r''/d.*?[A-Z].*?[a-z]'')
vocab = [''dog'', ''lazy'', ''the'', ''fly''] # Imagine it''s a longer list.

def check_no_caps(s):
    return None if re.match(pattern1, s) else s

def check_nomorethan_five(s):
    return s if len(s) <= 5 else None

def check_in_vocab_plus_x(s,x):
    # s and x are both str.
    return None if s not in vocab else s+x

slist = [''the'', ''dog'', ''jumps'', ''over'', ''the'', ''fly'']
# filter with check_no_caps
slist = [check_no_caps(s) for s in slist]
# filter no more than 5.
slist = [check_nomorethan_five(s) for s in slist if s is not None]
# filter in vocab
slist = [check_in_vocab_plus_x(s, str(i)) for i,s in enumerate(slist) if s is not None]

Lo anterior es solo un ejemplo y en realidad mis funciones para manipular las cadenas son más complicadas, pero devuelven la cadena original o una manipulada.

Podría usar generadores en lugar de una lista y hacer algo como esto:

slist = [''the'', ''dog'', ''jumps'', ''over'', ''the'', ''fly'']
# filter with check_no_caps and no more than 5.
slist = (s2 check_no_caps(s1) for s1 in slist 
         for s2 in check_nomorethan_five(s1) if s1)
# filter in vocab
slist = [check_in_vocab_plus_x(s, str(i)) for i,s in enumerate(slist) if s is not None]

O en un loco generador anidado:

slist = [''the'', ''dog'', ''jumps'', ''over'', ''the'', ''fly'']
slist = (s3 check_no_caps(s1) for s1 in slist 
         for s2 in check_nomorethan_five(s1) if s1
         for s3 in check_in_vocab_plus_x(s2, str(i)) if s2)

Tiene que haber una mejor manera. ¿Hay alguna manera de hacer que la cadena de for-loop sea más rápida?

¿Hay alguna forma de hacerlo con map , reduce y filter ? ¿Será más rápido?

Imagina que mi parte original es muy grande como 10 billones. Y mis funciones no son tan simples como las funciones anteriores, hacen algunos cálculos y hacen alrededor de 1,000 llamadas por segundo.

Answer 1

En primer lugar, es el proceso general que realiza en sus cadenas. Tomas algunas cadenas y a cada una de ellas les aplicas ciertas funciones. Entonces limpia la lista. Digamos por un momento que todas las funciones que aplica a las cadenas funcionan a una hora constante (no es cierto, pero por ahora no importará). En su solución, debe iterar la lista aplicando una función (eso es O (N)). Luego toma la siguiente función y repite otra vez (otra O (N)), y así sucesivamente. Por lo tanto, la forma obvia de acelerar es reducir el número de bucles. Eso no es tan difícil.

Lo siguiente que debes hacer es tratar de optimizar tus funciones. Por ejemplo, usa regexp para verificar si la cadena tiene letras mayúsculas, pero existe str.islower (Devuelva verdadero si todos los caracteres encajonados en la cadena están en minúsculas y hay al menos un carácter encajonado, de lo contrario es falso).

Por lo tanto, este es el primer intento de simplificar y acelerar su código:

vocab = [''dog'', ''lazy'', ''the'', ''fly''] # Imagine it''s a longer list.

# note that first two functions can be combined in one
def no_caps_and_length(s):
    return s if s.islower() and len(s)<=5 else None

# this one is more complicated and cannot be merged with first two
# (not really, but as you say, some functions are rather complicated)
def check_in_vocab_plus_x(s,x):
    # s and x are both str.
    return None if s not in vocab else s+x

# now let''s introduce a function that would pipe a string through all functions you need
def pipe_through_funcs(s):
    # yeah, here we have only two, but could be more
    funcs = [no_caps_and_length, check_in_vocab_plus_x]
    for func in funcs:
        if s == None: return s
        s = func(s)
    return s

slist = [''the'', ''dog'', ''jumps'', ''over'', ''the'', ''fly'']
# final step:
slist = filter(lambda a: a!=None, map(pipe_through_funcs, slist))

Puede haber una cosa más que se puede mejorar. Actualmente, se itera a través de la lista de elementos de modificación y luego se filtra. Pero si podría ser más rápido filtrar y luego modificar. Me gusta esto:

vocab = [''dog'', ''lazy'', ''the'', ''fly''] # Imagine it''s a longer list.

# make a function that does all the checks for filtering
# you can make a big expression and return its result,
# or a sequence of ifs, or anything in-between,
# it won''t affect performance,
# but make sure you put cheaper checks first
def my_filter(s):
    if len(s)>5: return False
    if not s.islower(): return False
    if s not in vocab: return False
    # maybe more checks here
    return True

# now we need modifying function
# there is a concern: if you need indices as they were in original list
# you might need to think of some way to pass them here
# as you iterate through filtered out list
def modify(s,x):
    s += x
    # maybe more actions
    return s

slist = [''the'', ''dog'', ''jumps'', ''over'', ''the'', ''fly'']
# final step:
slist = map(modify, filter(my_filter, slist))

Tenga en cuenta también que, en algunos casos, los generadores, los mapas y las cosas pueden ser más rápidos, pero eso no siempre es cierto. Creo que si la cantidad de elementos que filtra es considerable, podría ser más rápido usar un bucle for con el apéndice. No diría que será más rápido, pero podrías intentar algo como esto:

initial_list = [''the'', ''dog'', ''jumps'', ''over'', ''the'', ''fly'']
new_list = []
for s in initial_list:
    processed = pipe_through_funcs(s)
    if processed != None: new_list.append(processed)

Answer 2

En primer lugar: creo que su código de ejemplo no está haciendo lo que piensa. El resultado es [''the0'', ''dog1'', None, None, ''the4'', ''fly5''] , pero creo que no quieres los valores de None .

La única respuesta razonable a esto es medir su rendimiento e identificar los cuellos de botella, que probablemente estarán en sus funciones de verificación y no en el bucle externo.

Desde fuera de las funciones de verificación, la única optimización real que veo es realizar las comprobaciones que reducirán primero su conjunto, de modo que tendrá bucles más pequeños en las siguientes iteraciones y reduzca la cantidad de comprobaciones que realiza sobre los valores que descartará de todas formas. Dependiendo de sus datos y la cantidad de valores que se descartan en las primeras comprobaciones, es posible que vea un gran salto en el rendimiento ... ¡O no!

La única manera de saber realmente es perfilar su código. Debería usar cProfile junto con RunSnakeRun y trabajar en sus cuellos de botella, de lo contrario terminará optmizing las cosas incorrectas.

Para crear un perfil de su script, puede ejecutarlo de la siguiente manera: python -m cProfile <script-name>

Answer 3

Las optimizaciones dependen mucho del código específico. Sin saber qué manipulaciones reales se ejecutan en cadenas y la naturaleza de los datos, hay pocas posibilidades de resultados efectivos. Además, OP describe específicamente las manipulaciones de las cuerdas como "más complicadas". Esto reduce la parte de los bucles externos en el rendimiento general.

Dos sugerencias simples y relevantes que puedo agregar a otras respuestas aquí, se refieren al uso de llamadas de función incorporadas y generadores para optimizar:

1. Las funciones integradas mejoran el rendimiento al mantener más trabajo en el código nativo. Cuando los usas para llamar a lambda o, de lo contrario, a las llamadas de Python, pierden la mayor parte del valor de rendimiento. Utilícelos cuando una tarea se puede completar utilizando solo elementos nativos. itertools , operator y functools pueden brindar mucha ayuda en esto.
2. Los generadores ayudan principalmente en las optimizaciones de memoria, donde no desea mantener todos los valores en la memoria a la vez. Si puede hacer todo en una iteración sin usarlos, es mejor y ahorra los gastos generales del generador.

Otra cosa que habría cambiado en el ejemplo específico es el uso de expresiones regulares. En este caso simple de letras mayúsculas puede ser rápido comparar caracteres. Las expraciones regulares que no están bien construidas pueden ser peligrosas para el rendimiento, tiendo a evitarlas sin el beneficio específico en comparaciones más completas.

vocab = [''dog'', ''lazy'', ''the'', ''fly''] # Imagine it''s a longer list.

def check_no_caps(s):
    for char in s:
        if ''A'' <= char <= ''Z'':
            return None
    return s

def check_nomorethan_five(s):
    return s if len(s) <= 5 else None

def check_in_vocab_plus_x(s, x):
    # s and x are both str.
    return None if s not in vocab else s + str(x)

slist = [''the'', ''dog'', ''jumps'', ''over'', ''the'', ''fly'']

result = [check_in_vocab_plus_x(check_nomorethan_five(check_no_caps(string)), i) for i, string in enumerate(slist)]

Answer 4

Puedo ver tres optimizaciones que podrías hacer. La primera es que si todas las palabras en "vocab" son menores o iguales a cinco, no necesita verificar si las palabras en "slist" son menores o iguales a cinco, lo que significa que puede eliminar todo eso en bucle. La segunda optimización es que si todas las palabras en "vocab" son solo en minúsculas y su algoritmo de comparación de palabras distingue entre mayúsculas y minúsculas, entonces no necesita verificar si una palabra en "slist" es sensible a mayúsculas, lo que significa que puede eliminarla. en bucle.

La generalización básica para este principio es que si una palabra debe cumplir varias condiciones y una condición implica otra (es decir, si necesita un número que sea divisible entre cuatro y dos, solo debe verificar si es divisible entre cuatro), puede Eliminar la condición implícita.

Si "vocab" tiene palabras de más de cinco letras o palabras con mayúsculas, debería poder eliminarlas de "vocab", ya que todas las palabras en "slist" que están en mayúsculas o que tengan más de cinco letras podrían eliminarse De tus cheques antes de llegar a vocab.

La última optimización es que determinar si una palabra en "slist" está en "vocab" es lo mismo que encontrar su intersección. Hay muchos algoritmos relativamente rápidos para hacer esto que no requieren un bucle for. Aquí hay unos ejemplos:

Lista eficiente de algoritmo de intersección

¿Cálculo de intersecciones de conjuntos en tiempo lineal?

En resumen, puede eliminar dos bucles for y reducir la complejidad de tiempo de la comparación "vocab" - "slist" para bucle.

Answer 5

Si haces que tus funciones de transformación se unifiquen, podrías hacer algo como esto:

import random
slist = []
for i in range(0,100):
    slist.append(random.randint(0,1000))

# Unified functions which have the same function description
# x is the value
# i is the counter from enumerate
def add(x, i):
    return x + 2

def replace(x, i):
    return int(str(x).replace(''2'', str(i)))

# Specifying your pipelines as a list of tuples 
# Where tuple is (filter function, transformer function)
_pipeline = [
    (lambda s: True, add),
    (lambda s: s % 2 == 0, replace),
]

# Execute your pipeline
for _filter, _fn in _pipeline:
    slist = map(lambda item: _fn(*item), enumerate(filter(_filter, slist)))

El código funciona tanto en python 2 como en python 3. La diferencia es que en Python3 todo devuelve un generador, por lo que no se ejecuta hasta que tiene que ser. Así que efectivamente vas a tener una iteración sobre tu lista.

print(slist)
<map object at 0x7f92b8315fd0>

Sin embargo, iterar una o varias veces no supondrá una gran diferencia siempre que se pueda hacer en la memoria, ya que, independientemente del método de iteración, se debe ejecutar la misma cantidad de transformación y filtrado. Entonces, para mejorar su código, intente hacer sus funciones de filtro y transformación lo más rápido posible.

Por ejemplo, lo que @Rawing mencionó para tener vocab como un conjunto en lugar de una lista hará una gran diferencia, especialmente con un gran número de elementos.

Answer 6

Tienes un montón de cheques con los que puedes hacer un iterable:

def check1(s):
    if s.islower():
        return s

def check2(s):
    if len(s) < 5:
        return s

checks = [check1, check2]

Y un iterable de cuerdas:

l = [''dog'', ''Cat'', ''house'', ''foo'']

Entonces, una de las preguntas es si debe iterar las verificaciones primero o las cadenas primero.

def checks_first(l, checks):
    for check in checks:
        l = filter(None, map(check, l))

    return list(l)


def strings_first(l, checks):
    res = []

    for item in l:
        for check in checks:
            item = check(item)
            if item is None:
                break
        else:
            res.append(item)

    return res

Puedes timeit estos dos enfoques con el módulo timeit . Nota: es posible que tenga que usar un subconjunto de las cadenas para obtener estos resultados de manera oportuna.

import timeit

print(timeit.timeit(''checks_first(l, checks)'', setup=''from __main__ import checks_first, checks, l'', number=10))
print(timeit.timeit(''strings_first(l, checks)'', setup=''from __main__ import strings_first, checks, l'', number=10))

Lo que es más rápido depende de la proporción de verificaciones de números con respecto a las cadenas de números, el hardware, etc. De las pruebas que he realizado parecen funcionar aproximadamente a la misma velocidad.

Mi conjetura es que los mayores ahorros de tiempo se obtendrán al optimizar algunos de los cheques. Un buen punto de partida es identificar los cheques que cuestan más tiempo. Esto se puede hacer con un cierre para envolver sus funciones de verificación.

import functools

def time_func(func, timer_dict):

    @functools.wraps(func)
    def inner(*args, **kwargs):
        t0 = time.time()
        res = func(*args, **kwargs)
        timer_dict[func.__name__] += time.time() - t0
        return res

    return inner

Para aplicar esto a los cheques:

from collections import defaultdict

timer_dict = defaultdict(lambda: 0)
checks = [time_func(check, timer_dict) for check in checks]

Luego, llame a la (s) función (es) que aplican los controles y vea timer_dict para obtener información de tiempo.

checks_first(l, checks)
strings_first(l, checks)

print(dict(timer_dict))

# {''check1'': 0.41464924812316895, ''check2'': 0.2684309482574463}

Luego, identifique los cuellos de botella en las verificaciones costosas, ya sea mediante inspección o creación de perfiles. Esto último se puede hacer sincronizando líneas de código con el módulo de time o usando un perfilador de línea como this .

Optimice sus algos y estructuras de datos para deshacerse de estos cuellos de botella. Puede echar un vistazo a Cython para obtener el código que necesita llevar a (cerca de) la velocidad de C.