Python script to insert space between different character types: Why is this *so* slow?

Question

I'm working with some text that has a mix of languages, which I've already done some processing on and is in the form a list of single characters (called "letters"). I can tell which language each character is by simply testing if it has case or not (with a small function called "test_lang"). I then want to insert a space between characters of different types, so I don't have any words that are a mix of character types. At the same time, I want to insert a space between words and punctuation (which I defined in a list called "punc"). I wrote a script that does this in a very straight-forward way that made sense to me (below), but apparently is the wrong way to do it, because it is incredibly slow.

Can anyone tell me what the better way to do this is?

# Add a space between Arabic/foreign mixes, and between words and punc
cleaned = ""
i = 0
while i <= len(letters)-2: #range excludes last letter to avoid Out of Range error for i+1
    cleaned += letters[i]
    # words that have case are Latin; otherwise Arabic
    if test_lang(letters[i]) != test_lang(letters[i+1]):
        cleaned += " "
    if letters[i] in punc or letters[i+1] in punc:
        cleaned += " "
    i += 1
cleaned += letters[len(letters)-1] # add in last letter

Answer 1

There are a few things going on here:

• You call test_lang() on every letter in the string twice, this is probably the main reason this is slow.
• Concatenating strings in Python isn't very efficient, you should instead use a list or generator and then use str.join() (most likely, ''.join()).

Here is the approach I would take, using itertools.groupby():

from itertools import groupby
def keyfunc(letter):
    return (test_lang(letter), letter in punc)

cleaned = ' '.join(''.join(g) for k, g in groupby(letters, keyfunc))

This will group the letters into consecutive letters of the same language and whether or not they are punctuation, then ''.join(g) converts each group back into a string, then ' '.join() combines these strings adding a space between each string.

Also, as noted in comments by DSM, make sure that punc is a set.

Answer 2

Every time you perform a string concatenation, a new string is created. The longer the string gets, the longer each concatenation takes.

http://en.wikipedia.org/wiki/Schlemiel_the_Painter's_algorithm

You might be better off declaring a list big enough to store the characters of the output, and joining them at the end.

Answer 3

I suggest an entirely different solution that should be very fast:

import re
cleaned = re.sub(r"(?<!\s)\b(?!\s)", " ", letters, flags=re.LOCALE)

This inserts a space at every word boundary (defining words as "sequences of alphanumeric characters, including accented characters in your current locale", which should work in most cases), unless it's a word boundary next to whitespace.

This should split between Latin and Arabic characters as well as between Latin and punctuation.

Answer 4

Assuming test_lang is not the bottleneck, I'd try:

''.join(
    x + ' '
    if x in punc or y in punc or test_lang(x) != test_lang(y)
    else x
    for x, y in zip(letters[:-1], letters[1:])
)

Answer 5

Here is a solution that uses yield. I would be interested to know whether this runs any faster than your original solution.

This avoids all the indexing in the original. It just iterates through the input, holding onto a single previous character.

This should be easy to modify if your requirements change in the future.

ch_sep = ' '

def _sep_chars_by_lang(s_input):
    itr = iter(s_input)
    ch_prev = next(itr)

    yield ch_prev

    while True:
        ch = next(itr)
        if test_lang(ch_prev) != test_lang(ch) or ch_prev in punc:
            yield ch_sep
        yield ch
        ch_prev = ch

def sep_chars_by_lang(s_input):
    return ''.join(_sep_chars_by_lang(s_input))

Answer 6

Keeping the basic logic of the OP's original code, we speed it up by not doing all that [i] and [i+1] indexing. We use a prev and next reference that scan through the string, maintaining prev one character behind next:

# Add a space between Arabic/foreign mixes, and between words and punc
cleaned = ''
prev = letters[0]
for next in letters[1:]:
    cleaned += prev
    if test_lang(prev) != test_lang(next):
        cleaned += ' '
    if prev in punc or next in punc:
        cleaned += ' '
    prev = next
cleaned += next

Testing on a string of 10 million characters shows this is about twice the speed of the OP code. The "string concatenation is slow" complaint is obsolete, as others have pointed out. Running the test again using the ''.join(...) metaphor shows a slighly slower execution than using string concatenation.

Further speedup may come through not calling the test_lang() function but by inlining some simple code. Can't comment as I don't really know what test_lang() does :).

Edit: removed a 'return' statement that should not have been there (testing remnant!).

Edit: Could also speedup by not calling test_lang() twice on the same character (on next in one loop and then prev in the following loop). Cache the test_lang(next) result.