string - 在 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

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