我知道这段代码的效率不是最佳的（尤其是在输入巨大的情况下），而且我知道有一种方法可以更改此算法以处理其他数据类型，而不仅仅是字符串中的重复（显然只有这样）搜索许多字符）。
有什么办法可以提高效率吗？
我尝试使用字典，并且该函数始终返回“ none”，所以我尝试了一个列表，但一切正常。
提前感谢任何可以帮助我的人！
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')
现在带有字典...。（它一直向控制台打印“ none”）
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')
由于这是一个性能问题，所以让我们做一些时间安排：
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 是一个不错的工具，但它不是为性能而设计的，因此，如果您真的必须处理“大量输入”，请使用集（如果它们适合内存）或合并排序。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句