python - 如何比较两个列表并找出 `added` `deleted` `unchanged ` 部分

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