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行。我正在寻找可以更好地利用内置itertools函数或esque库的功能，以缩短代码长度并加快运行速度（C本机）。

编辑：

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

总结一下以上几点：

• cmp用于比较的至关重要，因为它不是对基本相等性的测试。
• 结果是[(a, b)]，a应该是与中的元素之一相同的实例，As以及b在中的元素之一的相同实例Bs，前提是并非如此None。
• As和Bs中的元素不可散列。

Answer 1

我决定采用 @thg435 的答案和使用（编辑：更改为@EOL 指出的那样）之类的内容，这帮助我减少了原来的大量代码。deque list

我选择这个的原因如下：

• 时间复杂度计算简单且易于预测。
• 它不需要更改界面。
• 我觉得代码量和预期运行效率之间取得了很好的平衡。

实施如下：

def izip_pairs(xs, ys, cmp):
    xs = list(reversed(sorted(xs, cmp)))
    ys = list(reversed(sorted(ys, cmp)))

    while xs or ys:
        delta = ((not xs) - (not ys)) or cmp(xs[-1], ys[-1])

        x = xs.pop() if delta <= 0 else None
        y = ys.pop() if delta >= 0 else None
        yield x, y

为了比较：

受到每个人基于集合的答案的启发，为了进行比较，我更改了界面以适应并实现了基于哈希查找的解决方案。

def izip_keys(xs, ys, key):
    xs = {key(x): x for x in xs}
    ys = {key(y): y for y in ys}

    for k in set(xs.keys() + ys.keys()):
        yield xs.get(k, None), ys.get(k, None)

时间差异：

我对下面结果的结论是，对于较大数量的元素，排序列表上的循环可以更好地扩展，而哈希查找仅对于微小的Ns更快。

>>> xs = range(100, 200)
>>> ys = range(150, 250)
>>> xs = map(lambda n: tuple(range(n, n + 10)), xs)
>>> ys = map(lambda n: tuple(range(n, n + 10)), ys)

>>> def profile_pairing():
...     list(izip_pairs(xs, ys, lambda x, y: cmp(x[:4], y[:4])))
...
>>> def profile_keying():
...     list(izip_keys(xs, ys, lambda v: v[:4]))
...

>>> from timeit import Timer
>>> Timer(profile_pairing).timeit(1000)
0.575916051864624
>>> Timer(profile_keying).timeit(1000)
0.39961695671081543

>>> xs = map(lambda n: tuple(range(n, n + 10)), range(1000, 2000))
>>> ys = map(lambda n: tuple(range(n, n + 10)), range(1500, 2500))
>>> Timer(profile_pairing).timeit(100)
0.5289111137390137
>>> Timer(profile_keying).timeit(100)
0.4951910972595215

>>> xs = map(lambda n: tuple(range(n, n + 10)), range(10000, 20000))
>>> ys = map(lambda n: tuple(range(n, n + 10)), range(15000, 25000))
>>> Timer(profile_pairing).timeit(10)
0.6034290790557861
>>> Timer(profile_keying).timeit(10)
0.9461970329284668

>>> xs = map(lambda n: tuple(range(n, n + 10)), range(100000, 200000))
>>> ys = map(lambda n: tuple(range(n, n + 10)), range(150000, 250000))
>>> Timer(profile_pairing).timeit(1)
0.6421248912811279
>>> Timer(profile_keying).timeit(1)
1.253270149230957

（注：在所有情况下，使用deque* 代替，list(reverse(...))速度提高了 1%。*请参阅一些编辑内容）