Операция вычитания списка Python

Question

Я хочу сделать что-то похожее на это:

>>> x = [1,2,3,4,5,6,7,8,9,0]  
>>> x  
[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]  
>>> y = [1,3,5,7,9]  
>>> y  
[1, 3, 5, 7, 9]  
>>> y - x   # (should return [2,4,6,8,0])

Но это не поддерживается списками Python. Как лучше всего это сделать?

Answer 1

Используйте понимание списка:

[item for item in x if item not in y]

Если вы хотите использовать инфиксный синтаксис -, вы можете просто сделать:

class MyList(list):
    def __init__(self, *args):
        super(MyList, self).__init__(args)

    def __sub__(self, other):
        return self.__class__(*[item for item in self if item not in other])

, а затем использовать его следующим образом

x = MyList(1, 2, 3, 4)
y = MyList(2, 5, 2)
z = x - y   

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

Answer 2

Использовать установить разницу

>>> z = list(set(x) - set(y))
>>> z
[0, 8, 2, 4, 6]

Или вы можете просто установить x и y, чтобы вам не приходилось выполнять какие-либо преобразования.

Answer 3

Это операция «установить вычитание».Для этого используйте заданную структуру данных.

В Python 2.7:

x = {1,2,3,4,5,6,7,8,9,0}
y = {1,3,5,7,9}
print x - y

Вывод:

>>> print x - y
set([0, 8, 2, 4, 6])

Answer 4

, если проблемы с дублированием и заказом:

[i for i in a if not i in b or b.remove(i)]

a = [1,2,3,3,3,3,4]
b = [1,3]
result: [2, 3, 3, 3, 4]

Answer 5

Для многих случаев использования вам нужен ответ:

ys = set(y)
[item for item in x if item not in ys]

Это гибрид между ответом Ааронастерлинга и ответом QuantSoup .

версия aaronasterling выполняет len(y) сравнение элементов для каждого элемента в x, поэтому требуется квадратичное время. В версии QuantSoup используются наборы, поэтому для каждого элемента в x выполняется поиск по одному набору с постоянным временем, но, поскольку он преобразует и x, и y в наборы, он теряет порядок ваши элементы.

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

---

Тем не менее, в версии QuantumSoup все еще есть проблема: она требует, чтобы ваши элементы были хэшируемыми. Это в значительной степени встроено в природу наборов. ** Если вы пытаетесь, например, вычесть список диктов из другого списка, но список для вычитания велик, что вы делаете?

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

ys = {tuple(item.items()) for item in y}
[item for item in x if tuple(item.items()) not in ys]

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

---

Если ваши элементы не являются и не могут быть сделаны хэшируемыми, но они сопоставимы, вы можете получить, по крайней мере, логарифмическое время (O(N*log M), что намного лучше, чем O(N*M) время решение списка, но не так хорошо, как O(N+M) время заданного решения) путем сортировки и использования bisect:

ys = sorted(y)
def bisect_contains(seq, item):
    index = bisect.bisect(seq, item)
    return index < len(seq) and seq[index] == item
[item for item in x if bisect_contains(ys, item)]

---

Если ваши предметы не являются ни хешируемыми, ни сопоставимыми, значит, вы застряли с квадратичным решением.

---

_{* Обратите внимание, что вы также можете сделать это, используя пару объектов OrderedSet, для которых вы можете найти рецепты и сторонние модули. Но я думаю, что это проще.}

_{** Причина, по которой установленные поиски являются постоянными, состоит в том, что все, что нужно сделать, - это хэшировать значение и посмотреть, есть ли запись для этого хэша. Если он не может хэшировать значение, это не сработает.}

Answer 6

Поиск значений в наборах происходит быстрее, чем поиск в списках:

[item for item in x if item not in set(y)]

Я считаю, что это будет немного лучше, чем:

[item for item in x if item not in y]

Оба сохраняют порядок списков.

Answer 7

Попробуйте это.

def subtract_lists(a, b):
    """ Subtracts two lists. Throws ValueError if b contains items not in a """
    # Terminate if b is empty, otherwise remove b[0] from a and recurse
    return a if len(b) == 0 else [a[:i] + subtract_lists(a[i+1:], b[1:]) 
                                  for i in [a.index(b[0])]][0]

>>> x = [1,2,3,4,5,6,7,8,9,0]
>>> y = [1,3,5,7,9]
>>> subtract_lists(x,y)
[2, 4, 6, 8, 0]
>>> x = [1,2,3,4,5,6,7,8,9,0,9]
>>> subtract_lists(x,y)
[2, 4, 6, 8, 0, 9]     #9 is only deleted once
>>>

Answer 8

Если списки допускают дублирование элементов, вы можете использовать Счетчик из коллекций:

from collections import Counter
result = list((Counter(x)-Counter(y)).elements())

Answer 9

Я думаю, что это быстрее:

In [1]: a = [1,2,3,4,5]

In [2]: b = [2,3,4,5]

In [3]: c = set(a) ^ set(b)

In [4]: c
Out[4]: {1}

Answer 10

Ответ, предоставленный @aaronasterling, выглядит хорошо, однако он не совместим с интерфейсом списка по умолчанию: x = MyList(1, 2, 3, 4) против x = MyList([1, 2, 3, 4]). Таким образом, приведенный ниже код можно использовать как более дружественный для списка Python:

class MyList(list):
    def __init__(self, *args):
        super(MyList, self).__init__(*args)

    def __sub__(self, other):
        return self.__class__([item for item in self if item not in other])

Пример:

x = MyList([1, 2, 3, 4])
y = MyList([2, 5, 2])
z = x - y