6
\$\begingroup\$

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?

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Why is merge_no_duplicates a class? Can't it be just a function? \$\endgroup\$ – Caridorc Oct 20 '15 at 19:27
  • 1
    \$\begingroup\$ @Caridorc Yeah, it can. \$\endgroup\$ – Barry Oct 20 '15 at 19:32
  • \$\begingroup\$ regarding the deque: it seems that they should be faster than regular lists even if used only to append on the right: docs.python.org/3/library/collections.html#collections.deque \$\endgroup\$ – meto Oct 20 '15 at 19:47
  • \$\begingroup\$ @meto Where do you see that in the linked doc? \$\endgroup\$ – Barry Oct 20 '15 at 19:51
  • \$\begingroup\$ @meto Running a quick %%timeit test in ipython, I got lists to be about 20% faster than deques for only-right-appends. \$\endgroup\$ – Dougal Oct 21 '15 at 1:43
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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))
\$\endgroup\$
  • 1
    \$\begingroup\$ sorted is certainly not redundant, since set is not sorted. Also, because of the sort, this is O(n log(n)), while the OP's code is O(n) \$\endgroup\$ – njzk2 Oct 21 '15 at 1:17
  • \$\begingroup\$ The reason I think it is redundant is that I have only observed union() returning sets that are sorted. The documentation does not indicate this is guaranteed however. \$\endgroup\$ – pourhaus Oct 21 '15 at 3:14
  • \$\begingroup\$ set are not sorted. what you observed is a coincidence, linked to the fact that small integers tend to be inserted in ordered buckets. Example, on my machine right now set([1,2,3]) (appears to be ordered) but set([1, 1000]) prints {1000, 1}. Result may differ from an environment to the other. \$\endgroup\$ – njzk2 Oct 21 '15 at 4:07
  • \$\begingroup\$ Also even with sorted that means these results only return in sorted order, not the original order that the lists were in. \$\endgroup\$ – SuperBiasedMan Oct 21 '15 at 15:22
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "Saves time"? In what sense, lazyness when writing? Not in performance time if we're talking about lists of a non trivial small size. \$\endgroup\$ – holroy Oct 22 '15 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.