Каков самый быстрый способ проверить, содержит ли строка повторяющиеся символы в Python 3?

Question

Мне нужно отфильтровать строки по критерию, чтобы они не содержали символ дважды.

• Струны многие (скажем 1400000000000).
• Строки короткие (около 8 символов).
• Строки уникальные (кеширование не работает).
• Строки имеют большой набор символов (скажем любой символ Юникода).
• Строки обычно соответствуют критерию (скажем, 2/3 не имеют повторяющихся символов).

используя код будет выглядеть следующим образом:

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

Я реализовал наивную версию, просто итерацию строки:

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 

Моей следующей-лучшая идея была использовать set, поэтому я внедрил это:

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)) 

Сохранения функции в файл UniqueCharacters.py, приуроченных их:

$ 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 

Это показывает, что unique_chars_set быстрее примерно 15% для этого набора данных.

Есть ли более быстрый способ сделать это? Возможно, с регулярными выражениями? Есть ли какой-нибудь метод в стандартной библиотеке, который это делает?

Answer 1

Позвольте мне начать с того, что я подозреваю, что вы оптимизируете, когда вам это не нужно. Python - это язык высокого уровня, который поддерживает мышление о вычислении на высоком уровне. Решение, которое является читаемым, элегантным и многоразовым, часто будет лучше, чем тот, который невероятно быстро, но трудно понять.

Когда, и только, когда вы определяете, что скорость является проблемой, тогда вы должны приступить к оптимизации. Возможно, даже напишите расширение C для вычислительно интенсивных частей.

Это, как говорится, вот сравнение нескольких методов:

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 

А вот сравнение производительности (в 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 

Заключение: set элегантна и быстрее, чем многие другие очевидные методы. Но различия настолько малы, что это не имеет значения.

Для получения дополнительной информации см. Ответ @FrancisAvila.

Answer 2

Вы можете отсортировать строку и перебрать ее, чтобы увидеть, нет ли последовательных одинаковых букв, но это N * log (N), поэтому я не уверен, что это будет быстрее, чем установленное решение.

Answer 3

См. bucket sort, хотя это алгоритм сортировки, в котором вы можете основывать свое решение, в основном вы определяете массив из n позиций, и для каждого символа вы помещаете его в массив в позиции, заданной его значением ASCII или UNICODE (см. Ниже для unicode), у вас будет сложность времени O (n) в каждой итерации максимум (вы можете сломать, когда позиция в массиве уже используется) ... но я думаю, вы не найдете значительной разницы в любом методе, учитывая, что вы можете просто проверить сначала if(string.length < 255) или что-то еще количество допустимых значений в строке.

Это проверить гарантирует, что любой цикл будет самым более 255 символов, которые делают их маленькими достаточно малы, чтобы иметь заботы о производительности в большинстве случаев

(я не знаю, питона, но я уверен, некоторые string.length собственности или эквивалент)

Как отметил @John, если вам необходимо поддерживать большой или все возможные значения строки, то это вызовет проблемы как с пространством и временем

Answer 4

мне делать, если не будет знать быть быстрее, но это регулярное выражение может удовлетворить вас:

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

Answer 5

Я создал файл с синхронизацией и испытательным упряжьем, чтобы попробовать целую кучу разных подходов.

Самый быстрый из них, который я нашел, основан на регулярном выражении, но он только немного быстрее, чем ваш самый быстрый подход len(set()). Ниже приведена функция isunique_reg().

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() 

На CPython 2.7.1 я получаю следующие результаты (к сожалению, я не имею CPython 3.x под рукой):

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 

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