性能比较:插入vs构建Python集合操作

Question

在python中,是否更快a)从n个项目列表中构建集合b)将n个项目插入到集合中？

我找到了这个页面(http://wiki.python.org/moin/TimeComplexity),但它没有足够的信息来得出更快的结论.

看来,一次插入一个项目可能在最坏的情况下需要O(n*n)时间(假设它使用dicts),并且在平均情况下需要O(n*1).使用列表初始化集合是否可以提高性能？

Answer 1

就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)

(**)查看sets(Objects/setobject.c)的代码,最终项目插入归结为调用set_add_key.从iterable初始化时,在紧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函数,而C 函数又会调用set_add_key.由于项目添加本身相对较快(Python的哈希表实现非常有效),所以这些额外的调用都会建立起来.