我知道这段代码的效率不是最优的(特别是在输入量巨大的情况下),而且我知道有一种方法可以改变此算法来处理其他数据类型,而不仅仅是字符串中的重复(显然只有这么多字符可供搜索)。
有什么办法可以提高效率吗?
我试着用字典,函数一直返回“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')
您可以使用
collections
查找重复字符:如果只想查找是否有重复(不查找重复字符):
由于这是一个性能问题,让我们做一些计时:
我测试的是一个整数列表,而不是一个字符串(因为对于一个字符串,不能得到超过256个循环)。我机器上的结果是这样的:
所以排序方法似乎是胜利者。我想这是因为它不会浪费时间创建散列和分配dict/set结构。另外,如果您不关心源列表的更改,您可以执行
xs.sort()
,而不是ys = sorted(xs)
,这样就没有内存占用。另一方面,如果重复项更可能出现在输入的开头(如
xs = 'abcdef' * 10000
),那么set
方法将执行得最好,因为它与sort
或Counter
不同,一旦找到重复项,就立即返回,并且不需要预处理整个列表。如果您需要第一个重复元素,那么您还应该使用set
,而不仅仅是其中一个。Counter
是一个很好的工具,但是它不是为性能而设计的,所以如果你真的需要处理“巨大的输入”,那么就使用集合(如果它们适合内存)或者合并排序(如果它们不适合内存)相关问题 更多 >
编程相关推荐