Самый эффективный способ проверить, является ли группа подгруппой другой группы, используя любую структуру данных на 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 использует хеширование, чтобы проверить, содержит ли он данный элемент.

Хотя, если вы создаете экземпляр набора для каждогоДля сравнения вы добавляете большие накладные расходы к своим вычислениям.

Одним из решений является создание нового set только в вашем методе __init__ и заполнение его в вашем методе __setattr__.Чтобы разрешить удаление атрибутов, вы также можете определить метод __delattr__, который удаляет элементы из set.Наконец, вы можете использовать метод __contains__ для выполнения сравнения подмножеств при использовании ключевого слова in.

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

Answer 2

Посмотрите на наборы питонов.Тип данных set содержит все необходимые операции (например, issubset) и действительно быстр.Если вы можете упростить свой код вызова и позволить наборам выполнять свою работу, вы увидите, что это хорошо работает.

>>> x = set(range(1000))
>>> y = {8,37,29,983}
>>> y.issubset(x) 
True

Так что я поместил это в цикл.Он выполнялся 100 000 000 раз за 27 секунд.

Я думаю, что если вы предварительно вычислите свои множества вместо построения их для каждого сравнения, вы обнаружите, что это суперэффективный способ обработки.

https://docs.python.org/3/tutorial/datastructures.html#sets