Сравнение двух списков по элементам

Question

У меня есть 2 списка, и я хочу сравнить эти списки по каждому элементу. Например:

a = [1,2,3] 
b = [2,3,1] 
for i in a: 
    if i in b: 
     pass # do something 
    else: 
     pass # do something else instead 

Я нахожу эту реализацию немного тривиальный.

Я хотел бы знать другие способы эффективного решения задачи.
(Эффективность подразумевает либо временную сложность или сложность пространства)

Answer 1

Вы можете использовать наборы, чтобы найти общие элементы a и b.

common_elements = set(a) & set(b) 
for item in a: 
    if item in common_elements: 
     pass # do something 
    else: 
     pass # do something else instead 

Набор конструкция O (N) в среднем случае, и установить тестирование членство O (1), что делает весь этот алгоритм O (N) в общей сложности. Для сравнения, тестирование членства для списков - O (N), поэтому ваш исходный алгоритм - O (N^2).

Answer 2

Мы можем использовать временный массив, чтобы проверить, присутствует ли каждый элемент a в b или нет. Этот размер этого массива должен быть больше максимального элемента, который может присутствовать в обоих списках (я искал, что максимальный размер списка Python в 32-битной системе равен 536,870,912, поэтому этот метод будет работать в обычных случаях). В этом временном списке temp_b будет каждый элемент равным нулю. Теперь, для всех целых чисел, присутствующих в списке b, мы инициализируем значение в этом индексе равным 1, указывая, что этот элемент присутствует в b. После этого все, что нам нужно сделать, это: для каждого элемента i в a, проверьте, temp_b[i] == 1? Если да, то элемент присутствует, иначе нет.

Обратите внимание, что для проверки того, соответствует ли частота каждого элемента в a также в b, мы должны будем изменить этот код. Сложность будет линейной по размеру массива.

a = [2, 5, 4, 7, 6, 8, 9] 
b = [1, 3, 6, 7, 4, 3, 0] 

temp_b = [0]*20 

for i in b: 
    temp_b[i] = 1 

#to check whether each element of a is present in b or not 
for i in a: 
    if temp_b[i] == 1: 
     #element is present 
     print "present" 
    else: 
     #element is not present 
     print "not present" 

Редактировать: Этот метод будет работать только для целых положительных чисел.

Answer 3

a, b = [1, 2, 3], [2, 3, 1] 
for i in map(lambda i:i in b,a): 
    if i == True: 
     # do someting 
    else: 
     # do other