Python:创建具有类似 Xor 行为的集合

Question

我有一个用例，用于有效实现具有类似 XOR 行为的 Set。
一个集合，如果添加一个元素，如果该元素已经包含在集合中，则从集合中删除该元素，但如果不包含，则添加它。请参阅以下代码:

# 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像这样创建集合的计数器对象:

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)

我想如果有一个处理新元素添加/删除的库，可能会有显着的加速，但我找不到任何。有谁知道一个的存在？
谢谢!

Answer 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}

您可以使用 ^= 执行相同的操作。运算符(operator):

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

更新 :实现 xorset @Erwin Haasnoot 提供的类(class)
一个完整的不可变 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 & 1)
        return super().__new__(cls, it)

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

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