<p>由于这是一个性能问题,让我们做一些计时:</p>
<pre><code>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)))
</code></pre>
<p>我测试的是一个整数列表,而不是一个字符串(因为对于一个字符串,不能得到超过256个循环)。我机器上的结果是这样的:</p>
<pre><code>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
</code></pre>
<p>所以排序方法似乎是胜利者。我想这是因为它不会浪费时间创建散列和分配dict/set结构。另外,如果您不关心源列表的更改,您可以执行<code>xs.sort()</code>,而不是<code>ys = sorted(xs)</code>,这样就没有内存占用。</p>
<p>另一方面,如果重复项更可能出现在输入的开头(如<code>xs = 'abcdef' * 10000</code>),那么<code>set</code>方法将执行得最好,因为它与<code>sort</code>或<code>Counter</code>不同,一旦找到重复项,就立即返回,并且不需要预处理整个列表。如果您需要<em>第一个</em>重复元素,那么您还应该使用<code>set</code>,而不仅仅是其中一个。</p>
<p><code>Counter</code>是一个很好的工具,但是它不是为性能而设计的,所以如果你真的需要处理“巨大的输入”,那么就使用集合(如果它们适合内存)或者合并排序(如果它们不适合内存)</p>