Установите понимание и разные сопоставимые отношения

Question

У меня есть набор объектов, которые в некотором роде сопоставимы, и я хочу удалить объекты из набора. Я думал о том, как эта проблема меняется, в разных сопоставимых отношениях между элементами. Меня интересовало развитие пространства поиска, использование памяти и масштабирование проблемы.

1-й сценарий: в самом простом сценарии отношение было бы двунаправленным, и, таким образом, мы могли бы удалить оба элемента, при условии, что мы можем гарантировать, что при удалении элементов не будут удалены другие "партнеры".

2-й сценарий: сопоставимое соотношение не является двунаправленным. Удалите только тот элемент, о котором идет речь, а не тот, с которым он сопоставим. Упрощенный сценарий будет набором, состоящим из целых чисел, и сопоставимая операция будет "делится без остатка"

Я могу сделать следующее, не удаляя элементы:

a_set = set([4,2,3,7,9,16])

def compare(x, y):
    if (x % y == 0) and not (x is y):
        return True
    return False

def list_solution():
    out = set()
    for x in a_set:
        for y in a_set:
            if compare(x,y):
                out.add(x)
                break
    result = a_set-out
    print(result)

Конечно, мой первый вопрос как младшего программиста на Python: "Какое подходящее понимание для этого?

Кроме того: я не могу изменить размер наборов Python во время итерации без копирования, верно?

А теперь для алгоритма людей: как эта проблема изменится, если соотношение между количеством элементов в элементе может быть сравнимо с увеличением. Как это меняется, если сопоставимые отношения представляют частичные заказы?

Answer 1

Я буду предшествовать подтверждению вашей заявки - изменение набора во время итерации вызовет RuntimeErrorчто бы претендовать на что-то вроде "Set changed size during iteration",

---

Теперь давайте начнем с compare функция: так как вы используете наборы, x is y вероятно, как x == y и последний всегда лучший выбор, когда это возможно.

Кроме того, нет необходимости в состоянии; вы уже выполняете один:

def compare (x, y):
    return x != y and x % y == 0

Теперь, чтобы установить понимание - это грязное. После установки набора в качестве аргумента - что лучше, чем использование глобальной переменной - нормальный код будет выглядеть примерно так:

for x in my_set:
    for y in my_set:
        if compare(x, y):
            for a in (x, y):
                temp.append(a)

обратите внимание на последние две строки, которые не используют распаковку, потому что это было бы невозможно в понимании. Теперь все, что осталось, это переместить a вперед и сделай все : исчезают - и происходит волшебство:

def list_solution (my_set):
    return my_set - {a for x in my_set for y in my_set if compare(x, y) for a in (x, y)}

Вы можете проверить это с чем-то вроде

my_set = set([4, 2, 3, 7, 9, 16])
print(list_solution(my_set)) # {7}

• Условие и итерация по (x, y) Я могу поменяться местами, но я считаю, что повторение после подтверждения будет быстрее, чем ввод и начало повторения, когда есть вероятность, что вы не будете выполнять никаких действий.

---

Изменение для второго случая незначительно - просто использование x вместо x, y распаковка:

def list_solution_2 (my_set):
    return my_set - {x for x in my_set for y in my_set if compare(x, y)}