Блог

У меня есть пример использования для эффективной реализации набора с XOR-подобным поведением.

Набор, который при добавлении элемента удаляет элемент из набора, если он уже содержится в наборе, но добавляет его в случае, если это не так. Смотрите приведенный ниже код:

 # Create set `a`
a = xorset((0,0,0,1,1,2))
assert a == {0,2}
a.add(0)
assert a == {2}
a.add(0)
assert a == {0,2}

a.update((0,0))
assert a == {0,2}
a.update((0,0,0,2,1))
assert a == {1}
 

До сих пор моей лучшей попыткой было использовать объект collections Counter для создания наборов, подобных этому:

 from collections import Counter
def xorset(it):
    return set(k for k,v in Counter(it) if v % 2 == 1)
 

а затем вручную выполнить операции добавления и обновления:

 import itertools
def xorset_add(s,e):
    if e in s:
         s.remove(e)
    else:
         s.add(e)
    return s # not necessary as works in place
def xorset_update(s,it):
    return set(k for k,v in Counter(itertools.chain(s,it)) if v % 2 == 1)
 

Я бы предположил, что было бы возможно значительное ускорение, если бы существовала библиотека, которая обрабатывала добавление/удаление новых элементов, но я не смог ее найти. Кто-нибудь знает о его существовании?

Спасибо!

Если я вас не неправильно понял, похоже set , что метод symmetric_difference_update делает то, что вы ищете, и, поскольку он встроен, он работает примерно так быстро, как вы собираетесь.

 >>> s = set((1,2,3))
>>> s
{1, 2, 3}
>>> s.symmetric_difference_update(set((2,)))         ["add" 2, but removes 2]
>>> s
{1, 3}
>>> s.symmetric_difference_update(set((2,)))         ["add" 2 back]
>>> s
{1, 2, 3}
>>> s.symmetric_difference_update(set((3,4)))        ["add" 3 and 4, but removes 3]
>>> s
{1, 4}
 

Вы можете выполнить ту же операцию с ^= оператором:

 >>> s
{1, 4}
>>> s ^= set((4,))
>>> s
{1}
>>> s ^= set((4,))
>>> s
{1, 4}
 

Обновление: реализация xorset класса, предоставленного @Erwin Haasnoot

Полная неизменяемая реализация xorset, подкласс frozenset, будет выглядеть следующим образом:

 import itertools
from collections import Counter

class xorset(frozenset):
    def __new__(cls, it=()):
        it = (k for k, v in Counter(it).items() if v amp; 1)
        return super().__new__(cls, it)

    def add(self, v):
        return self ^ {v}

    def update(self, it):
        return self.__class__(itertools.chain(self, it))```