I don't know how you time it but here is what I get:
import re import timeit def alfalfa(input_str=None, n=1000): if not input_str: string = 'it |BS||BS||BS|this is one|BS||BS||BS|an example'*n else: string = input_str while re.search("\|BS\|", string): array = list(string) for m in re.finditer("\|BS\|", string): del array[m.start():m.end()] if m.start()-1 >= 0: del array[m.start()-1] string = ''.join(array) break return string def buran1(input_str = None, n=1000): ptrn = re.compile(r'[\w ]?\|BS\|') if not input_str: string = 'it |BS||BS||BS|this is one|BS||BS||BS|an example'*n else: string = input_str while True: after_sub = ptrn.sub('', string, count=1) if string == after_sub: break else: string = after_sub return string def buran2(input_str=None, n=1000): ptrn = re.compile(r'(\|BS\|)+') if not input_str: string = 'it |BS||BS||BS|this is one|BS||BS||BS|an example'*n else: string = input_str while True: match = re.search(ptrn, string) if match: num_chars = min(match.start(), int(len(match.group())/4)) sub_pattern = re.compile(r'[\w ]{{{}}}(\|BS\|)+'.format(num_chars)) string = sub_pattern.sub('', string, count=1) else: break return string def noBS(s=None, n=1000): if not s: s = 'it |BS||BS||BS|this is one|BS||BS||BS|an example'*n else: s = s*n pattern=re.compile(r'.\|BS\|((\|BS\|)*)') previous='' while s!=previous: previous=s s=re.sub(pattern,r'\1',s) return s if __name__ == '__main__': print 'repeat 1000, short string:\n' print 'alfalfa --> {}'.format(timeit.timeit("alfalfa(n=1)", number=1000, setup="from __main__ import alfalfa")) print 'buran1 --> {}'.format(timeit.timeit("buran1(n=1)", number=1000, setup="from __main__ import buran1")) print 'buran2 --> {}'.format(timeit.timeit("buran2(n=1)", number=1000, setup="from __main__ import buran2")) print 'ofnut --> {}'.format(timeit.timeit("noBS(n=1)", number=1000, setup="from __main__ import noBS")) print '\nrepeat 1, long string\n' print 'alfalfa --> {}'.format(timeit.timeit("alfalfa()", number=1, setup="from __main__ import alfalfa")) print 'buran1 --> {}'.format(timeit.timeit("buran1()", number=1, setup="from __main__ import buran1")) print 'buran2 --> {}'.format(timeit.timeit("buran2()", number=1, setup="from __main__ import buran2")) print 'ofnut --> {}'.format(timeit.timeit("noBS()", number=1, setup="from __main__ import noBS"))and the result of two consecutive runs:
Output:repeat 1000, short string:
alfalfa --> 0.0432239843385
buran1 --> 0.0112259009714
buran2 --> 0.0158689890339
ofnut --> 0.0273017555023
repeat 1, long string
alfalfa --> 3.50733362241
buran1 --> 1.34837528801
buran2 --> 1.86298544437
ofnut --> 0.0084199068111
repeat 1000, short string:
alfalfa --> 0.0284217156815
buran1 --> 0.00996738901746
buran2 --> 0.0157894500521
ofnut --> 0.0273982927342
repeat 1, long string
alfalfa --> 3.52313333556
buran1 --> 1.35965603239
buran2 --> 1.82195551718
ofnut --> 0.00834742370672