Python：在两个列表中压缩和配对匹配元素的快速和最小化方法

Question

我有：

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

我想要下面的zip_fn：

^{pr2}$

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

一些要点：

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

我已经实现了一些满足功能需求的东西，使用直接的预排序循环，但它大约有30行。我正在寻找一种能更好地利用内置函数或itertools式库的东西，以获得更短的代码和更快的（C本机）运行。在

编辑：

我应该说得更清楚些。尽管为了简洁起见，我在上面的示例中使用了一系列普通数字，但我实际使用的元素是元组，cmp只测试元组的一部分是否相等。将元素看作是记录和cmp是匹配键字段的东西可能更容易。我可以将元素包装在一个类中并使其在键上散列，但是这样的设置对于其他任何东西都是不需要的，所以任何需要这样做的解决方案都会得到额外的代码和运行时开销。在

作为以上几点的补充：

• 重要的是，cmp用于比较，因为它不是基本相等的测试。在
• 在结果[(a, b)]，a应该与As中的一个元素是相同的实例，b是{}中某个元素的同一实例，前提是它们不是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)]

Answer 2

我知道这并没有考虑cmp()操作，但希望它能有所帮助。在

>>> As = [1, 2, 5, 6]
>>> Bs = [2, 3, 4, 5]
>>> result = []
>>> for n in set(As + Bs):
...     result.append((n if n in As else None, n if n in Bs else None))
...
>>> result
[(1, None), (2, 2), (None, 3), (None, 4), (5, 5), (6, None)]
>>>

和列表比较一样：

^{pr2}$

Answer 3

([(i,j) for i in As for j in Bs if cmp(i,j) == 0] +
[(i,None) for i in As if all(cmp(i,j) !=0 for j in Bs)] +
[(None, j) for j in Bs if all(cmp(i,j) !=0 for i in As)])

但是，时间复杂度将是n^2，因为我们无法根据您的描述判断一个元素是否比另一个元素大。在