I want this:
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}
But it seems is very bad efficiency for me. So I want to know any more efficient solution? or build in function?
In Python you could get extra speed by comparing the smaller intersection to the two larger lists rather than comparing them against each other.
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))
Is upto 0.3s faster than your function by only calculating the intersection once and using it twice.
--- 6.982441663742065 seconds ---
vs
--- 7.270233154296875 seconds ---
With respect to time complexity, we still have three passes over the data. We could sort first and then do a single pass, which yiels O(n log n).
Python pseudocode, which is much slower but a C implementation would do. After sorting, this would be 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