Python:在两个列表中压缩和配对匹配元素的快速且简约的方法

Question

我有:

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

我想要下面类似 zip_fn 的东西:

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

换句话说，给定两个任意序列 As 和 Bs，我想生成一个元组列表 Rs 以便选择满足cmp(a, b) == 0 被配对到它们自己的元组 (a, b) 中，但是那些在 As 和 Bs 没有匹配的对应项分别输出为 (a, None) 和 (None, b)。

几点:

• 我不担心 As 或 Bs 中的重复项，因为不会有任何重复项。
• Rs 可以是生成相同序列的迭代器。
• Rs 的顺序不重要。

我已经使用直接的预排序循环实现了满足功能要求的东西，但它大约有 30 行。我正在寻找可以更好地利用内置函数或 itertoolsesque 库来缩短代码和加快(C 原生)运行速度的东西。

编辑:

我应该更清楚地说明这一点。尽管为了简洁起见，我在上面的示例中使用了纯数字列表，但我实际使用的元素是元组，cmp 仅测试元组的一部分是否相等。将元素视为 records 并将 cmp 视为与 key fields 匹配的东西可能更容易。我可以将元素包装在一个类中，并使其在键上可散列，但其他任何东西都不需要这样的设置，因此任何需要它的解决方案都会将其作为额外的代码和运行时开销。

将此总结为以上几点的补充:

• cmp 用于比较很重要，因为它不是基本相等性测试。
• 在结果 [(a, b)] 中，a 应该与 As 和 b Bs 中元素之一的相同实例，前提是它们不是 None。
• As 和 Bs 中的元素不可哈希。

Answer 1

我想这与您已有的类似:

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)]