Вопрос:

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

python list

268964 просмотра

13 ответа

34351 Репутация автора

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

>>> 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. Каков наилучший способ сделать это?

Автор: daydreamer Источник Размещён: 06.08.2010 11:43

Ответы (13)


211 плюса

16132 Репутация автора

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

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

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

Автор: quantumSoup Размещён: 06.08.2010 11:45

34 плюса

8959 Репутация автора

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

В 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])
Автор: Santa Размещён: 06.08.2010 11:46

279 плюса

52016 Репутация автора

Решение

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

[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   

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

Автор: aaronasterling Размещён: 07.08.2010 12:19

2 плюса

29 Репутация автора

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

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
>>>
Автор: user3435376 Размещён: 22.08.2013 02:06

31 плюса

3380 Репутация автора

Если дубликаты и заказы являются проблемой:

[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]
Автор: nguyên Размещён: 28.11.2013 06:49

19 плюса

268004 Репутация автора

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

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

Это гибрид между ответом aaronasterling в и ответ quantumSoup в .

Версия aaronasterling выполняет len(y)сравнение элементов для каждого элемента x, поэтому требуется квадратичное время. В версии QuantumSoup используются наборы, поэтому для каждого элемента выполняется поиск по одному набору с постоянным временем, 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объектов, для которых вы можете найти рецепты и сторонние модули. Но я думаю, что это проще.

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

Автор: abarnert Размещён: 18.12.2014 02:33

7 плюса

858 Репутация автора

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

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

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

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

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

Автор: rudolfbyker Размещён: 21.07.2015 02:44

-1 плюса

17 Репутация автора

Этот пример вычитает два списка:

# List of pairs of points
list = []
list.append([(602, 336), (624, 365)])
list.append([(635, 336), (654, 365)])
list.append([(642, 342), (648, 358)])
list.append([(644, 344), (646, 356)])
list.append([(653, 337), (671, 365)])
list.append([(728, 13), (739, 32)])
list.append([(756, 59), (767, 79)])

itens_to_remove = []
itens_to_remove.append([(642, 342), (648, 358)])
itens_to_remove.append([(644, 344), (646, 356)])

print("Initial List Size: ", len(list))

for a in itens_to_remove:
    for b in list:
        if a == b :
            list.remove(b)

print("Final List Size: ", len(list))
Автор: Joao Nicolau Размещён: 13.01.2017 03:24

1 плюс

28 Репутация автора

Ответ предоставляется @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
Автор: Hamid Zafar Размещён: 26.09.2017 08:18

1 плюс

91 Репутация автора

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

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}
Автор: Eds_k Размещён: 23.01.2018 12:24

1 плюс

11866 Репутация автора

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

from collections import Counter
result = list((Counter(x)-Counter(y)).elements())
Автор: Alain T. Размещён: 06.03.2019 03:53

0 плюса

1036 Репутация автора

Я думаю, что самый простой способ добиться этого - использовать set ().

>>> x = [1,2,3,4,5,6,7,8,9,0]  
>>> y = [1,3,5,7,9]  
>>> list(set(x)- set(y))
[0, 2, 4, 6, 8]
Автор: Loochie Размещён: 11.08.2019 08:33

0 плюса

72551 Репутация автора

Другие решения имеют одну из нескольких проблем:

  1. Они не сохраняют порядок, или
  2. Они не удаляют точное количество элементов, например, for x = [1, 2, 2, 2]и y = [2, 2]преобразуют yв a set, и либо удаляют все совпадающие элементы (оставляя [1]только), либо удаляют один из каждого уникального элемента (оставляя [1, 2, 2]), когда правильное поведение будет удалять 2дважды, оставляя [1, 2]или
  3. Они O(m * n)работают, где оптимальное решение может O(m + n)работать

Ален был на правильном пути,Counter чтобы решить # 2 и # 3, но это решение потеряет порядок. Решение, которое сохраняет порядок (удаление первых nкопий каждого значения для nповторений в listзначениях для удаления):

from collections import Counter

x = [1,2,3,4,3,2,1]  
y = [1,2,2]  
remaining = Counter(y)

out = []
for val in x:
    if remaining[val]:
        remaining[val] -= 1
    else:
        out.append(val)
# out is now [3, 4, 3, 1], having removed the first 1 and both 2s.

Попробуйте онлайн!

Построение Counterвыражается O(n)в единицах yдлины, итерации x- O(n)в единицах xдлины, а Counterтестирование членства и мутации O(1), пока list.appendамортизируются O(1)(данные appendмогут быть O(n), но для многих appendс, общие средние значения big-O, O(1)так как все меньше и меньше из них требуют перераспределения), поэтому общая работа сделана O(m + n).

Вы также можете проверить, чтобы определить, были ли какие-либо элементы y, которые не были удалены xпутем тестирования:

remaining = +remaining  # Removes all keys with zero counts from Counter
if remaining:
    # remaining contained elements with non-zero counts
Автор: ShadowRanger Размещён: 06.09.2019 06:42
Вопросы из категории :
32x32