Concatenar de manera eficiente las subcadenas de larga lista de cadenas -- python campo con performance campo con strings campo con python-2.x camp codereview Relacionados El problema

Efficiently concatenate substrings of long list of strings


4
vote

problema

Español

Tengo problemas de rendimiento con la siguiente función de Python:

  def remove_comments(buffer):     new_buffer = ''     lines = buffer.split(' ')     for line in lines:         line_wo_comments = line.split('--')[0] + ' '         new_buffer = new_buffer + line_wo_comments     return new_buffer   

Cuando el tampón es muy grande (miles de líneas +), la función se vuelve más lenta y más lenta a medida que procesa el búfer.

¿Qué técnicas podría usar para acelerar esta función de llamada?

Supongamos que la entrada es un archivo de código fuente. Líneas de longitud 1 - ~ 120 caracteres. Las líneas pueden o no tener comentarios. Los archivos podrían ser muchas líneas de largo. Los especialmente las problemáticas son generadas por máquina (1-10K + LÍNEAS DE LARGO).

Actualización: la intención es usar esto como un paso de "pre-procesamiento" para los contenidos de búfer (un archivo). Supongo que no soy demasiado interesado en posiblemente maneras de refactorizar completamente esto (es decir, métodos para evitar la necesidad de iterar a través de todas las líneas varias veces), pero más bien hacer la esencia del tampón en / tampón tan rápido como sea posible.

Original en ingles

I am having performance problems with the following python function:

def remove_comments(buffer):     new_buffer = ''     lines = buffer.split('\n')     for line in lines:         line_wo_comments = line.split('--')[0] + '\n'         new_buffer = new_buffer + line_wo_comments     return new_buffer 

When buffer is very large (thousands+ lines), the function gets slower and slower as it processes the buffer.

What techniques could I use to speed this function call up?

Assume that the input is a source code file. Lines of length 1 - ~120 characters. Lines may or may not have comments. The files could be many lines long. The especially problematic ones are machine generated (1-10k+ lines long).

Update: The intention is to use this as a "pre-processing" step for the buffer contents (a file). I guess I am not too interested in possibly ways to completely refactor this (i.e. methods to avoid needing to iterate through all the lines multiple times), but rather make the essence of buffer in / buffer out as fast as possible.

           
 
 

Lista de respuestas

3
 
vote
vote
La mejor respuesta
 

La función es lenta porque está realizando repetidamente de una concatenación de cadena con new_buffer = new_buffer + line_wo_comments . Dado que las cadenas en Python son inmutables, cada concatenación requiere copiar todo el resultado hasta ese punto para cada línea. El rendimiento sería aproximadamente O ( N 2 ), donde n es la longitud del texto.

Creo que incluso la división del texto en una lista de líneas es demasiado complicada. Solo haz una sustitución simple:

  import re  def remove_comments(buffer):     return re.sub(r'--[^ ]*', '', buffer)   
 

The function is slow because you are repeatedly doing of string concatenation with new_buffer = new_buffer + line_wo_comments. Since strings in Python are immutable, every concatenation requires copying the entire result up to that point for each line. The performance would be roughly O(n2), where n is the length of the text.

I think that even splitting up the text into a list of lines is too complicated. Just do a simple substitution:

import re  def remove_comments(buffer):     return re.sub(r'--[^\n]*', '', buffer) 
 
 
3
 
vote

The Sección de consejos de rendimiento en Python.org tiene comentarios sobre cómo hacer una concatenación de cadena repetida que Usted puede encontrar aquí:

https://wiki.python.org/moin/pythonspeed/performancetips#string_concatenation < / a>

Específicamente, sugiere usar "".join(listOfStrings) en lugar de agregar repetidamente a un acumulador con += .

Así que intentaría algo así, usando re.finditer() Para encontrar todos los comentarios y colocar las piezas que no son comentarios en una lista:

  import re  def removeComments(s):   chunks = []   offset = 0   for m in re.finditer("--.* ", s):     chunks.append( s[offset: m.start(0)] )     offset = m.end(0)-1   chunks.append( s[offset:] )   return "".join(chunks)  s = """ line 1 line 2  -- comment 2 line 3 line 4 -- comment 4 line 5 line 6 -- comment 6 line 7 """ print removeComments(s)   

