Python: Fast and minimalistic way to zip and pair matching elements in two lists

Question

I have:

>>> As = [1, 2, 5, 6]
>>> Bs = [2, 3, 4, 5]

I want something like zip_fn below:

>>> Rs = zip_fn(As, Bs, cmp)
>>> Rs
[(1, None), (2, 2), (None, 3), (None, 4), (5, 5), (6, None)]

In other words, given two arbitrary sequences As and Bs, I want to produce a list of tuples Rs such that choices that satisfy cmp(a, b) == 0 are paired together into their own tuple (a, b), but those in As and Bs without matching counterparts are output as (a, None) and (None, b) respectively.

Some points:

• I'm not worried about duplicates in As or Bs as there won't be any.
• Rs can be an iterator that produces the same sequence.
• The ordering of Rs is unimportant.

I've already implemented something that satisfies the functional requirement using straight-forward presorted looping but it's roughly 30 lines. I'm looking for something that makes better use of builtins or itertoolsesque libraries for shorter code and faster (C native) running.

Edit:

I should have made this clearer. Although I used a list of plain numbers in the example above for brevity, the elements I'm actually working with are tuples, and cmp tests only a part of the tuple for equality. It might be easier to think of the elements as being records and cmp as something that matches on the key fields. I could wrap the elements in a class and make it hashable on the key, but such a set up isn't required for anything else so any solution that requires this will get this as additional code and runtime overhead.

Summarizing this as additional points to the some above:

• It's vital that cmp is used for comparison as it's not a test for basic equality.
• In the result [(a, b)], a should be the same instance as one of the elements in As and b the same instance of one of the elements in Bs, provided they aren't None.
• Elements in As and Bs aren't hashable.

Answer 1

I guess this is similar to what you already have:

from collections import deque

def pairs(xs, ys):
    xs = deque(sorted(xs))
    ys = deque(sorted(ys))

    while xs and ys:
        c = cmp(xs[0], ys[0])
        if c == 0:
            yield xs.popleft(), ys.popleft()
        elif c < 0:
            yield xs.popleft(), None
        else: # c > 0:
            yield None, ys.popleft()

    for x in xs: yield x, None
    for y in ys: yield None, y


xs = [1, 2, 5, 6]
ys = [2, 3, 4, 5]        
print list(pairs(xs, ys))
# [(1, None), (2, 2), (None, 3), (None, 4), (5, 5), (6, None)]