schnellste Art und Weise zusammenhängende Zeichen in Zeichenfolge dedupliziert Python

Question

Wir können die zusammenhängenden Zeichen in einer Zeichenfolge mit Deduplizierung

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

Auf der Kommandozeile gibt es eine Option für squeezetr:

$ tr -s " " < file 

Gibt es eine squeeze Funktion in Python-String?

Was ist der schnellste Weg zur Deduplizierung zusammenhängender Zeichen in einer Zeichenfolge in Python?

Bitte beachten Sie, dass das zu deduplizierende Zeichen ein Ascii/Unicode-Zeichen und nicht nur \s/Leerzeichen sein sollte. (Es ist in Ordnung 2 Unter Antworten für ASCII- und Unicode zu haben.

Answer 1

Zunächst einmal zu versuchen, Ihre deduplicate Funktion ist wirklich wirklich schnell. Aber es kann einige Verbesserungen sein . gemacht, um es noch schneller zu machen habe ich lambda ized Ihre Funktion und nannte es (unten) org_deduplicate nun für einige Zeit Tests (ipython des %timeit verwenden).

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 

aber die strip ist wirklich nicht notwendig und kann Sie auch zu unerwarteten Ergebnissen führen (wenn Sie nicht Leerzeichen Deduplizierung werden), so können wir versuchen:

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 

die Dinge durch ein kleines bisschen, aber es ist nicht so beeindruckend beschleunigt. Lass uns einen anderen Ansatz ausprobieren ... reguläre Ausdrücke. Diese sind auch schön, denn sie geben Ihnen die Flexibilität, jeden regulären Ausdruck als „Zeichen“ wählen dedupliziert (und nicht nur ein einzelnes Zeichen):

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 

Die zweiten ist schneller, aber weder sind noch nah an Ihrem ursprünglichen Funktion. Es sieht so aus, als wären normale String-Operationen schneller als re Funktionen. Was passiert, wenn wir stattdessen versuchen zippen (itertools.izip verwenden, wenn mit Python 2 Arbeits):

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 

immer noch keine Besserung. Die Zip-Methode macht zu viele Teilstrings, wodurch ''.join langsam gemacht wird. Ok noch einen Versuch ... was str.replace rekursiv aufgerufen:

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 

Nicht schlecht, dass unsere Gewinner zu sein scheint. Aber nur um sicher zu sein, kann versuchen, es gegen unsere ursprüngliche Funktion mit einem wirklich langen Eingabestring:

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 

Yup, es sieht aus wie es schön skaliert. Aber lassen Sie uns einen weiteren Test versuchen: Der rekursive Deduplizierer entfernt bei jedem Aufruf nur doppelte Zeichen der Länge 2.So macht es noch besser mit langen doppelten Zeichen:

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 

Es verliert einen Teil seines Vorteils, wenn es lange Ketten von wiederholten Zeichen zu entfernen.

Zusammenfassend, verwenden Sie Ihre ursprüngliche Funktion (mit ein paar Optimierungen), wenn Ihre Strings lange Teilstrings von sich wiederholenden Zeichen haben. Andernfalls ist die rekursive Version am schnellsten.

Answer 2

itertools sind eine gute lib

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