Как сравнить два списка и выяснить, `добавлен`` удален` `неизменен` часть

Question

Я хочу это:

def compare_list(old, new):
    new_set = set(new)
    old_set = set(old)
    return new_set - old_set, old_set - new_set, new_set & old_set

old = [1, 2, 3]
new = [5, 4, 2, 3]

added, deleted, unchanged = compare_list(old, new)

print("added: ", added)
print("deleted: ", deleted)
print("unchanged: ", unchanged)

---

added:  {4, 5}
deleted:  {1}
unchanged:  {2, 3}

Но, похоже, это очень плохая эффективность для меня. Итак, я хочу узнать более эффективное решение? или встроить функцию?

Answer 1

В Python вы можете получить дополнительную скорость, сравнивая меньшее пересечение с двумя большими списками, а не сравнивая их друг с другом.

def compare_list2(old, new):
    new_set = set(new)
    old_set = set(old)
    inter = new_set & old_set
    return new_set - inter, old_set - inter, inter

old = [1, 2, 3]
new = [5, 4, 2, 3]

#%time added, deleted, unchanged = compare_list(old, new)
start_time = time.time()
for i in range(10000000):
    compare_list2(old, new)
print("--- %s seconds ---" % (time.time() - start_time))

На 0,3 с быстрее, чем ваша функция, только вычисляя пересечение один раз и использование его дважды.

--- 6.982441663742065 seconds ---
vs
--- 7.270233154296875 seconds ---

Что касается сложности времени, у нас еще есть три прохода по данным. Мы могли бы сначала отсортировать, а затем сделать один проход, что дает O(n log n). Python псевдокод, который намного медленнее, но реализация C подойдет. После сортировки это будет O(n).

def compare_single_pass(old,new):
    new_set = sorted(new)
    old_set = sorted(old)
    added, deleted, unchanged = [],[],[]
    i, j = 0, 0
    j_max = len(old_set)
    i_max = len(new_set)
    while True:
        if i == i_max and j == j_max:
            return added, deleted, unchanged
            break
        if j == j_max:
            added.append(new_set[i])
            i += 1
            continue
        if i == i_max:
            deleted.append(old_set[j])
            j += 1
            continue
        if new_set[i] < old_set[j]:
            added.append(new_set[i])
            i += 1
            continue
        if new_set[i] == old_set[j]:
            unchanged.append(new_set[i])
            i += 1
            j += 1
            continue
        if new_set[i] > old_set[j]:
            deleted.append(old_set[j])
            j += 1
            continue