Efficiently concatenate substrings of long list of strings

Question

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.

Answer 1

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(n²), 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)

Answer 2

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)

Answer 3

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.

Answer 4

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)