Python: Как получить элементы, которые появляются только в одном наборе из списка наборов?

Question

Я хочу создать функцию, которая берет список из одного или нескольких наборов и находит симметричное различие всех наборов в списке, т.е. результатом должен быть набор значений, каждое из которых содержится только в одномиз отдельных наборов.(Пожалуйста, исправьте меня, если я ошибаюсь из-за симметричной разницы.)

Например:

>>> s1 = set([1, 2, 3])
>>> s2 = set([2, 3, 4])
>>> s3 = set([2, 3, 7])
>>> s4 = set([2, 5, 9])
>>> myfunc([s1, s2, s3, s4])
{1, 4, 5, 7, 9}

Есть ли что-то встроенное, что можно использовать выше вместо * 1006?*?Или я использую что-то вроде этого:

def myfunc(sets: List[set]) -> set:

    sd = set()
    goners = set()
    for s in sets:
        still_ok = s - goners
        sd = sd.symmetric_difference(still_ok)
        goners = goners.union(s.difference(sd))
    return sd

Есть ли лучший / более эффективный / "Pythonic" способ сделать это?

Answer 1

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

Улучшенная версия вашего подхода с использованием операторов набора выглядит следующим образом:

def myfunc_improved(sets: List[set]) -> set:
    sd = set()
    goners = set()
    for s in sets:
        sd ^= s - goners
        goners |= s - sd
    return sd

Производительность измерений:

%timeit myfunc(sets)
%timeit myfunc_improved(sets)

3.19 µs ± 34.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
1.75 µs ± 11.5 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Answer 2

Вам нужен набор B, содержащий все члены, которые содержатся исключительно в одном ваших наборов в A. Как насчет следующего (Python 3)?

from functools import reduce
A = [set([1, 2, 3]), set([2, 3, 4]), set([2, 3, 7]), set([2, 5, 9])]
B = set()
for i in range(len(A)):
    U = reduce(set.union, A[:i]+A[(i+1):])
    B = B.union(set.difference(A[i], U))

print(B)

{1, 4, 5, 7, 9}

Answer 3

сначала да, ваше наблюдение неверное, s3, s4) будет {1, 3, 4, 5, 7, 9}.

def s_diff(li):
    res=set()
    for s in li:
        res =res.symmetric_difference(s)
    return res


output:
s_diff([s1,s2,s3,s4])
{1, 3, 4, 5, 7, 9}

Answer 4

Как насчет этого:

from collections import Counter

s1 = set([1, 2, 3])
s2 = set([2, 3, 4])
s3 = set([2, 3, 7])
s4 = set([2, 5, 9])
print([k for k,v in Counter((*s1,*s2,*s3,*s4)).items() if v == 1])

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

In [85]: def nicefunc(sets): 
    ...:     return [k for k,v in Counter(itertools.chain.from_iterable(sets)).items() if v == 1] 
    ...:                                                                                                                                                                                       

In [86]: def nicefunc2(sets): 
    ...:     return [k for k,v in Counter( [i for s in sets for i in s]).items() if v == 1] 
    ...:                                                                                                                                                                                       

In [87]: def nicefunc3(): 
    ...:     return [k for k,v in Counter((*s1,*s2,*s3,*s4)).items() if v == 1] 
    ...:                                                                                                                                                                                       

In [88]: def myfunc(sets): 
    ...:     sd = set() 
    ...:     goners = set() 
    ...:     for s in sets: 
    ...:         still_ok = s - goners 
    ...:         sd = sd.symmetric_difference(still_ok) 
    ...:         goners = goners.union(s.difference(sd)) 
    ...:     return sd 
    ...:                                                                                                                                                                                       

In [89]: sets = [s1, s2, s3, s4]                                                                                                                                                               

In [90]: %timeit myfunc(sets)                                                                                                                                                                  
2.25 µs ± 2.53 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [91]: %timeit nicefunc(sets)                                                                                                                                                                
3.64 µs ± 23 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [92]: %timeit nicefunc2(sets)                                                                                                                                                               
3.79 µs ± 11.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [94]: %timeit nicefunc3()                                                                                                                                                                   
3.64 µs ± 18.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

ВыМожно также выбрать другой подход, который все еще является одним, но более быстрым:

In [152]: def coolfunc(sets): 
     ...:     return set.union(*[sets[i]-set.union(*sets[:i],*sets[i+1:]) for i in range(len(sets))]) 

In [153]: coolfunc(sets)                                                                                                                                                                       
Out[153]: {1, 4, 5, 7, 9}

In [154]: %timeit coolfunc(sets)                                                                                                                                                               
3.34 µs ± 19.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Однако, как указал @VBrail, вы неправильно определили различие симметричных множеств в наборе множеств.Ниже приведен однострочник для расчета фактической симметричной разности наборов в коллекции, которая определяется как

. Симметричная разность набора содержит только элементы, которые находятся в нечетном числе наборов вколлекция Википедия

from functools import reduce                                                                                                                                                          
s1 = set([1, 2, 3]) 
s2 = set([2, 3, 4]) 
s3 = set([2, 3, 7]) 
s4 = set([2, 5, 9])                                                                                                                                                                   
sets = [s1,s2,s3,s4]                                                                                                                                                                  
reduce(set.symmetric_difference, sets)      

{1, 3, 4, 5, 7, 9}

Answer 5

Модуль itertools отчасти полезен для таких вещей:

import itertools as it

def only_exists_in_one_set(target):
    remover = []
    case = it.combinations(target, 2) #generate all combinations ignores order
    while True:
        try:
            temp = next(case)
            # AND all combos to find duplicates
            remover.append(temp[0] & temp[1])
        except StopIteration:
            break
    #flatten the nested list of sets passed to the function:
    target = [x for each_set in target for x in each_set]
    #flatten remover, eliminate duplicates with set
    for val in set([x for each_set in remover for x in each_set]):
        target = [a for a in target if a != val]    #remove all duplicate values
    return sorted(target)

>>> only_exists_in_one_set([{1,2,3},{2,3,4},{2,3,7},{2,5,9}])

>>> [1, 4, 5, 7, 9]

Не такой краткий, как многие подходы, но, возможно, читаемый?