быстрое вычитание списка для большого списка с порядком o (n) в python

Question

У меня есть два больших списка строк в Python.Я хочу вычесть эти два списка быстро с порядком o (n).Я нашел какой-то способ, например удалить вторые элементы списка в цикле из первого списка, или преобразовать список в set () (проблема: изменить порядок в списке) и использовать оператор минус (-), но эти методы неэффективны.Есть ли способ сделать эту операцию?

a=['1','2','3',...,'500000']
b=['1','2','3',...,'200000']

c=a-b

c=['200001','200002',...,'500000']

Answer 1

Ваша проблема в том виде, как она сформулирована:

• Пройдите через A
• Для каждого элемента найдите его в B и возьмите, если он не найден
• Не сделано никаких предположений об элементах

Для произвольных данных поиск по списку - O (N), поиск по множеству - O (1), преобразование в набор - по O (N). Прохождение через A - это O (N).

Так что это O (N ^ 2) только со списками и O (N) при преобразовании B в набор.

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

• В вашем примере ваши данные являются последовательными числами, поэтому вы можете взять A[len(B):].
• Если вы собираетесь использовать один и тот же B несколько раз, вы можете кэшировать набор
• Вы можете сделать набор B сразу же (если необходимо сохранить порядок, вы можете использовать заказанный набор )
• Если все данные относятся к одному типу и являются короткими, вы можете использовать numpy массивы и их быстрое setdiff1d
• и т.д.