Python集合交集 - 返回哪些对象

Question

我有一个问题在Python文档(https://docs.python.org/2/library/stdtypes.html#set.intersection)中并没有很清楚的解释。

使用set.intersection时，结果集包含当前集合或其他集合中的对象？如果两个对象具有相同的值但在内存中是不同的对象呢？

我正在使用它来比较从文件中提取出的先前数据和从互联网获取的新数据。两者都有一些相似的对象，但我想更新旧的对象。也许有更简单的方法来实现这个目标吗？如果集合实现了__getitem__，那就会更容易些。

    oldApsExtract = set()
    if (os.path.isfile("Apartments.json")):
        with open('Apartments.json', mode='r') as f:
            oldApsExtract = set(jsonpickle.decode(f.read()))
    newApsExtract = set(getNewExtract())

    updatedAps = oldApsExtract.intersection(newApsExtract)
    deletedAps = oldApsExtract.difference(newApsExtract)
    newAps = newApsExtract.difference(oldApsExtract)

    for ap in deletedAps:
        ap.mark_deleted()

    for ap in updatedAps:
        ap.update()

    saveAps = list(oldApsExtract) + list(newAps)
    with open('Apartments.json', mode='w') as f:
        f.write(jsonpickle.encode(saveAps))

- husvar

---

两者都有一些相似的对象，但是我想要更新旧的那些。如果你的对象是可变的，那么你可能根本无法将它们放入集合中。如果你可以这样做，那么很可能违反了不可变对象才能被哈希且在 == 比较时不受影响的规则。集合并不适用于可变内容。 - user2357112

为什么需要 __getitem__？如果这确实是你想要的，你可以这样做：for thing in set1: if thing in set2: do_whatever(thing)。 - jonrsharpe

你是对的。我只是想利用内置方法，因为它们通常更优化。 - husvar

依赖于实现特定的行为是不好的编程实践，这也是你问题所询问的。你可能本来就不应该创建可变但哈希不变的对象。有更好的方法。 - msw

如果你发现只有扩展语言才能使你的方法更容易，那么这可能是一个不好的想法。 - msw

Answer 1

如果集合大小相同，则使用的对象会有所不同，从b中返回交集元素，如果b具有更多元素，则从a返回对象：

i = "$foobar" * 100
j = "$foob" * 100
l  = "$foobar" * 100
k = "$foob" * 100
print(id(i), id(j))
print(id(l), id(k))
a = {i, j}
b = {k, l, 3}
inter = a.intersection(b)
for ele in inter:
    print(id(ele))

输出：

35510304 35432016
35459968 35454928
35510304
35432016

现在它们是相同的大小：

i = "$foobar" * 100
j = "$foob" * 100
l  = "$foobar" * 100
k = "$foob" * 100
print(id(i), id(j))
print(id(l), id(k))
a = {i, j}
b = {k, l}
inter = a.intersection(b)
for ele in inter:
    print(id(ele))

输出：

35910288 35859984
35918160 35704816
35704816
35918160

这里是源代码的相关部分。该行代码 if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) 中比较的结果似乎决定了应该迭代哪个对象以及使用哪些对象。

    if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
        tmp = (PyObject *)so;
        so = (PySetObject *)other;
        other = tmp;
    }
     
    while (set_next((PySetObject *)other, &pos, &entry)) {
        key = entry->key;
        hash = entry->hash;
        rv = set_contains_entry(so, key, hash);
        if (rv < 0) {
            Py_DECREF(result);
            return NULL;
        }
        if (rv) {
            if (set_add_entry(result, key, hash)) {
                Py_DECREF(result);
                return NULL;
            }

如果传递的对象不是一个集合，那么长度就无关紧要了，因为可迭代对象中的对象将被使用：

it = PyObject_GetIter(other);
if (it == NULL) {
    Py_DECREF(result);
    return NULL;
}

while ((key = PyIter_Next(it)) != NULL) {
    hash = PyObject_Hash(key);
    if (hash == -1)
        goto error;
    rv = set_contains_entry(so, key, hash);
    if (rv < 0)
        goto error;
    if (rv) {
        if (set_add_entry(result, key, hash))
            goto error;
    }
    Py_DECREF(key);

当您传递一个可迭代对象时，首先它可能是一个迭代器，因此在消耗之前无法检查其大小；如果您传递了一个列表，那么查找将会是 0(n) 的，因此最好只是遍历传入的可迭代对象。相比之下，如果您有一个包含 1000000 个元素和一个包含 10 个元素的集合，则检查这 10 个元素是否在包含 1000000 个元素的集合中是有意义的，而不是检查任何 1000000 个元素是否在您的包含 10 个元素的集合中，因为平均查找时间应该是 0(1)，这意味着对于 10 个元素的线性遍历与对于 1000000 个元素的线性遍历相比较。

如果您查看 wiki.python.org/moin/TimeComplexity，可以证明上述内容。

平均情况 -> 交集 s&t O(min(len(s), len(t))

最坏情况 -> O(len(s) * len(t))O(len(s) * len(t))

如果t不是一个集合，则将“min”替换为“max”

因此，当我们传递可迭代对象时，我们应该总是从b中获取对象：

i = "$foobar" * 100
j = "$foob" * 100
l  = "$foobar" * 100
k = "$foob" * 100
print(id(i), id(j))
print(id(l), id(k))
a = {i, j}
b = [k, l, 1,2,3]
inter = a.intersection(b)
for ele in inter:
    print(id(ele))

你从b中获取对象：

20854128 20882896
20941072 20728768
20941072
20728768

如果您真的想决定保留哪些对象，那么请自行进行迭代和查找，并保留您想要的任何对象。

- Padraic Cunningham

---

谢谢。我希望结果更加“可预期”。程序员可以选择要迭代哪个。 - husvar

@husvar，我想如果你正在寻找交集，那么迭代较小的集合更有意义，如果另一个集合只有10个元素，那么迭代10000个元素是没有意义的。 - Padraic Cunningham

@husvar 迭代的是什么，返回的是完全独立的事物。当你找到一个匹配时，你拥有两个元素，因此你可以返回其中任意一个，而不会增加额外的时间复杂度。 你说得对，最好总是从第一个集合中返回元素。 - Kiuhnm

Answer 2

你可以使用Python字典来实现这个功能。访问时间仍然是O(1)，元素易于访问，而且只需要一个简单的循环就可以得到交集特性：

 res=[]
 for item in dict1.keys():
  if dict2.has_key(item):
   res.append(item)

这里的优势在于您可以完全控制正在发生的事情，并根据需要进行调整。例如，还可以执行以下操作：

if dict1.has_key(item):
 dict1[item]=updatedValue

- Untitled123

---

不要使用.has_key；它已经被弃用了，并且比基于语法的包含检查更慢。将dict1.has_key(item)替换为item in dict1，它运行得更快（并且与所有容器类型一样有效，而不仅仅是dict）。同样，在Py3中不需要迭代.keys()；在Py2中这是浪费的（因为它创建一个完整的list来包含所有的键）；你可以直接迭代键（没有副本，没有调用）使用for item in dict1:。 - ShadowRanger

当然，这一切都是毫无意义的；你可以使用set来完成完全相同的事情，那么为什么我们要费心去使用dict，在其中每个键都必须存储一个垃圾值呢？ - ShadowRanger

我使用了一个字典，因为他提到了get_item方法，而字典允许你在O(1)时间内完成这个操作。 - Untitled123

set的成员测试在平均情况下具有相同的时间。我猜你可以通过维护一个将键映射到自身的dict来允许获取一个非相等但相等的对象，但实际上，如果你处于这种位置，几乎肯定违反了set成员和dict键应该遵守的可变性不变式。 - ShadowRanger

最初这个问题要求快速获取一个项目，我将其解释为基于键访问任意随机项目。我没有认为集合有这种能力。 - Untitled123