python - 使用 Python 3 上的任何数据结构检查一个组是否是其他组的子组的最有效方法

Question

如果我可以在对象列表、整数列表和字典之间进行选择(是否有任何其他数据结构选项？)，这是发现一个组是否是另一个组的子组的最有效数据结构，以及如何实现？

我有一个具有唯一整数属性的类，因此我可以通过它们包含的整数或对象(指针)本身“表示”类对象。

a.atributeEx = 1
b.atributeEx = 2
c.atributeEx = 3

listOfPointers = [a,b,c]
listAtributes = [1,2,3]
dictEx = ['1':1, '2':2, '3':3]

一种选择是使用 issubset，如下所示:

listAtributes2 = [1,2]
set(listAtributes).issubset(listAtributes2)

但是，使用带有属性列表的 issubset 函数，我的代码将需要数月甚至数年才能完成运行，因为这必须执行数十亿次。通常，一个列表包含 1 到 4 个元素，而另一个列表包含 200 到 2000 个元素。

解决这个问题的最佳方法是什么？

Answer 1

使用set 方法应该相当有效。特别是，如果您执行 x.issubset(y)，只有 x 的大小很重要，因为 set 使用散列来检查它是否包含给定的项目。

尽管如此，如果您为每次比较都实例化一个集合，那么您的计算就会增加很大的开销。

一个解决方案是仅在您的 __init__ 方法中实例化一个新的 set 并将其填充到您的 __setattr__ 方法中。为了也允许删除属性，您可以定义一个 __delattr__ 方法来从 set 中删除元素。最后，在使用关键字in时，可以使用__contains__方法进行子集比较。

class Container:
    def __init__(self, **kwargs):
        self.__dict__['_attr_set'] = set()
        for k, v in kwargs.items():
            setattr(self, k, v)

    def __setattr__(self, key, value):
        self._attr_set.add((key, value))
        super().__setattr__(key, value)

    def __delattr__(self, item):
        for x in self._attr_set:
            if x[0] == item:
                self._attr_set.remove(x)
                break
        super().__delattr__(item)


    def __contains__(self, item):
        return item._attr_set.issubset(self._attr_set)

例子

x = Container(a=1, b=2, c=3)
y = Container(a=1, b=2)

print(y in x) # True