python - 高效查找字符串中重复的字符

Question

我知道这段代码的效率不是最优的(尤其是对于巨大的输入)，而且我知道有一种方法可以改变这个算法来处理其他数据类型而不仅仅是字符串中的重复(显然有要搜索的字符只有这么多)。

有什么办法可以提高效率吗？

我尝试使用字典，但该函数一直返回“无”，所以我尝试了一个列表，一切正常。

提前感谢任何可以帮助我的人!

def find_repeater(string):
    my_list = []
    my_list.append(string[0])

    for i in range (1, len(string)):

        if string[i] in my_list:
            print 'repetition found'
            return (string[i])

        else:
            my_list.append(string[i])

print find_repeater('abca')  

现在有了字典....(它一直在控制台打印“无”)

def find_repeater(string):
    my_dict = {}
    my_dict[0] = string[0]

    for i in range (1, len(string)):

        if string[i] in my_dict:
            print 'repetition found'
            return string[i]

        else:
            my_dict[i] = string[i]

print find_repeater('abca')  

Answer 1

由于这是一个性能问题，让我们做一些计时:

def test_set(xs):
    seen = set()  # O(1) lookups
    for x in xs:
        if x not in seen:
            seen.add(x)
        else:
            return x

import collections

def test_counter(xs):
    freq = collections.Counter(xs)
    for k in freq:
        if freq[k] > 1:
            return k

def test_dict(xs):
    d = {}
    for x in xs:
        if x in d:
            return x
        d[x] = 1

def test_sort(xs):
    ys = sorted(xs)

    for n in range(1, len(xs)):
        if ys[n] == ys[n-1]:
            return ys[n]

##

import sys, timeit
print (sys.version + "\n")
xs = list(range(10000)) + [999]
fns = [p for name, p in globals().items() if name.startswith('test')]
for fn in fns:
    assert fn(xs) == 999
    print ('%50s %.5f' % (fn, timeit.timeit(lambda: fn(xs), number=100)))

我正在测试一个整数列表而不是一个字符串(因为对于一个字符串，您不能获得超过 256 个循环)。我机器上的结果如下所示:

3.2.3 (v3.2.3:3d0686d90f55, Apr 10 2012, 11:25:50) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)]

                <function test_set at 0x1020f7380> 0.19265
               <function test_dict at 0x1020f7490> 0.12725
               <function test_sort at 0x1020f7518> 0.04683
            <function test_counter at 0x1020f7408> 0.92485

所以排序方法似乎是赢家。我猜这是因为它不会浪费时间创建哈希和分配 dict/set 结构。此外，如果您不关心正在更改的源列表，您可以执行 xs.sort() 而不是 ys = sorted(xs)，这会给您零内存占用。

另一方面，如果重复项更有可能出现在输入的开头(如 xs = 'abcdef' * 10000)，则 set方法将执行最佳，因为它与 sort 或 Counter 不同，一旦发现重复项就会立即返回，并且不需要预处理整个列表。如果您需要 第一个 重复元素，而不仅仅是其中一个，您还应该使用 set。

Counter 是一个很好的工具，但它不是为性能而设计的，所以如果你真的必须处理“巨大的输入”，请使用集合(如果它们适合内存)或归并排序(如果它们适合)不要。