Question

关于 python set 列表 差集的问题。

有2个50万级别的 列表，
求差集，为什么python 用set 去做，就那么快。
2秒 就算出来了。

想了解下大概的算法。

Answer 1

从源代码看在set中增加一个元素，就可以看出set是根据hash表来索引数据，每个元素都计算出一个long类型的hash值。

另外一个优化就是内存分配：set_table_resize
每次增加元素时，如果原来分配数不够，就一次增加一批，而不是一个一个增加。

static int set_add_key(register PySetObject *so, PyObject *key)
{
register long hash;
register Py_ssize_t n_used;

if (!PyString_CheckExact(key) ||
(hash = ((PyStringObject *) key)->ob_shash) == -1) {
hash = PyObject_Hash(key);
if (hash == -1)
return -1;
}
assert(so->fill <= so->mask); /* at least one empty slot */
n_used = so->used;
Py_INCREF(key); //插入元素引用+1
if (set_insert_key(so, key, hash) == -1) {
Py_DECREF(key);
return -1;
}
if (!(so->used > n_used && so->fill*3 >= (so->mask+1)*2))
return 0;
return set_table_resize(so, so->used>50000 ? so->used*2 : so->used*4);
}

static int set_insert_key(register PySetObject *so, PyObject *key, long hash)
{
register setentry *entry;
typedef setentry *(*lookupfunc)(PySetObject *, PyObject *, long);

assert(so->lookup != NULL);
entry = so->lookup(so, key, hash); //这里根据hash值来查找元素
if (entry == NULL)
return -1;
if (entry->key == NULL) {
/* UNUSED */
so->fill++;
entry->key = key;
entry->hash = hash;
so->used++;
} else if (entry->key == dummy) {
/* DUMMY */
entry->key = key;
entry->hash = hash;
so->used++;
Py_DECREF(dummy);
} else {
/* ACTIVE */
Py_DECREF(key);
}
return 0;
}

Answer 2

Python中的set是用hash表来实现的。hash表的查找，插入，删除等操作时间近似常数，所以很快。你可以看看hash表的具体实现方式就明白了。
比如百度百科中“哈希表”条目。

Answer 3

python里面有部分代码是用c写的，c的计算比较快，set差集python里面用了几种算法的，它通过判断你要求的set的大小来确认那种算法，而数据较大的是用c写的

Answer 4

这个还真不知道

建议你直接去看Python源代码中关于set的部分，这应该是最原始的资料了，比别人讲解要好的多