Есть ли простой способ добраться до "остатка" заданной разницы?

ProgramBox

Есть ли простой способ добраться до «остатка» заданной разницы?

Post author:admin
Запись опубликована:2 ноября, 2022
Post category:Вопросы по программированию

#python #set

#python #установить

Вопрос:

У меня возникла эта проблема:

Учитывая итерацию i , два непересекающихся набора a и b (где обычно a и b каждый содержат гораздо больше элементов, чем i ) удаляют все элементы, a которые находятся в i , и добавляют все элементы i , которые не являются общими a для to b .

Например:

 i = [0, 3]
a = {1, 2, 3, 4}
b = {5, 6, 7, 8}

должно привести к

 a = {1, 2, 4}
b = {0, 5, 6, 7, 8}

С точки зрения этой диаграммы, серые подмножества должны быть пустыми. После операции я хочу, чтобы к светло-синим подмножествам были присоединены b , а желтое перекрытие было удалено a .

Чтобы решить эту проблему, я написал эту функцию Python:

 def foo(i, a, b):
    set_i = set(i)
    b |= set_i - a
    a -= set_i

Это работает, но это не очень красиво и все равно делает что-то (разница a в и set_i ) дважды.

Какой способ был бы более эффективным?

1. Я не вижу, чтобы разница вычислялась дважды: i - a это не простое дополнение a - i .

2. Извините, я не думаю, что понял эту часть «нет простого дополнения». Как разница не вычисляется в обеих этих строках?

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

4. Это заставило меня понять, что я забыл указать, что a и b должны быть непересекающимися.

Ответ №1:

Разве вы не можете просто сделать это так, как вы это описали:

 def foo(i, a, b):

    for el in i:
        if el in a:
            a.remove(el)
        else:
            b.add(el)

Я бы не стал изменять a и b на месте, тем более, что они предоставляются в качестве аргументов функции, безопасная версия будет

 def foo(i, a, b):

    a_new = a.copy()
    b_new = b.copy()

    for el in i:
        if el in a:
            a_new.remove(el)
        else:
            b_new.add(el)

    return a_new, b_new

В общем случае это будет более эффективно, поскольку i , будучи итеративным (который может быть фактическим итератором), вы выполняете итерацию только один раз. Если вы преобразуете его в set , внутренне он будет повторяться один раз, а затем снова, по крайней мере, два раза для каждой операции set.

Вы также можете использовать groupby from itertools , подобный этому:

 from itertools import groupby

def foo(i, a, b):

    for in_a, i_group in groupby(i, key=lambda x: x in a):
    
        if in_a:
            a -= set(i_group)
        else:
            b |= set(i_group)

1. Можно было бы сделать это так, но я предположил, что повторение i только один раз не компенсирует дополнительную работу по удалению из a и добавлению в b за один шаг, в отличие от выполнения этого с помощью операций set. Я также признаю, что мутировать входные аргументы — не лучший стиль, но это то, что я хотел с этим сделать, и копирование их содержимого при каждом вызове не приведет к его сокращению. groupby близок к тому, что я себе представляю, но мне кажется, что вызов этого лямбда-выражения — это просто дополнительная работа, а также функция требует сортировки итератора ввода по ключу.

2. Добавление в a и удаление из b выглядит как дополнительная работа, но внутри операции set все равно выполняются по пунктам, поэтому только ваш код выглядит менее неэффективным, но фактическое время его выполнения быстрее, вы можете рассчитать его и посмотреть, что эффективнее.

3. Согласен, похоже, что они работают одинаково. Однако теперь я не уверен, является ли явная проверка «el в a» дополнительной работой, поскольку внутри set.remove уже может быть что-то подобное. Так что, возможно, это не может быть сделано с абсолютной эффективностью в python.

4. @TheodorStraube Я только что заметил, что в моем первом решении есть ошибка — если один и тот же элемент появляется несколько раз в i , а также в a , его первое вхождение будет удалено a , но последующие будут добавлены b , поскольку он больше не будет присутствовать a . Последнее решение с использованием groupby работает правильно, поскольку генерация групп выполняется до повторения групп.

Ответ №2:

Попробуйте:

 def foo(i, a, b):
    a -= set(i)
    b |= a

1. Это совсем не эквивалентно

2. Это работает для перемещения элементов i в a и b, но также перемещает все, что ранее было в a, в b.

3. Не могли бы вы привести нам какой-нибудь пример того, какими могут быть входные и ожидаемые выходные данные, пожалуйста