Una ventaja de este enfoque sobre la división de cada línea es que si hay grandes trozos de su programa que no tienen comentarios, se transferirán a la lista 99887766655444337 en una pieza en lugar de las líneas separadas .

Actualización

También intentaría usar un enfoque REGEXP Reemplazar, podría ser aún más rápido:

  def removeComments(s):   return re.sub('(?m)--.*$', '', s)   
 

The Performance Tips section at python.org has comments about doing repeated string concatenation which you may find here:

https://wiki.python.org/moin/PythonSpeed/PerformanceTips#String_Concatenation

Specifically, it suggests using "".join(listOfStrings) instead of repeatedly appending to an accumulator with +=.

So I would try something like this, using re.finditer() to find all of the comments, and place the non-comment parts into a list:

import re  def removeComments(s):   chunks = []   offset = 0   for m in re.finditer("--.*\n", s):     chunks.append( s[offset: m.start(0)] )     offset = m.end(0)-1   chunks.append( s[offset:] )   return "".join(chunks)  s = """ line 1 line 2  -- comment 2 line 3 line 4 -- comment 4 line 5 line 6 -- comment 6 line 7 """ print removeComments(s) 

An advantage of this approach over splitting each line is that if there are large chunks of your program which do not have any comments they will transferred to the chunks list in one piece instead of as separate lines.

Update

I would also try using a regexp replace approach - it could be even faster:

def removeComments(s):   return re.sub('(?m)--.*$', '', s) 
 
 
     
     
3
 
vote

Algunas cosas:

  1. Siga el estilo PEP8.
  2. Como otros han dicho, 9988776655544330 es más eficiente. Sin emabargo:
    1. Puede usar ' '.join para evitar que para agregar manualmente la nueva línea.
    2. Si va a trabajar con líneas individualmente, o va a guardar el archivo, es mejor usar un generador y no unirse en absoluto.
  3. Puedes elegir cuántas divisiones para hacer. Es mucho más rápido hacer una división que un número arbitrario como usted. Es aún más rápido usando partition , que siempre hace solo una dividida.
  4. Si está leyendo el búfer en, de nuevo, sería mejor iterar sobre las líneas en lugar de leer todo el asunto de una vez y dividir.

Entonces, usando su código, suponiendo que necesitamos un búfer dentro y fuera, este sería un enfoque mucho más eficiente:

  def remove_comments(buffer):     lines = buffer.splitlines()     return ' '.join(line.partition('--')[0] for line in lines)   

Sin embargo, por ejemplo, digamos que desea leer un archivo, elimine los comentarios, luego guárdelo nuevamente. Este sería un enfoque mucho más eficiente:

  with open(infile, 'r') as fin, open(outfile, 'w') as fout:     for line in infile:         newline = line.partition('--')[0]         outfile.write(newline+' ')   

o mejor aún:

  with open(infile, 'r') as fin, open(outfile, 'w') as fout:     outfile.writelines(line.partition('--')[0]+' ' for line in infile)   

El punto clave de estos dos enfoques es que solo mantienen una línea en la memoria a la vez, lo que salva en la memoria enormemente.

O, si desea hacer alguna otra manipulación en las líneas antes de ahorrar, podría hacer algo así:

  with open(infile, 'r') as fin, open(outfile, 'w') as fout:    newlines1 = (line.partition('--')[0] for line in infile)    newlines2 = (myfunc1(line) for line in newlines1)    newlines3 = (myfunc2(line) for line in newlines2)    fout.writelines(line+' ' for line in newlines3)   

En este caso, mfunc1 y myfunc2 son funciones que toman una sola cadena y devuelve una sola cadena. Este enfoque aplicará cada operación a cada línea, pero solo tendrá una línea en la memoria a la vez.

