检查字符串是否包含Python 3中的重复字符的最快方法是什么？

Question

我需要按照它们不包含两次字符的标准来过滤字符串.

• 字符串很多(比如1.4万亿).
• 字符串很短(大约8个字符).
• 字符串是唯一的(缓存不起作用).
• 字符串有一个很大的字符集(比如任何Unicode字符).
• 字符串通常符合标准(例如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

我的下一个最好的想法是使用a 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的回答.