Python的PairSum函数与字典

我想写一个函数pairSum（数据，价值），其中如果列表“数据”包含两个distict数字的总和等于“价值”，该函数返回true。我用列表完成了这个，但是有没有更高效的方法可以使用字典编写这个函数？Python的PairSum函数与字典

2012-04-22 Jim West

也许你应该澄清一下列表是否有*对*号或只有*单*号。 – 2012-04-22 03:19:57

我原来的功能有个别的数字，我试图用字典来实现相同的基本功能。 – 2012-04-22 03:34:45

你可以尝试使用一套。

def pairSum(data, value): 
    s = set() 
    for i in data: 
    if (value - i) in s: 
     return True 
    else: 
     s.add(i) 
    else: 
    return False

来源

2012-04-22 03:13:22

不错！你的解决方案是O（n），我们实际上不需要在这里计算所有可能的组合。 – Akavall 2012-04-22 04:11:49

from itertools import combinations 

pairSum = lambda data, value: any(sum(i) == value for i in combinations(data, 2))

编辑佩德罗韦尔内克指出，在set()会员测试可能更有效：

pairSum = lambda data, value: value in set(sum(i) for i in combinations(data, 2))

进一步编辑 我把伊格纳西奥的建议，并测试了两种方法使用timeit。结果如下：

对于所有测试，测试的功能与我在原始答案（上面）中发布的功能相同。处决

timeit数为10,000

data = range(100)

Test Value Generator  Set

   1  0.02824  10.84905

  101  0.66934  10.77293

  197 11.07062  10.73978

所以得出的结论似乎是，发电机运行在平均水平，与这两个最坏的情况下倍对于设置和发电机大致相同。

来源

2012-04-22 03:18:17

any（）进行线性搜索，因此在set（sum（i）for i in combination（data，2））中做值可能更有效。 – 2012-04-22 03:36:46

@Pedro：生成一个集合仍然是线性的，所以你可以节省很少的东西。 – 2012-04-22 03:50:57

@PedroWerneck：嗯，我不确定。我认为这取决于'组合'的大小。 'any（sum（i）...'是一个生成器表达式，不需要在评估前计算所有的值。 – 2012-04-22 03:51:29

不是字典，但您可以构建所有组合并检查您的值是否在该集合中。

import itertools 

def pairSum(data, value): 
    return value in set(map(sum, itertools.combinations(data, 2)))

如果列表不包含零或负值，你可以保持仅比列表中的目标下的值，因为在列表中总结的价值相等或更高，以别的不匹配：

import itertools 

def pairSum(data, value): 
    data = [v for v in data if v < value] 
    return value in set(map(sum, itertools.combinations(data, 2)))

来源

2012-04-22 03:23:29

Python的PairSum函数与字典

回答

相关问题