Realmente no importa lo que hagas en última instancia con las líneas. Usted los convierte en frío a números o listas de números y realice algunos cálculos en ellos, envíelos a través de una red a otra máquina, o lo que sea. El punto es que al hacerlo utilizando generadores, iteradores y expresiones generadoras, puede ahorrar en la memoria y aumentar el rendimiento por mucho porque solo tiene una línea en la memoria a la vez.

 

A few things:

  1. Follow pep8 style.
  2. As others have said, join is more efficient. However:
    1. You can use '\n'.join to avoid having to manually append the newline.
    2. If you are going to be working with lines individually, or are going to save the file, it is better to use a generator and not join at all.
  3. You can choose how many splits to do. It is much faster to do one split than an arbitrary number as you do. It is faster still to use partition, which always does only one split.
  4. If you are reading the buffer in, again it would be better to iterate over the lines rather than reading the whole thing in at once and splitting.

So, using your code, assuming we need a buffer in and out, this would be a much more efficient approach:

def remove_comments(buffer):     lines = buffer.splitlines()     return '\n'.join(line.partition('--')[0] for line in lines) 

However, for example, lets say you want to read a file in, remove comments, then save it again. This would be a far, far more efficient approach:

with open(infile, 'r') as fin, open(outfile, 'w') as fout:     for line in infile:         newline = line.partition('--')[0]         outfile.write(newline+'\n') 

Or better yet:

with open(infile, 'r') as fin, open(outfile, 'w') as fout:     outfile.writelines(line.partition('--')[0]+'\n' for line in infile) 

They key point to these two approaches is that they only ever keep one line in memory at a time, which saves on memory enormously.

Or, if you want to do some other manipulation on the lines before saving, you could do something like this:

with open(infile, 'r') as fin, open(outfile, 'w') as fout:    newlines1 = (line.partition('--')[0] for line in infile)    newlines2 = (myfunc1(line) for line in newlines1)    newlines3 = (myfunc2(line) for line in newlines2)    fout.writelines(line+'\n' for line in newlines3) 

In this case, mfunc1 and myfunc2 are functions that take a single string and return a single string. This approach will apply each operation to each line, but will only ever have one line in memory at a time.

It doesn't really matter what you ultimately do with the lines. You cold convert them to numbers or lists of numbers and do some calculation on them, send them over a network to another machine, or whatever. The point is that by doing it using generators, iterators, and generator expressions, you can save on memory and increase performance by a lot because it only ever has one line in memory at a time.

 
 
 
 
1
 
vote

Use Únete a :

  def remove_comments(buffer):     return ' '.join([line.split('--')[0] for line in buffer.split(' ')])   

No estoy seguro de cuánta mejora ofrecerá esto, ya que no puedo probarlo ahora, pero cualquier programador de Python serio recomendará 99887766655443310 cuando se trata de una concatenación de cadenas.

es tentador solo suministrar ' '.join1 con un generador en lugar de una lista, pero el hecho es que la unión todavía creará esta lista internamente, lo que realmente resulta ser más lento que suministrarlo con una lista . Puedes probar esto tú mismo

Algunos tiempos ( archivo de entrada ):

  ' '.join2  

Script de tiempo:

  ' '.join3  
 

Use join:

def remove_comments(buffer):     return '\n'.join([line.split('--')[0] for line in buffer.split('\n')]) 

I'm not sure how much improvement this will offer as I can't test it now, but any serious python programmer will recommend join when it comes to string concatenation.

It is tempting to just supply join with a generator rather than a list, but the fact is that join will still created this list internally which actually turns out to be slower than supplying it with a list. You can test this yourself

Some timings (input file):

rc1 function; best of 10: 6.823 ms rc2 function; best of 10: 18.241 ms rc3 function; best of 10: 4.757 ms rc4 function; best of 10: 7.715 ms rc5 function; best of 10: 5.883 ms 

Timing script:

