быстрый способ дедупликации смежных символов в строке - Python

Question

Мы можем дедуплицировать смежных символов в строке с:

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

Э.Г.

>>> s = 'this is an irritating string with random spacing .' 
>>> deduplicate(s) 
'this is an irritating string with random spacing .' 

В командной строке есть squeeze вариант для tr:

$ tr -s " " < file 

Есть squeeze функции в строке Пайтона?

Каков самый быстрый способ дедупликации смежных символов в строке в Python?

Обратите внимание: символ, подлежащий дедупликации, должен быть любым символом ascii/unicode, а не только \s/пробелами. (Это хорошо, чтобы иметь 2 суб-ответы для ASCII и Юникода.

Answer 1

Прежде всего, ваша deduplicate функция на самом деле очень быстро. Но может быть некоторые улучшения ., чтобы сделать его еще быстрее я lambda роскопию вашей функции и назвал его org_deduplicate (ниже) Теперь какими-то время тестов (с использованием %timeit IPython в.):

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 действительно не является необходимым и может даже дать вам неожиданные результаты (если вы не дедуплицирующие пробелов), поэтому мы можем попробовать:

org_deduplicate2 = lambda s,c: c.join(substring for substring in s.split(c) if substring) 

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

который ускоряет вещи по чуть-чуть, но это не все, что впечатляет. Давайте попробуем другой подход ... регулярные выражения. Они также хороши, потому что они дают вам возможность выбрать любое регулярное выражение в качестве «символа» в Дедуплицировать (а не только один символ):

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. Что делать, если мы пытаемся сжать вместо (используйте itertools.izip при работе с Python 2):

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 

Она теряет часть своего преимущества, когда есть длинные строки повторяющихся символов, чтобы удалить.

Таким образом, используйте свою оригинальную функцию (возможно, с несколькими настройками), если ваши строки будут иметь длинные подстроки повторяющихся символов. В противном случае рекурсивная версия будет самой быстрой.

Answer 2

Itertools хороший Lib попробовать

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