ansaurus

Question

Fastest implementation to do multiple string substitutions in Python

Answer 1

A:

How fast? Also, how big are your strings?

There's a fairly simple recipe for building a regular expression to do the job on another site. It might need some tweaking to handle regex metacharacters; I didn't look too closely.

If that's not good enough, you probably need to write some C code, honestly. You can build a simple state machine to do all the replacements, and then process any string byte by byte with no backtracking along the machine to actually do the work. However, I doubt you will beat the regex engine without going to C and optimizing that.

Walter Mundt 2010-08-05 01:02:06

"How fast?" - at least faster than the replace chaining method above. "how big" - up to what the system RAM allows minus memory space that would be used by the 'function'. I'm not talking about some gigantic string of, say, 4GiB size.

OTZ 2010-08-05 01:07:50

Based on my experiment with 3.5M size of a string with 5 substitution pairs, the regular expression method *always* performs worse (1.285878 sec vs 1.341442 sec), even with the caching of the resultant re object. If I increase the number of substitution pairs, the situation could be reversed. But under normal condition, it just doesn't happen. So the linear regular expression method in the recipe in this case is not usable. My tests were againt a more efficient version of it, actually.

OTZ 2010-08-05 02:34:08

Yeah, that method is not so great. With any luck we'll see a better answer soon. If not, I may see if implementing a state machine on top of the Python buffer interface works any better.

Walter Mundt 2010-08-05 03:50:25

Answer 2

+2 A:

Something like the following maybe? Split the text into pieces with the first "from" item to be replaced, then recursively split each of those parts into sub-parts with the next "from" item to be replaced, and so on, until you've visited all your replacements. Then join with the "to" replacement item for each as recursive function completes.

A little hard to wrap your head around the following code perhaps (it was for me, and I wrote it), but it seems to function as intended. I didn't benchmark it, but I suspect it would be reasonably fast.

def multi_replace(pairs, text):
    stack = list(pairs)
    stack.reverse()
    def replace(stack, parts):
        if not stack:
            return parts
        # copy the stack so I don't disturb parallel recursions
        stack = list(stack) 
        from_, to = stack.pop()
        #print 'split (%r=>%r)' % (from_, to), parts
        split_parts = [replace(stack, part.split(from_)) for part in parts]
        parts = [to.join(split_subparts) for split_subparts in split_parts]
        #print 'join (%r=>%r)' % (from_, to), parts
        return parts
    return replace(stack, [text])[0]


print multi_replace(
    [('foo', 'bar'), ('baaz', 'foo'), ('quux', 'moop')], 
    'foobarbaazfooquuxquux')

for:

barbarfoobarmoopmoop

Matt Anderson 2010-08-05 05:26:02

Matt, thanks for the function. It beats multiple 'replace' method on a large string :) 'replace' method is still faster on a smaller string though (strings < 1M or so). I've added my test results to my original question. You might want to check it out.

OTZ 2010-08-05 06:58:16

Answer 3

A:

Normally, .replace method beats all other methods. (See my benchmarks above.)

OTZ 2010-08-30 10:14:05

ansaurus

tags:

views:

answers:

Fastest implementation to do multiple string substitutions in Python

related questions