import re import sys import time   def timing(func, repeat=10):   def wrapper(*args, **kwargs):     best = float('inf')      for k in xrange(repeat):         start = time.time()         func(*args, **kwargs)         end = time.time()          best = min(best, (end - start) * 1000.0)         time.sleep(0.1)      print ('%s function; best of %d: %0.3f ms' % (func.func_name, repeat, (end - start) * 1000.0))   return wrapper  @timing def rc1(buffer):     return '\n'.join([line.split('--')[0] for line in buffer.split('\n')])  @timing def rc2(buffer):     lines = buffer.splitlines()     return '\n'.join(line.partition('--')[0] for line in lines)  @timing def rc3(buffer):     return re.sub(r'--[^\n]*', '', buffer)  @timing def rc4(s):   chunks = []   offset = 0   for m in re.finditer("--.*\n", s):     chunks.append( s[offset: m.start(0)] )     offset = m.end(0)-1   chunks.append( s[offset:] )   return "".join(chunks)  @timing def rc5(s):   return re.sub('(?m)--.*$', '', s)    if __name__ == '__main__':     with open(sys.argv[1], 'r') as f:         buffer = f.read()      for f in [rc1, rc2, rc3, rc4, rc5]:         f(buffer)         time.sleep(1) 
 
 
         
         

Relacionados problema

4  Atomas Clone en Python  ( Atomas clone in python ) 
Aquí está mi clon de mierda de atomas , un juego de rompecabezas donde combina pequeños átomos en otros más valiosos. 9988776655544337 ¿Hay algún códig...

6  Comprobando una cuadrícula de palabras  ( Checking a word grid ) 
Escribí este programa donde puede ingresar x cantidad de palabras que de longitud x que comprueba si la cuadrícula se formó son las mismas palabras vertic...

4  Uso eficiente de la expresión regular y la manipulación de cadenas  ( Efficient use of regular expression and string manipulation ) 
La siguiente es mi solución a java vs c ++ . Creo que la forma en que he usado, la biblioteca de RE es ineficiente, y es posible erróneas, ya que estoy obten...

3  Seleccione Quick - Shuffle para hacer una clasificación más rápida  ( Quick select shuffle to make sorting faster ) 
Estoy tratando de usar el shuffle para mejorar el peor caso del escenario de selección rápida (por ejemplo, cada vez, el valor de pivote seleccionado es el má...

6  Valores coincidentes de la tabla HTML para actualizar los valores en Pandas DataFrame  ( Matching values from html table for updating values in pandas dataframe ) 
Esto es más un ejercicio para que me utilice a Pandas y sus cuadros de datos. Para aquellos que no escucharon de él: Panda es un paquete de Python que prop...

3  Usuario rápido para algunos números, luego imprime el máximo y min  ( Prompt user for some numbers then print the max and min ) 
La función de este programa está solicitando repetidamente a un usuario para números enteros hasta que el usuario ingrese en 'done' . Una vez que se ingresa ...

1  Una clase con un puntero de función en lugar de un generador  ( A class with a function pointer instead of a generator ) 
Estoy construyendo archivos Tikz, un PDF para cada imagen que tengo. El propósito es agregar texto a cada uno por separado. Las imágenes son LEGION, así que c...

2  Dos formas de aleatorias aleatoriamente las tarjetas  ( Two ways to randomly shuffle cards ) 
Aquí hay dos implementaciones que escribí para aleatorizar las tarjetas. El primer método ( dt5 ) Selecciona una tarjeta aleatoria, luego lo quita al frent...

1  Foldify - Una herramienta de carpeta de Python Tree Tree  ( Foldify a python folder tree manager tool ) 
El objetivo era crear una herramienta para ayudar a administrar las estructuras de las carpetas y permitirme crear plantillas de estas carpetas y almacenarlas...

10  Protocolo de red usando TCP, enviando imágenes a través de sockets  ( Network protocol using tcp sending images through sockets ) 
Me gustaría preguntar sobre su opinión sobre mi código. La idea es simple: diseñé mi propio protocolo, donde el cliente le pregunta al servidor sobre la image...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos