Qual è il modo più veloce per verificare se una stringa contiene caratteri ripetuti in Python 3?

Question

Devo filtrare le stringhe in base al criterio che non contengano il carattere due volte.

• Le stringhe sono molti (diciamo 1.400 miliardi).
• Le stringhe sono breve (circa 8 caratteri).
• Le stringhe sono univoche (il caching non funzionerà).
• Le stringhe hanno un set di caratteri grandi (ad esempio qualsiasi carattere Unicode).
• Le stringhe di solito soddisfano il criterio (ad esempio 2/3 non hanno caratteri ripetuti).

Il codice usando sarebbe simile a questa:

>>> candidate_strings = ["foobnehg", "barfnehg", "bazfnehg"] 
>>> result_strings = [s if unique_chars(s) for s in candidate_strings] 
>>> print(result_strings) 
["barfnehg", "bazfnehg"] 

ho implementato una versione ingenua, semplicemente scorrendo la stringa:

def unique_chars_naive(string_given): 
    """ 
    Checks if a given string contains only unique characters. 
    This version iterates the given string, saving all occurred characters. 
    """ 
    chars_seen = [] 
    for char in string_given: 
     if char in chars_seen: 
      return False 
     chars_seen.append(char) 
    return True 

Il mio prossimo best-idea era quella di utilizzare un set, quindi l'ho implementato:

def unique_chars_set(string_given): 
    """ 
    Checks if a given string contains only unique characters. 
    This version exploits that a set contains only unique entries. 
    """ 
    return len(string_given) == len(set(string_given)) 

Salvataggio delle funzioni in un file UniqueCharacters.py, li cronometrato:

$ python3 -m timeit -n 100000 --setup='import UniqueCharacters; candidate_strings = ["foobnehg", "barfnehg", "bazfnehg"]' '[UniqueCharacters.unique_chars_naive(s) for s in candidate_strings]' 
100000 loops, best of 3: 20.3 usec per loop 

$ python3 -m timeit -n 100000 --setup='import UniqueCharacters; candidate_strings = ["foobnehg", "barfnehg", "bazfnehg"]' '[UniqueCharacters.unique_chars_set(s) for s in candidate_strings]' 
100000 loops, best of 3: 17.7 usec per loop 

Questo dimostra che il unique_chars_set è più veloce di circa il 15% di questo insieme di dati.

C'è un modo più veloce per farlo? Con le espressioni regolari forse? C'è qualche metodo nella libreria standard che lo fa?

Answer 1

Lasciatemi dire che sospetto che tu stia ottimizzando quando non ne hai bisogno. Python è un linguaggio di alto livello che supporta il pensiero sulla computazione in un modo di alto livello. Una soluzione leggibile, elegante e riutilizzabile è spesso migliore di una che è incredibilmente veloce, ma difficile da capire.

Quando, e solo quando si determina che la velocità è un problema, è necessario procedere con le ottimizzazioni. Forse anche scrivere un'estensione C per le parti computazionalmente intense.

Detto questo, ecco un confronto tra alcune tecniche:

def unique_chars_set(s): 
    return len(s) == len(set(s)) 

def unique_chars_frozenset(s): 
    return len(s) == len(frozenset(s)) 

def unique_chars_counter(s): 
    return Counter(s).most_common(1)[0][1] > 1 

def unique_chars_sort(s): 
    ss = ''.join(sorted(s)) 
    prev = '' 
    for c in ss: 
     if c == prev: 
      return False 
     prev = c 
    return True 

def unique_chars_bucket(s): 
    buckets = 255 * [False] 
    for c in s: 
     o = ord(c) 
     if buckets[o]: 
      return False 
     buckets[o] = True 
    return True 

Ed ecco il confronto delle prestazioni (in IPython):

In [0]: %timeit -r10 [unique_chars_set(s) for s in candidate_strings] 
100000 loops, best of 10: 6.63 us per loop 

In [1]: %timeit -r10 [unique_chars_frozenset(s) for s in candidate_strings] 
100000 loops, best of 10: 6.81 us per loop 

In [2]: %timeit -r10 [unique_chars_counter(s) for s in candidate_strings] 
10000 loops, best of 10: 83.1 us per loop 

In [3]: %timeit -r10 [unique_chars_sort(s) for s in candidate_strings] 
100000 loops, best of 10: 13.1 us per loop 

In [4]: %timeit -r10 [unique_chars_bucket(s) for s in candidate_strings] 
100000 loops, best of 10: 15 us per loop 

Conclusione: set è elegante e più veloce di molti altri metodi ovvi. Ma le differenze sono così piccole, non importa comunque.

Per ulteriori benchmark, vedere la risposta di @FrancisAvila.

Answer 2

Si può ordinare la stringa e iterarla per vedere se non ci sono le stesse lettere consecutive, ma questo è N * log (N) quindi non sono sicuro che sarà più veloce della soluzione impostata.

Answer 3

Vedere bucket sort Vedere un algoritmo di ordinamento è possibile basare la soluzione in questo, in pratica si definisce un array di n posizioni e per ogni carattere lo si posiziona nell'array sulla posizione data dal relativo valore ASCII o UNICODE (vedere di seguito per unicode), si avrà O (n) complessità temporale in ogni iterazione al massimo (si può interrompere quando una posizione nell'array è già utilizzata) ... ma penso che non si troverà una differenza considerevole in nessuno dei due metodi dato che puoi semplicemente verificare al primo if(string.length < 255) o qualunque sia il numero di possibili valori validi nella stringa.

che il check assicura che ogni ciclo sarà al massimo di oltre 255 caratteri, che li rendono piccoli abbastanza piccolo da avere preoccupazioni per le prestazioni nella maggior parte dei casi

(non so python, ma sono sicuro che ci è un po 'string.length proprietà o equivalente)

Come menzionato da @JOHN, se avete bisogno di supportare un grande o tutti i possibili valori di stringa allora questo causerà problemi di spazio e tempo

Answer 4

non so se la volontà essere più veloce, ma questa espressione regolare potrebbe soddisfarti:

couplet = re.compile(r'(.).*\1') 
result_strings = [s if not re.search(couplet, s) for s in candidate_strings] 

Answer 5

Ho creato un file con una sincronizzazione e un cablaggio di prova per provare un sacco di approcci diversi.

Il più veloce che ho trovato è basato su regex, ma è solo un pochino più veloce rispetto al più veloce approccio basato su len(set()). È la funzione isunique_reg() qui sotto.

import re 
import array 
import collections 
import bisect 

re_dup_g = re.compile(r'(.).*\1', re.DOTALL) 
re_dup_ng = re.compile(r'(.).*?\1', re.DOTALL) 


def isunique_reg(s, search=re_dup_g.search): 
    return search(s) is None 

def isunique_reng(s, search=re_dup_ng.search): 
    return search(s) is None 

def isunique_set(s, set=set, len=len): 
    return len(s) == len(set(s)) 

def isunique_forset(s, set=set): 
    seen = set() 
    add = seen.add 
    for c in s: 
     if c in seen: 
      return False 
     add(c) 
    return True 

def isunique_array(s, array=array.array): 
    seen = array('u') 
    append = seen.append 
    for c in s: 
     if c in seen: 
      return False 
     append(c) 
    return True 

def isunique_deque(s, deque=collections.deque): 
    seen = deque() 
    append = seen.append 
    for c in s: 
     if c in seen: 
      return False 
     append(c) 
    return True 

def isunique_bisect(s, find=bisect.bisect_right, array=array.array): 
    seen = array('u') 
    insert = seen.insert 
    for c in s: 
     i = find(seen, c) 
     if i and seen[i-1] == c: 
      return False 
     insert(i, c) 
    return True 

def isunique_bisectl(s, find=bisect.bisect_right): 
    seen = [] 
    insert = seen.insert 
    for c in s: 
     i = find(seen, c) 
     if i and seen[i-1] == c: 
      return False 
     insert(i, c) 
    return True 

def isunique_count(s, Counter=collections.Counter): 
    return Counter(s).most_common(1)[0][1]==1 

def isunique_list(s): 
    seen = [] 
    append = seen.append 
    for c in s: 
     if c in seen: 
      return False 
     append(c) 
    return True 


def _test(): 
    funcs = [f for n,f in globals().items() if n.startswith('isunique_')] 
    cases = [ 
     (u'string given', False), 
     (u'string uoqzd', True), 
    ] 
    for func in funcs: 
     for s,rv in cases: 
      try: 
       assert rv is func(s) 
      except AssertionError, e: 
       print "%s(%r) is not %r" % (func.__name__, s, rv) 
       raise e 

def _time(): 
    import timeit 
    funcs = [f for n,f in globals().items() if n.startswith('isunique_')] 
    funcs.sort(key=lambda f: f.__name__) 
    cases = [ 
     ('!uniq', u'string given', False), 
     ('uniq', u'string uoqzd', True), 
    ] 

    casenames = [name for name, _, _ in cases] 
    fwidth = max(len(f.__name__) for f in funcs) 
    timeitsetup = 's = {!r}; from __main__ import {} as u' 

    print('{: <{fwidth}s}|{: >15s}|{: >15s}'.format('func', *casenames, fwidth=fwidth)) 
    print('-'*(fwidth+2+15+15)) 
    for f in funcs: 
     times = [timeit.timeit('u(s)', setup=timeitsetup.format(input, f.__name__)) for _, input, _ in cases] 
     print('{: <{fwidth}s}|{: >15.10f}|{: >15.10f}'.format(f.__name__, *times, fwidth=fwidth)) 

if __name__=='__main__': 
    _test() 
    _time() 

Su CPython 2.7.1 I ottenere i seguenti risultati (purtroppo non hanno una 3.x CPython a portata di mano):

func   |   !uniq|   uniq 
------------------------------------------------ 
isunique_array | 6.0237820148| 11.0871050358 
isunique_bisect | 10.8665719032| 18.4178640842 
isunique_bisectl| 8.2648131847| 13.9763219357 
isunique_count | 23.1477651596| 23.5043439865 
isunique_deque | 4.0739829540| 7.3630020618 
isunique_forset | 2.8148539066| 4.1761989594 
isunique_list | 3.6703650951| 6.9271368980 
isunique_reg | 1.7293550968| 2.8794138432 
isunique_reng | 1.9672849178| 3.3768401146 
isunique_set | 2.3157420158| 2.2436211109 

Noterete che quando una stringa non è unico , l'approccio basato su regex è più veloce di quello basato su set, ma il caso peggiore per l'approccio basato su regex è più lento rispetto agli insiemi.