Вычитание двух списков в Python

Question

В Python, как можно вычесть два неуникальных неупорядоченных списка? Скажем, у нас есть a = [0,1,2,1,0] и b = [0, 1, 1] Я хотел бы сделать что-то вроде c = a - b и иметь c be [2, 0] или [0, 2] порядок, для меня не имеет значения. Это должно вызвать исключение, если a не содержит все элементы в b.

Обратите внимание, что это отличается от наборов! Меня не интересует различие наборов элементов в a и b, меня интересует различие между фактическими наборами элементов в a и б.

Я могу сделать это с помощью цикла for, отыскивая первый элемент b в a, а затем удаляя элемент из b и из a и т. Д. Но это мне не нравится, это будет очень неэффективно (порядок O(n^2) времени), в то время как это не должно быть проблемой, чтобы сделать это в O(n log n) времени.

Answer 1

list(set([x for x in a if x not in b]))

• Листья a и b нетронуты.
• Является уникальным набором "a - b".
• Готово.

Answer 2

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

from copy import copy

def subtract_lists(a, b):
    """
    >>> a = [0, 1, 2, 1, 0]
    >>> b = [0, 1, 1]
    >>> subtract_lists(a, b)
    [2, 0]

    >>> import random
    >>> size = 10000
    >>> a = [random.randrange(100) for _ in range(size)]
    >>> b = [random.randrange(100) for _ in range(size)]
    >>> c = subtract_lists(a, b)
    >>> assert all((x in a) for x in c)
    """
    a = copy(a)
    for x in b:
        if x in a:
            a.remove(x)
    return a

Answer 3

Вы можете попробовать что-то вроде этого:

class mylist(list):

    def __sub__(self, b):
        result = self[:]
        b = b[:]
        while b:
            try:
                result.remove(b.pop())
            except ValueError:
                raise Exception("Not all elements found during subtraction")
        return result


a = mylist([0, 1, 2, 1, 0] )
b = mylist([0, 1, 1])

>>> a - b
[2, 0]

Вы должны определить, что должны выводить [1, 2, 3] - [5, 6], хотя, я думаю, вы хотите [1, 2, 3], поэтому я игнорирую ValueError.

Edit: Теперь я вижу, что вы хотели исключение, если a не содержит все элементы, добавили его вместо передачи ValueError.