11

我需要根据字符串两次不包含字符的标准来过滤字符串。

  • 字符串很多（比如 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%。

有没有更快的方法来做到这一点？也许用正则表达式？标准库中是否有一些方法可以做到这一点？

4

5 回答 5

14

让我首先说我怀疑您在不需要时正在优化。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的答案。

于 2013-04-01T20:50:44.567 回答
4

我创建了一个带有计时和测试工具的文件，以尝试各种不同的方法。

我发现的最快的是基于正则表达式的，但它只比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

您会注意到，当字符串不是唯一的时，基于正则表达式的方法比基于集合的方法快，但基于正则表达式的方法的最坏情况比集合慢。

于 2013-04-01T20:51:17.027 回答
1

我不知道是否会更快，但这个正则表达式可能会让你满意：

couplet = re.compile(r'(.).*\1')
result_strings = [s if not re.search(couplet, s) for s in candidate_strings]
于 2013-04-01T20:26:37.533 回答
0

您可以对字符串进行排序并对其进行迭代以查看是否没有连续的相同字母，但这是 N*log(N) 所以我不确定这是否会比设置的解决方案更快。

于 2013-04-01T20:17:17.590 回答
0

请参阅桶排序，尽管它是一种排序算法，您可以将解决方案作为基础，基本上您定义一个 n 位置的数组，并且对于每个字符，您将其放置在数组中由其 ASCII 或 UNICODE 值给出的位置上（参见下面的 unicode），每次迭代最多会有 O(n) 时间复杂度（当数组中的某个位置已经被使用时，你可以中断）......但我认为你不会在任何一种方法中找到相当大的差异，因为你可以简单地首先检查if(string.length < 255)字符串中可能的有效值的数量。

该检查可确保任何循环最多超过 255 个字符，这使得它们足够小，可以在大多数情况下担心性能

（我不知道python，但我确定有一些string.length属性或等价物）

正如@JOHN 所提到的，如果您需要支持一个大的或所有可能的字符串值，那么这将导致空间和时间问题

于 2013-04-01T20:22:38.383 回答