Merge two list and discarding duplicates

Question

I am trying to implement a function that merges two ordered lists into a third (ordered) one, but duplicates have to be discarded (basically the last step of a mergesort).

I think that this code can be generalized to an arbitrary number or lists, by keeping a list of indices, rather than 2 explicit ones.

def merge_no_duplicates(list_1, list_2):
    i = j = 0
    import collections
    result = collections.deque()

    while i < len(list_1) and j < len(list_2):
        if len(result) > 1 and list_1[i] == result[-1]:
            i += 1
            continue
        if len(result) > 1 and list_2[j] == result[-1]:
            j += 1
            continue

        if list_1[i] <= list_2[j]:

            result.append(list_1[i])
            i += 1
        elif list_2[j] < list_1[i]:
            result.append(list_2[j])
            j += 1

    # we still need to consume part of list_2
    if i == len(list_1):
        while j < len(list_2):

            if list_2[j] == result[-1]:
                j += 1
                continue 

            result.append(list_2[j])
            j += 1

    # still need to consume part of list_1
    if j == len(list_2):
        while i < len(list_1):

            if list_1[i] == result[-1]:
                i += 1
                continue 

            result.append(list_1[i])
            i += 1
    return result

Possible improvements: factor out the repetitive parts, for example by using something similar to this helper function:

check_duplicates(my_list, index):
    if my_list[index] == result[-1]:
        index += 1

Unfortunately this won't work (index is a parameter, and will not influence the behavior of i or j). Is this possible at all?

Answer 1

Pick a good return type

A deque is a Double Ended QUEue. Deques are great for when you have to insert and erase from the front as well as the back. You never need this for your problem - all you ever need is to insert at the end. You just need a normal list.

Generate when you can

Rather than necessarily giving the entire result all at once, it's better to just yield the next element as you go. This is a simple change in your algorithm (just yield x instead of result.append(x)), but could have serious performance implications down the line if you have lots of large iterables. If the caller wants a full list, then can always explicitly write list(merge_no_duplicates(a, b, c)).

Use the standard when you can

There is a function that already merges sorted inputs into a single sorted output: heapq.merge. It will give you duplicates, but that seems like a much better starting point than writing everything from scratch:

def merge_no_duplicates(*iterables):
    last = object()

    for val in heapq.merge(*iterables):
        if val != last:
            last = val
            yield val

If you don't want to use heapq.merge, then you can at least use this framework to separate the "merge sorted iterables" concern from the "remove duplicates" concern.

Answer 2

Code refactor suggestion

A possible better approach would be to use something along the lines of:

• Let method accept a list of lists
• Create iterators for each of list
• Repeat following until no more elements:
  • Compare current element of all list
    • Push minimum to result list, iterate this list
    • Remove duplicates if any, and iterate corresponding list
• Return the resulting list

This should do the trick rather efficiently as well as elegantly. Will possibly code it later on, but just now I'm a little busy. But just thought I would give you something to think about regarding how to improve it.

Update: No need to reinvent the wheel, so please do use (and/or accept) code example provided by Barry. Will maybe code it just for the exercise, but most likely using heapq.merge, or some union-variant, will be a better implementation.

Answer 3

Sometimes the code to do what you want is already there. If you think about what is like a list and supports the operation you want to perform.

Convert both lists to sets, use union(), then convert back to a list. I think the sorted() is redundant BTW:

def merge_no_duplicates(iterable_1, iterable_2):
    myset = set(iterable_1).union(set(iterable_2))
    return sorted(list(myset))

list1 = [0, 2, 6, 'dup']
list2 = [9, 1, 3, 6, 7, 'dup']

print("Sorted union as list =", merge_no_duplicates(list1, list2))

Answer 4

Hmmm, objects in an ordered list.... Are we overthinking?

def combine_remove_and_sort(list1, list2):
    return sorted(list(set(list1+list2)))

Kinda lazy but saves time for the really complex problems.