1
\$\begingroup\$

Thus code uses a mergesort-like algorithm to perform an outer join (in the database sense) on two sequences. (It's derived from the ActiveState recipe mentioned in the docstring.)

The actual algorithm is completely obscured by the extra code required to handle the possibility that either of the main iterators might throw StopIteration at any time. I've written almost-but-not-quite-exactly the same tail handling code four times. Surely there must be a less repetitive way to express this algorithm? But I can't think of anything. Even nested functions don't seem like they would help.

(In case it's not clear, the problem all this extra code is solving is that, if one input list is shorter than the other, we have to process the remaining elements of the long list after the short list is exhausted. This can manifest at any call to next() and the recovery logic is just different enough in each case that I'm not seeing how to factor out the except clauses.)

Note 1: The official relational-algebra definition of this algorithm assumes repeated keys can happen, but in my particular application they can't and I'd kinda like to get rid of the extra complexity involved in dealing with them.

Note 2: In my particular application R and S are one-shot iterables, and they can produce hundreds of thousands of elements each, but not millions.

def merge_outer_join(R, S, key, val):
    """Perform an outer join on R and S.  Abstractly, this pairs up
    the elements of R and S by key(x), and yields 3-tuples
    (key(rx or sx), val(rx), val(sx)), in sorted order.
    If some elements of R lack matching elements in S, or
    vice versa, then the missing val() is replaced with a None.

    Example:

        list(merge_outer_join([(1,'a'), (3,'b')], [(1,'x'), (2,'y')],
                              key=lambda x: x[0],
                              val=lambda x: x[1]))
        -->
        [(1,'a','x'), (2,None,'y'), (3,'b',None)]

    Corrected, Py3k-ified, and simplified from
    https://code.activestate.com/recipes/492216/"""

    from itertools import groupby, zip_longest
    from operator import itemgetter, concat

    R_grouped = groupby(sorted((key(r), val(r)) for r in R),
                        key=itemgetter(0))
    S_grouped = groupby(sorted((key(s), val(s)) for s in S),
                        key=itemgetter(0))

    # Initial boundary conditions: if either list was empty, the outer
    # join is just the contents of the other list.
    try:
        rk, rvs = next(R_grouped)
    except StopIteration:
        for sk, svs in S_grouped:
            for _,sv in svs:
                yield sk, None, sv
        return

    try:
        sk, svs = next(S_grouped)
    except StopIteration:
        for _,rv in rvs:
            yield rk, rv, None
        for rk, rvs in R_grouped:
            for _,rv in rvs:
                yield rk, rv, None
        return

    # Main loop. We have to watch out for either or both iterators
    # running out on us at any time.
    while True:
        if rk == sk:
            for (_,rv), (_,sv) in zip_longest(rvs, svs, 
                                              fillvalue=(None,None)):
                yield rk, rv, sv

            try:
                rk, rvs = next(R_grouped)
            except StopIteration:
                for sk, svs in S_grouped:
                    for _,sv in svs:
                        yield sk, None, sv
                return

            try:
                sk, svs = next(S_grouped)
            except StopIteration:
                for _,rv in rvs:
                    yield rk, rv, None
                for rk, rvs in R_grouped:
                    for _,rv in rvs:
                        yield rk, rv, None
                return

        elif rk < sk:
            for _,rv in rvs:
                yield rk, rv, None

            try:
                rk, rvs = next(R_grouped)
            except StopIteration:
                for _,sv in svs:
                    yield sk, None, sv
                for sk, svs in S_grouped:
                    for _,sv in svs:
                        yield sk, None, sv
                return

        else:
            for _,sv in svs:
                yield sk, None, sv

            try:
                sk, svs = next(S_grouped)
            except StopIteration:
                for _,rv in rvs:
                    yield rk, rv, None
                for rk, rvs in R_grouped:
                    for _,rv in rvs:
                        yield rk, rv, None
                return
\$\endgroup\$
2
\$\begingroup\$

The following assumes that both iterables are sorted and not grouped.

Consider getting different exception, depending on which list runs out:

class StopS(Exception): pass
class StopR(Exception): pass

Define a wrapper

def get_next(iterable, exception):
    try:
        return next(iterable)
    except StopIteration:
        raise exception

and replace naked calls to next(S) and next(R) with get_next(S, StopS) and get_next(R, StopR) respectively.

Now you can get rid of duplicated code:

def outer_join(R, S):
    try:
        from_S = get_next(S, StopS)
        from_R = get_next(R, StopR)
        while True:
            if from_S[0] == from_R[0]:
                yield (from_S[0], from_S[1], from_R[1])
                from_S = get_next(S, StopS)
                from_R = get_next(R, StopR)
            elif from_S[0] < from_R[0]:
                yield (from_S[0], None, from_S[1])
                from_S = get_next(S, StopS)
            else:
                yield (from_R[0], from_R[1], None)
                from_R = get_next(R, StopR)
    except StopS:
        while True:
            yield (from_R[0], from_R[1], None)
            from_R = next(R)
    except StopR:
        while True:
            yield (from_S[0], None, from_S[1])
            from_S = next(S)

Notice that terminating loops do use naked next to deliver StopIteration to caller.

This is a skeleton, of course. Some care need to be exercised to not yield None or a repeated value from StopS clause.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You were missing a : after the else in the while loop. Also your Nones were all at the wrong positions (swap all None with the value being yielded next to it). For timings including this code, see my answer. Your code trumps both mine and zwol's implementation. \$\endgroup\$ – Graipher Sep 17 '16 at 8:29
  • \$\begingroup\$ You have some bugs: If list S is empty on entry, this code goes directly to the except StopS clause and attempts to yield values from from_R which has not yet been initialized. Similarly, if list S is exhausted immediately after from_S[0] == from_R[0] was true, you emit the current value from list R twice. I think I can patch it up, though. \$\endgroup\$ – zwol Sep 19 '16 at 16:12
1
\$\begingroup\$

This seems indeed like a lot of hassle just to keep it generators throughout. If your number of elements is not too big, you could just use a dict like this:

def outer_join(iter1, iter2):
    d1 = dict(iter1)
    d2 = dict(iter2)
    for key in sorted(set(d1) | set(d2)):
        yield key, d1.get(key, None), d2.get(key, None)

Where the sorted is kind of assumed (because this is what your implementation also seems to do).

This is of course less memory-efficient (because all values are in memory in the dicts). But before writing the generic generator, I would try whether this is not already enough performance-wise.

However, your algorithm also has to touch and store all values once in the beginning (to do the groupby). So maybe it is not worse after all.

This algorithm does, however, deal differently with repeated keys:

>>> list(merge_outer_join([(1,'a'), (5, "k"), (3,'b')], [(1,'x'), (3, "z"), (3,'y')], key=lambda x: x[0], val=lambda x: x[1]))
[(1, 'a', 'x'), (3, 'b', 'y'), (3, None, 'z'), (5, 'k', None)]

>>> list(outer_join([(1,'a'), (5, "k"), (3,'b')], [(1,'x'), (3, "z"), (3,'y')]))
[(1, 'a', 'x'), (3, 'b', 'y'), (5, 'k', None)]

I'm not sure which way is the right way to deal with that, but I think your way is at least wrong that it pairs of (3, 'b', 'y'), instead of (3, 'b', 'z'), because 'z' actually comes first in order.

But if the key is really like an ID in a database, there should be no duplicates, anyway.


Some timing tests:

Boilerplate code to do testing:

import time
from itertools import cycle
from string import ascii_lowercase, ascii_uppercase

# function definition

if __name__ == "__main__":
    n = 10000000

    start = time.perf_counter()
    gen = merge_outer_join(zip(range(0,n,2),cycle(ascii_lowercase)), zip(range(1, n, 2), cycle(ascii_uppercase)), key=lambda x: x[0],val=lambda x: x[1])
    next(gen)
    print(time.perf_counter() - start)

    start = time.perf_counter()
    gen = merge_outer_join(zip(range(0,n,2),cycle(ascii_lowercase)), zip(range(1, n, 2), cycle(ascii_uppercase)), key=lambda x: x[0],val=lambda x: x[1])
    for x in gen:
        pass
    print(time.perf_counter() - start)

The first part measures the initialization time to get to the first element. The second part does a no-op through the generator.

Here are the results (average of 3) for a 10,000,000 long iter1 and iter2:

          init  pass
zwol      3.15  7.89
graipher  2.90  6.90
vnp       2e-5  4.28
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ The lists are actually so long that I would rather like to go in the opposite direction and get rid of the groupby(). They would still need to be sorted, but it would at least cut down on scratch objects. \$\endgroup\$ – zwol Sep 16 '16 at 21:14
  • \$\begingroup\$ @zwol Yeah, I was afraid of that. Still I think my approach should not be worse than yours, both will take the longest time sorting the keys...Would be nice if you could try them on a realistic input and see which one is faster. \$\endgroup\$ – Graipher Sep 16 '16 at 21:16
  • \$\begingroup\$ The computer with all the data on it is currently tied up with something else, but I can experiment with that tomorrow, probably. Your algorithm is certainly easier to read! \$\endgroup\$ – zwol Sep 16 '16 at 21:19

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.