Использование массивов с другими массивами в Python

Question

Попытка найти эффективный способ извлечения всех экземпляров элементов в массиве из другого.

Например

array1 = ["abc", "def", "ghi", "jkl"]

array2 = ["abc", "ghi", "456", "789"]

Массив 1 - это массив элементов, которые необходимо извлечь из массива 2. Таким образом, массив 2 следует изменить на ["456", "789"]

Я знаю, как это сделать, но не эффективно.

Answer 1

Это списки, а не массивы. (Слово «массив» означает разные вещи для разных людей, но в python объекты называют себя списками, и это все; есть другие модули, которые предоставляют объекты, называющие себя массивами, например array и NumPy )

Чтобы ответить на ваш вопрос, самый простой способ - вообще не изменять array2. Используйте понимание списка:

set1 = set(array1)
array2 = [e for e in array2 if e not in set1]

(множество делает это O (n) вместо O (n ^ 2))

Если вы абсолютно должны преобразовать массив2 (потому что он существует в другом месте), вы можете использовать назначение среза:

array2[:] =  [e for e in array2 if e not in set1]

Это так же эффективно, но отчасти неприятно.

edit : как отмечает Марк Байерс, это работает, только если array1 содержит только хешируемые элементы (такие как строки, числа и т. Д.).

Answer 2

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

>>> set1 = set(["abc", "def", "ghi", "jkl"])
>>> set2 = set(["abc", "ghi", "456", "789"])
>>> set2 - set1
set(['456', '789'])

Если list2 может содержать дубликаты или порядок имеет значение, вы все равно можете сделать list1 набором для ускорения поиска:

>>> list1 = ["abc", "def", "ghi", "jkl"]
>>> list2 = ["abc", "ghi", "456", "789"]
>>> set1 = set(list1)
>>> [a for a in list2 if a not in set1]
['456', '789']

Обратите внимание, что для этого требуется, чтобы элементы были хэшируемыми, но выполнялись в течение времени, близкого к O (n).

Если элементы не могут быть хешируемыми, но их можно заказать, вы можете отсортировать list1 и использовать двоичный поиск, чтобы найти элементы в нем. Это дает O (n log (n)) время.

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

Answer 3

Прямой путь будет примерно таким:

array2 = [i for i in array2 if i not in array1]

список пониманий - вот что вам нужно