Python: Fast and minimalistic way to zip and pair matching elements in two lists
<p>I have:</p>

<pre><code>&gt;&gt;&gt; As = [1, 2, 5, 6]
&gt;&gt;&gt; Bs = [2, 3, 4, 5]
</code></pre>

<p>I want something like <code>zip_fn</code> below:</p>

<pre><code>&gt;&gt;&gt; Rs = zip_fn(As, Bs, cmp)
&gt;&gt;&gt; Rs
[(1, None), (2, 2), (None, 3), (None, 4), (5, 5), (6, None)]
</code></pre>

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

<p>Some points:</p>

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

<p>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 <code>itertools</code>esque libraries for shorter code and faster (C native) running.</p>

<p><strong>Edit:</strong></p>

<p>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 <code>cmp</code> tests only a part of the tuple for equality.  It might be easier to think of the elements as being <em>records</em> and <code>cmp</code> as something that matches on the <em>key fields</em>.  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.</p>

<p>Summarizing this as additional points to the some above:</p>

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