Python中检查重复项的最快方法是什么？

Question

使用词典似乎是最理想的选择。

例如：

history = {}
for i in collection:
    if i not in history:
        history[i] = None
        # fancy computation here

使用set()类型会比较快吗？使用set()不需要在哈希键中添加无意义的None值。

- TheOne

Answer 1

是的，你应该使用set。

---

使用set()类型会和使用其他方法一样快吗？

不，它不仅仅和其他方法一样快，而是会更加快速。

---

更新

一些人发布了基准测试结果，显示set比dict慢。我认为这有点让人惊讶，因为它们基本上具有相同的底层实现，只是set更加简单。我认为我找到了慢的原因：

def set_way():
    my_set = set()
    my_set_add = my_set.add   # remember the method
    for ele in x:
        if ele not in my_set:
            my_set_add(ele)   # call the method directly

结果：

dict time : 1.896939858077399
set time : 1.8587076107880456

如预期所示，现在Set的速度稍微快了一些。

- Mark Byers

---

为什么更快？在字典中检查键需要恒定的时间，集合是否使用完全相同的算法？ - TheOne

@Ramin：是的，集合也使用哈希表。集合中的项必须是可哈希的。 - Mark Byers

@Ramin，集合的实现方式与“dict”几乎完全相同。 - agf

@MarkByers 如果列表包含一些不可哈希的类型，例如列表、集合等，该怎么办？ - Ashwini Chaudhary

好的，集合不需要为一个值分配内存，它只有一个键，因此应该更快，并且使用更少的内存。 - schlenk

Answer 2

词典似乎更快。

import timeit
import random as rn

x  = [rn.choice(xrange(10000)) for i in xrange(1000)]

def set_way():
    my_set = set()
    for ele in x:
        if ele in my_set:
            return True
        else:
            my_set.add(ele)
    else:
        return False

def dict_way():
    dicto = {}
    for ele in x:
        if ele in dicto:
            return True
        else:
            dicto[ele] = None
    else:
        return False



num = 10000

set_time = timeit.timeit(set_way, number = num)
print 'set time :', set_time
dict_time = timeit.timeit(dict_way, number = num)
print 'dict time :', dict_time

结果：

set time : 0.619757678699
dict time : 0.466664548148

- Akavall

---

集合比较慢？令人惊讶...你有解释吗？ - Mark Byers

我也感到惊讶。或许将元素添加到集合中比添加到字典中要慢？我很好奇自己也想知道解释是什么。 - Akavall

+1 鼓励发布令人惊讶的性能测量结果。请查看我的更新答案以获取解释。 - Mark Byers

Answer 3

字典速度更快，但只有稍微的优势：

import timeit

setup = """
x = range(10000)
s = set(range(5000))
d = dict.fromkeys(range(5000))
"""

print '# set', timeit.timeit('for i in x: z = i in s', setup, number=1000)
print '# dic', timeit.timeit('for i in x: z = i in d', setup, number=1000)

# set 1.18897795677
# dic 1.1489379406

然而，除非性能绝对关键，否则出于可读性的考虑，您应该使用集合。

当然，正如您的问题所暗示的那样，我们正在谈论可哈希类型。不可哈希类型（例如容器）将需要其他技术。

为了完整起见，这里是不同修改方法的基准测试：

import timeit

setup = """
x = range(10000)
s = set(range(5000))
d = dict.fromkeys(range(5000))

add_method = s.add
"""

print '# set-add     ', timeit.timeit('for i in x: s.add(i)', setup, number=1000)
print '# set-closure ', timeit.timeit('for i in x: add_method(i)', setup, number=1000)
print '# dict []     ', timeit.timeit('for i in x: d[i]=None', setup, number=1000)
print '# d.setdefault', timeit.timeit('for i in x: d.setdefault(i)', setup, number=1000)

# set-add      1.96829080582
# set-closure  1.2261030674
# dict []      0.982795000076
# d.setdefault 2.27355480194

dict[i] 是最快的，但这次并不奇怪，因为没有涉及到函数调用。

- georg

---

你的测试和问题要求的不一样。你没有逐步添加到集合/字典中。 - schlenk

@thg435，你运行了足够多的代码来保证字典始终优于集合吗？计时算法并不是检查速度的好方法。 - TheOne

@schlenk：“add”代码对于这个问题并不重要，也不会影响时间。 - georg

@thg435 当涉及到调整哈希表的大小和更改它时，“添加”非常重要。在您的示例中，您有最佳情况，可以知道表的最终大小并在一步中分配它。 - schlenk