Remove all the elements that occur in one list from another

Удалить все элементы, встречающиеся в одном списке, из другого

Допустим, у меня есть два списка, l1 и l2. Я хочу выполнить l1 - l2, который возвращает все элементы l1 not in l2.

Я могу придумать наивный циклический подход к выполнению этого, но это будет действительно неэффективно. Какой питонический и эффективный способ сделать это?

В качестве примера, если у меня есть l1 = [1,2,6,8] and l2 = [2,3,5,8], l1 - l2 должен вернуться [1,6]

Переведено автоматически

Ответ 1

В Python есть языковая функция под названием Понимание списков, которая идеально подходит для предельного упрощения подобных задач. Следующий оператор выполняет именно то, что вы хотите, и сохраняет результат в l3:

l3 = [x for x in l1 if x not in l2]

l3 будет содержать [1, 6].

Ответ 2

Один из способов - использовать наборы:

>>> set([1,2,6,8]) - set([2,3,5,8])
set([1, 6])

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

Ответ 3

Сравнение производительности

Сравниваем производительность всех ответов, упомянутых здесь, на Python 3.9.1 и Python 2.7.16.

Python 3.9.1

Ответы приведены в порядке производительности:

разница с использованием операции вычитания setArkku "-" - (91,3 нсек за цикл)

mquadri$ python3 -m timeit -s "l1 = set([1,2,6,8]); l2 = set([2,3,5,8]);" "l1 - l2"
5000000 loops, best of 5: 91.3 nsec per loop

используя Moinuddin Quadriset().difference()- (133 нсек за цикл)

mquadri$ python3 -m timeit -s "l1 = set([1,2,6,8]); l2 = set([2,3,5,8]);" "l1.difference(l2)"
2000000 loops, best of 5: 133 nsec per loop

понимание списка с помощью поиска на основеsetMoinuddin Quadri- (366 нсек за цикл)

 mquadri$ python3 -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "[x for x in l1 if x not in l2]"
 1000000 loops, best of 5: 366 nsec per loop

понимание списка в обычном списке Donut's - (489 нсек за цикл)

 mquadri$ python3 -m timeit -s "l1 = [1,2,6,8]; l2 = [2,3,5,8];" "[x for x in l1 if x not in l2]"
 500000 loops, best of 5: 489 nsec per loop

выражение генератора с поиском на основеsetДэниела Прайдена и приведением типа к list - (583 нсек за цикл) : Явное приведение типа к списку для получения конечного объекта как list, как запрошено OP. Если выражение генератора заменить на понимание списка, оно станет таким же, как у Мойнуддина Квадри понимание списка с set поиском на основе.
```
 mquadri$ mquadri$ python3 -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "list(x for x in l1 if x not in l2)"
 500000 loops, best of 5: 583 nsec per loop
```

используя Moinuddin Quadrifilter() и явно приводя тип в list (необходимо явно приводить тип, как в Python 3.x, он возвращает итератор) - (681 нсек за цикл)
```
 mquadri$ python3 -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "list(filter(lambda x: x not in l2, l1))"
 500000 loops, best of 5: 681 nsec per loop
```

используя комбинацию + functools.reduceАкшая Хазариfilter -(3,36 usec за цикл) : Явное приведение типа к list как из Python 3.x, он запустил возвращаемый итератор. Также нам нужно импортировать functools для использования reduce в Python 3.x
```
 mquadri$ python3 -m timeit "from functools import reduce; l1 = [1,2,6,8]; l2 = [2,3,5,8];" "list(reduce(lambda x,y : filter(lambda z: z!=y,x) ,l1,l2))"
 100000 loops, best of 5: 3.36 usec per loop
```

Python 2.7.16

Ответы приведены в порядке производительности:

разница с использованием операции вычитания setArkku "-" - (0,0783 сек за цикл)

mquadri$ python -m timeit -s "l1 = set([1,2,6,8]); l2 = set([2,3,5,8]);" "l1 - l2"
10000000 loops, best of 3: 0.0783 usec per loop

с помощью Moinuddin Quadriset().difference()- (0,117 сек на цикл)

mquadri$ mquadri$ python -m timeit -s "l1 = set([1,2,6,8]); l2 = set([2,3,5,8]);" "l1.difference(l2)"
10000000 loops, best of 3: 0.117 usec per loop

понимание списка с помощью поиска на основеsetМойнуддина Квадри - (0,246 секунды использования за цикл)
```
 mquadri$ python -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "[x for x in l1 if x not in l2]"
 1000000 loops, best of 3: 0.246 usec per loop
```

понимание списка в обычном списке Donut's - (0,372 секунды использования за цикл)

 mquadri$ python -m timeit -s "l1 = [1,2,6,8]; l2 = [2,3,5,8];" "[x for x in l1 if x not in l2]"
 1000000 loops, best of 3: 0.372 usec per loop

с помощью Moinuddin Quadrifilter() - (0,593 сек за цикл)

 mquadri$ python -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "filter(lambda x: x not in l2, l1)"
 1000000 loops, best of 3: 0.593 usec per loop

выражение генератора с поиском на основеsetДэниела Прайдена и приведением типа к list - (0,964 за цикл) : Явное приведение типа к списку для получения конечного объекта как list, как запрошено OP. Если выражение генератора заменить на понимание списка, оно станет таким же, как у Мойнуддина Квадри понимание списка с set поиском на основе.
```
 mquadri$ python -m timeit -s "l1 = [1,2,6,8]; l2 = set([2,3,5,8]);" "list(x for x in l1 if x not in l2)"
 1000000 loops, best of 3: 0.964 usec per loop
```

используя комбинацию + functools.reduceАкшая Хазариfilter -(2,78 сек за цикл)

 mquadri$ python -m timeit "l1 = [1,2,6,8]; l2 = [2,3,5,8];" "reduce(lambda x,y : filter(lambda z: z!=y,x) ,l1,l2)"
 100000 loops, best of 3: 2.78 usec per loop

Ответ 4

Расширяя ответ Donut и другие ответы здесь, вы можете получить еще лучшие результаты, используя понимание генератора вместо понимания списка и используя set структуру данных (поскольку in оператор равен O (n) в списке, но O (1) в наборе).

Итак, вот функция, которая будет работать для вас:

def filter_list(full_list, excludes):
    s = set(excludes)
    return (x for x in full_list if x not in s)

Результатом будет итерируемый файл, который будет лениво извлекать отфильтрованный список. Если вам нужен реальный объект списка (например, если вам нужно выполнить len() над результатом), то вы можете легко создать список следующим образом:

filtered_list = list(filter_list(full_list, excludes))