Uniendo cuerdas. ¿Generador o lista de comprensión?

Considere el problema de extraer alfabetos de una cadena enorme.

Una forma de hacerlo es

''.join([c for c in hugestring if c.isalpha()]) 

El mecanismo es claro: la lista de comprensión genera una lista de caracteres. El método de unión sabe cuántos caracteres necesita unir accediendo a la longitud de la lista.

Otra forma de hacerlo es

 ''.join(c for c in hugestring if c.isalpha()) 

Aquí la comprensión del generador resulta en un generador. El método de unión no sabe cuántos caracteres se unirán porque el generador no posee un atributo len . Por lo tanto, esta forma de unirse debería ser más lenta que el método de comprensión de lista.

Pero las pruebas en python muestran que no es más lento. ¿Por qué esto es tan? ¿Alguien puede explicar cómo funciona unirse en un generador.

Para ser claro:

 sum(j for j in range(100)) 

no necesita tener ningún conocimiento de 100 porque puede realizar un seguimiento de la sum acumulada. Puede acceder al siguiente elemento utilizando el siguiente método en el generador y luego agregarlo a la sum acumulada. Sin embargo, dado que las cadenas son inmutables, la unión de cadenas de forma acumulativa creará una nueva cadena en cada iteración. Así que esto llevaría mucho tiempo.

Cuando llama a str.join(gen) donde gen es un generador, Python hace el equivalente de list(gen) antes de pasar a examinar la longitud de la secuencia resultante.

Específicamente, si observa el código que implementa str.join en CPython , verá esta llamada:

  fseq = PySequence_Fast(seq, "can only join an iterable"); 

La llamada a PySequence_Fast convierte el argumento seq en una lista si ya no era una lista o una tupla.

Por lo tanto, las dos versiones de su llamada se manejan de manera casi idéntica. En la lista de comprensión, usted mismo crea la lista y la pasa a join . En la versión de la expresión del generador, el objeto generador que se pasa se convierte en una list justo al inicio de la join , y el rest del código funciona de la misma manera para ambas versiones.

join() no necesita implementarse como un agregado secuencial de elementos de la secuencia a una cadena acumulada más larga y más larga (lo que de hecho sería muy lento para secuencias largas); sólo necesita producir el mismo resultado. Por lo tanto, join() probablemente solo está agregando caracteres a un búfer de memoria interna y creando una cadena al final. El constructo de comprensión de lista, por otro lado, necesita primero construir la lista (atravesando el generador de hugestring ), y solo entonces dejar que join() comience su trabajo.

Además, dudo que join() mire la longitud de la lista, ya que no puede saber que cada elemento es un solo carácter (en la mayoría de los casos, no lo será); es probable que solo obtenga un generador de la lista.

Al menos en mi máquina, la comprensión de la lista es más rápida para el caso que probé, probablemente debido a que ''.join ser capaz de optimizar la asignación de memoria. Es probable que solo dependa del ejemplo específico que está probando (por ejemplo, si la condición que está probando ocurre con menos frecuencia, el precio que CPython paga por no saber la longitud anticipada puede ser menor):

 In [18]: s = ''.join(np.random.choice(list(string.printable), 1000000)) In [19]: %timeit ''.join(c for c in s if c.isalpha()) 10 loops, best of 3: 69.1 ms per loop In [20]: %timeit ''.join([c for c in s if c.isalpha()]) 10 loops, best of 3: 61.8 ms per loop