在字符串Python中消除连续字符的最快方法

Question

我们可以使用以下方法消除字符串中的连续字符：

def deduplicate(string, char):
    return char.join([substring for substring in string.strip().split(char) if substring])

例如

^{pr2}$

在命令行上，tr有一个squeeze选项：

$ tr -s " " < file

在Python的字符串中有squeeze函数吗？

在Python中消除字符串中连续字符的最快方法是什么？

请注意，要消除重复的字符应该是任何ascii/unicode字符，而不仅仅是\s/空白。（对于ascii和unicode有两个子答案是很好的。在

Answer 1

Itertools是一个很好的lib

>>> t = "THHHISSS ISSS BBBBSSSSS"
>>> import itertools
>>> ''.join(char for char, _ in itertools.groupby(t))
'THIS IS BS'

Answer 2

首先，您的deduplicate函数实际上非常快。但也有一些改进可以使它更快。我已经lambda对您的函数进行了org_deduplicate（如下所示）。现在进行一些时间测试（使用iPython的%timeit）：

s = 'this is   an   irritating string with  random spacing  .'

org_deduplicate = lambda s,c: c.join([substring for substring in s.strip().split(c) if substring])

%timeit org_deduplicate(s,' ')
100000 loops, best of 3: 3.59 µs per loop

但是strip确实没有必要，甚至可能会给您带来意想不到的结果（如果您没有对空白进行重复数据消除），因此我们可以尝试：

^{pr2}$

它使事情加快了一点点，但并不那么令人印象深刻。让我们尝试另一种方法。。。正则表达式。它们也很不错，因为它们使您能够灵活地选择任何正则表达式作为重复数据消除的“字符”（而不仅仅是一个字符）：

import re

re_deduplicate = lambda s,c: re.sub(r'(%s)(?:\1)+' %c, '\g<1>',  s)
re_deduplicate2 = lambda s,c: c.join(re.split('%s+'%c,s))

%timeit re_deduplicate(s,' ')
100000 loops, best of 3: 13.8 µs per loop

%timeit re_deduplicate2(s,' ')
100000 loops, best of 3: 6.47 µs per loop

第二个更快，但都不接近您原来的功能。看起来常规的字符串操作比re函数快。如果我们改为尝试压缩（如果使用python2，请使用itertools.izip），会怎么样：

zip_deduplicate = lambda s,c: ''.join(s1 for s1,s2 in zip(s,s[1:]) if s1!=c or s1!=s2)

%timeit zip_deduplicate(s,' ')
100000 loops, best of 3: 12.9 µs per loop

仍然没有改善。zip方法生成太多的子字符串，这使得执行''.join的速度变慢。好吧，再试一次。。。递归调用str.replace怎么样：

def rec_deduplicate(s,c):                                                                             
    if s.find(c*2) != -1:   
        return rec_deduplicate(s.replace(c*2, c),c)
    return s

%timeit rec_deduplicate(s,' ')
100000 loops, best of 3: 2.83 µs per loop

不错，这似乎是我们的赢家。但为了确定，让我们用一个非常长的输入字符串来对照原始函数：

s2 = s*100000

%timeit rec_deduplicate(s2,' ')
10 loops, best of 3: 64.6 ms per loop

%timeit org_deduplicate(s2,' ')
1 loop, best of 3: 209 ms per loop

是的，看起来它的比例很好。但是让我们再试一次测试，递归重复数据消除器每次调用时只删除长度为2的重复字符。那么，长重复字符是否仍然更好：

s3 = 'this is                       an                        irritating string with                                  random spacing  .'

%timeit rec_deduplicate(s3,' ')
100000 loops, best of 3: 9.93 µs per loop

%timeit org_deduplicate(s3,' ')
100000 loops, best of 3: 8.99 µs per loop

当需要删除长串重复字符时，它确实会失去一些优势。在

总之，如果字符串将有长的重复字符子字符串，请使用原始函数（可能会进行一些调整）。否则，递归版本最快。在