性能比较：插入与构建Python集合操作

Question

在Python中，创建一个集合（set）有两种方法：
a) 从一个包含n个项目的列表中构建一个集合
b) 将n个项目一个一个地插入到集合中。

我找到这个页面（http://wiki.python.org/moin/TimeComplexity），但是里面的信息不足以让我得出哪个方法更快的结论。

看起来，一个一个插入项目在最坏的情况下可能需要O(n*n)的时间（因为它使用了字典），而在平均情况下则是O(n*1)。那么，直接用一个列表来初始化集合是否能提高性能呢？

Answer 1

在我的Thinkpad上：

In [37]: timeit.timeit('for a in x: y.add(a)',
                       'y=set(); x=range(10000)', number=10000)
Out[37]: 12.18006706237793

In [38]: timeit.timeit('y=set(x)', 'y=set(); x=range(10000)', number=10000)
Out[38]: 3.8137960433959961

Answer 2

在编程中，有时候我们需要处理一些数据，比如从一个地方获取信息，然后在另一个地方使用这些信息。这个过程就像是把水从一个桶倒到另一个桶一样。

有些时候，我们可能会遇到一些问题，比如数据格式不对，或者我们想要的数据没有被正确获取。这就像是你想要的水被堵住了，或者桶的形状不对，导致水流不出来。

为了避免这些问题，我们可以使用一些工具和方法来确保数据能够顺利地流动。就像在倒水之前，先检查一下桶是不是干净，水管是不是通畅。

总之，处理数据就像是管理水流一样，需要仔细检查和调整，确保一切都能顺利进行。

$ python -V
Python 2.5.2
$ python -m timeit -s "l = range(1000)" "set(l)"
10000 loops, best of 3: 64.6 usec per loop
$ python -m timeit -s "l = range(1000)" "s = set()" "for i in l:s.add(i)"
1000 loops, best of 3: 307 usec per loop

Answer 3

从 O() 复杂度的角度来看，这两种方法是一样的，因为它们的操作都是将 n 个项目插入到一个集合中。

不过，二者的实现方式有所不同：从可迭代对象初始化的一个明显好处是，你可以节省很多 Python 层级的函数调用——从可迭代对象初始化的过程完全是在 C 语言层面完成的(**)。

实际上，对一个包含 5,000,000 个随机整数的列表进行测试时，逐个添加的速度要慢一些：

lst = [random.random() for i in xrange(5000000)]
set1 = set(lst)    # takes 2.4 seconds

set2 = set()       # takes 3.37 seconds
for item in lst:
    set2.add(item)

---

(**) 看看集合的代码（Objects/setobject.c），最终项目的插入实际上是调用 set_add_key 函数。当从可迭代对象初始化时，这个函数是在一个紧凑的 C 循环中被调用的：

while ((key = PyIter_Next(it)) != NULL) {
  if (set_add_key(so, key) == -1) {
    Py_DECREF(it);
    Py_DECREF(key);
    return -1;
  } 
  Py_DECREF(key);
}

另一方面，每次调用 set.add 都会进行属性查找，这个查找会解析到 C 语言的 set_add 函数，而这个函数又会调用 set_add_key。由于项目的添加本身相对较快（Python 的哈希表实现非常高效），这些额外的调用会逐渐累积起来。