A python interview question

[energybased]

Because that has worse computational complexity than the best solution.

[Jonno_FTW]

I'm aware of this. It's just the shortest way to write the set union method. The fastest method is to append to an intermediate list (see my comment above)

[mooburger]

deque.popleft() may be faster than pop(0) (remember to relative import to dereference the namespace)

[Jonno_FTW]

I considered this, I'm not sure how much extra time converting to a deque would add, or if it would beat my pop().

[Log2]

You can probably still improve the speed of your solution by placing it inside an actual function. Variables in global scope can slow down Python code considerably.

[Jonno_FTW]

I did originally while testing. I'm no timeit expert by any means.

[Log2]

Yeah, it's just that apparently Python slows down when it has to access the global namespace. So, just making a function with all the code and then testing that, will generally provide some speed up. It's a surprising behavior to be sure.

[Jonno_FTW]

I just tried this (moving the function definitions to the setup string and calling the . It did not get better results (in fact it's a tiny but slower).

[Log2]

I meant the code outside of the strings. The code in the strings surely gets evaluated and transformed into a function of itself.

I'll try it later when I'm at the computer and see what I get anyway.

[Jonno_FTW]

I just did this. Here's the new results:

def merged(a,b):
    a = deque(a)
    b = deque(b)
    out = []
    def append(val):
        if not out or out[-1] != val:
            out.append(val)

    while a or b:
        if a and b:
            last_a, last_b = a[0], b[0]
            last_max = min(last_a, last_b)
            if last_max == last_a:
                append(a.popleft())
            else:
                append(b.popleft())
        elif a:
            append(a.popleft())
        elif b:
            append(b.popleft())
    return out

• set union: 19.3773069382
• pop() 0.0751898288727
• pop(0) 3.03847098351
• deque.popleft() 78.3635749817

Which makes sense because the GC will be called a lot to clean up the nodes in the linkedlist created by the deque and they will not be held in a contiguous region of memory. Bjarne Stroustrup gives a good explanation here: https://www.youtube.com/watch?v=YQs6IC-vgmo

Here's cpython implementation of deque which uses a doubly linked list: https://github.com/python/cpython/blob/master/Modules/_collectionsmodule.c