6

我有：

>>> 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一起配对成它们自己的 tuple (a, b)，但是那些匹配As和Bs不匹配的选项分别输出为(a, None)和(None, b)。

几点：

  • 我不担心重复As或Bs不会有任何重复。
  • Rs可以是产生相同序列的迭代器。
  • 的顺序Rs并不重要。

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

编辑：

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

将其总结为上述几点的补充：

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

5 回答 5

2

我想这与您已经拥有的类似：

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)]
于 2012-07-11T06:22:57.787 回答
1 
([(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，因为根据您的描述，我们无法判断一个元素是否大于另一个元素。

于 2012-07-11T06:50:01.120 回答
1

我意识到这没有考虑到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)]
>>>

与列表组合相同：

>>> result = [ (n if n in As else None, n if n in Bs else None) for n in set(As + Bs)]
>>> result
[(1, None), (2, 2), (None, 3), (None, 4), (5, 5), (6, None)]
>>>
于 2012-07-11T05:37:30.480 回答
1

这个怎么样：

As = set([1, 2, 5, 6])
Bs = set([2, 3, 4, 5])
values = [(a, a) if a in Bs else (a, None) for a in As] + [(None, b) for b in Bs if b not in As]
>>> values
[(1, None), (2, 2), (5, 5), (6, None), (None, 3), (None, 4)]

或使用集合：

>>> values = [(a, a) for a in As.intersection(Bs)] + [(a, None) for a in As - Bs] + [(None, b) for b in Bs - As]
>>> values
[(2, 2), (5, 5), (1, None), (6, None), (None, 3), (None, 4)]
>>>

我不担心 As 或 Bs 中的重复项，因为不会有任何重复项。

所以 make then sets 给出了几乎恒定的查找时间。

Rs 的顺序并不重要。

所以我们可以检查 A 然后简单地检查 B :)

我不知道这是否正确，这只是我的想法，如果有问题我表示歉意。

更新
这有点更具挑战性，因为我们不能散列它，我们基本上被困在 O(n**2) 抱歉:(

我试图使其尽可能优化。

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

indicies_a, indicies_b, values = [], [], []
for index_a, a in enumerate(As):
    for index_b, b in enumerate(Bs):
        if cmp(a, b) == 0:
            values.append((a, b))
            indicies_a.append(index_a) 
            indicies_b.append(index_b)

values += [(As[index], None) for index in set(range(len(As))) - set(indicies_a)] + [(None, Bs[index]) for index in set(range(len(Bs))) - set(indicies_b)]

>>> values
[(2, 2), (5, 5), (1, None), (6, None), (None, 3), (None, 4)]
>>>

抱歉，我想不出更简洁的版本，我尽量让我的背心尽可能快。

于 2012-07-11T05:31:46.627 回答
0

我决定使用类似@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* 而不是1% 的速度快。*请参阅后面的一些编辑）list(reverse(...))

于 2012-07-11T08:35:17.437 回答