1

众所周知，如果我们在 python 中有两个列表l1和，l2可以使用zip(l1, l2)它来创建一个元组列表。l1l2

现在，假设我们有两个函数f1和f2. 我想创建一个元组列表，其中包含元素 froml1和l2（如zip输出），这样元素 from的输出将等于f1元素 from的输出。以数学形式：l1f2l2

在此处输入图像描述

在我的用例中，可以假设f1和f2都是单射函数。但是，不能保证 的每个元素l1都匹配，l2反之亦然。

这是执行此操作的代码：

from itetools import product

tuples_list = [
    (e1, e2)
    for e1, e2 in product(l1, l2)
    if f1(e1) == f2(e2)
]

我想知道是否有更好的方法（也许它已经以更快/更清洁的方式在内置库中实现）。

任何帮助将非常感激。

4

3 回答 3

2

如果您的函数计算成本很高，您可能需要在执行产品之前预先计算 f1 和 f2。您可以计算 N+M 次，而不是计算函数 NxM 次。你可以做

l1_out = [(f1(el_l1), el_l1) for el_l1 in l1]
l2_out = [(f1(el_l2), el_l2) for el_l2 in l2]

tuples_list = [(x[1], y[1]) for x in l1_out for y in l2_out if x[0] == y[0]]
于 2021-09-12T16:45:36.077 回答
2

请考虑itertools.product本质上是嵌套循环的包装器。因此，不需要外部模块的解决方案是：

tuples_list = [
    (e1, e2)
    for e1 in l1
    for e2 in l2
    if f1(e1) == f2(e2)
]

但是，该解决方案仍然可以优化。由于您使用笛卡尔积，这意味着您要为每个输入值多次重新计算f1和函数，这意味着您增加了不必要的复杂性。f2您可以缓存函数的输出值，我更快的解决方案是：

lf1 = [f1(v) for v in l1]
lf2 = [f2(v) for v in l2]

tuples_list = [
    (l1[i1], l2[i2])
    for i1, fe1 in enumerate(lf1)
    for i2, fe2 in enumerate(lf2)
    if fe1 == fe2
]
于 2021-09-12T16:27:11.487 回答
0

我喜欢 Rui Reis 和 SMeznaric 发布的解决方案，他们启发了我编写自己的解决方案。

我的解决方案不太直观，但我认为它运行得更快。

代码：

def find_pairs(l1, l2, f1, f2):
    d = {}
    for e1 in l1:
        d[f1(e1)] = e1

    tuples_list = []
    for e2 in l2:
        if f2(e2) in d:
            tuples_list.append((d[f2(e2)], e2))

    return tuples_list

说明：

  1. 创建一个空字典。
  2. 用 [f1, e1] 对填充字典。也就是说，对于列表l1中的每个元素e1，计算函数f1的值。该值 ( f1 ) 将是字典的键，元素本身 ( e1 ) 将是值。请注意，这只需要通过第一个列表。
  3. （关键部分）现在，我们通过 list l2。对于列表l2中的每个元素e2，我们计算函数f2的值。现在我们检查这个计算出的函数值是否已经存在于我们的字典中。这个操作是O(1)快！（https://wiki.python.org/moin/TimeComplexity）。如果字典中已经存在该值，则意味着我们有一个f1(e1) == f2(e2)的情况。我们只是不知道e1 是什么。但是，由于我们将其作为对应的键值对缓存在字典中，因此我们通过从键f1下的字典中获取值来获得e1。我们知道f1，因为f1 == f2(e2)。所以： d[f2(e2)] == e1。

备注：

  • 这应该非常快，因为f1只对l1的每个元素应用一次，而f2只对f2的每个元素应用一次。
  • 在提供的实际代码中，f2(e2) 被计算了两次。我这样做是为了便于阅读，但我们可以轻松地将 f2(e2) 记住为一个变量。
  • 加速依赖于将函数值作为键存储在字典中，因此无需花费时间搜索匹配项。
  • 如果f1和f2是实函数（返回浮点数），它们仍然可以用作字典键：浮点值作为字典键
于 2021-09-12T18:05:07.003 回答