使用Map迭代器测试集合交集

Question

我正试图编写一个函数来寻找弱Sidon序列（一个序列（a_I），其中a_I+a_j对于所有I<j） 任意长度，从1开始。

这就是我目前所拥有的：

def weakSidon(sequence_length):
    """Finds a weak Sidon sequence (a sequence (a_i) of integers where a_i + a_j for i < j are all unique) of the necessary length."""
    sequence = [1]
    sums = []
    while len(sequence) < sequence_length:
        test_integer = sequence[-1] + 1
        test_sums = list(map(lambda x: test_integer + x, sequence))
        while any(x in list(test_sums) for x in sums):
            test_integer = test_integer + 1
            test_sums = list(map(lambda x: test_integer + x, sequence))
        sequence.append(test_integer)
        sums = sums + test_sums
    return sequence

这是可行的（而且，正如我在完成这项工作后意识到的那样，这只是一种在没有第一个元素的情况下生成斐波那契序列的愚蠢方式），但将映射迭代器转换为列表，然后在下一行的生成器中立即对其进行迭代似乎很愚蠢，如果可能的话，我想知道如何在未来避免这种混乱。

当然，对于简化的任何其他一般性建议（特别是对于重复的test_sums分配）都是值得赞赏的。

Answer 1

您的代码有两个主要问题。

第一种是，每次测试总和是否在test_sums列表中时，都会调用list。all(x in list(test_sums) for x in sums)多次调用list，由于test_sums已经是一个列表，这只是浪费了周期。

第二个问题是，列表成员身份测试通常很慢，即使您没有首先复制列表。在set中测试成员资格要快得多，所以您可能应该在这里使用一个。

如果您将sums设为一个集合，并更改在all调用中迭代的序列，以利用快速set.__contain__测试，您将得到如下结果：

def weakSidon(sequence_length):
    """Finds a weak Sidon sequence (a sequence (a_i) of integers where
       a_i + a_j for i < j are all unique) of the necessary length."""
    sequence = [1]
    sums = set()                                   # start with an empty set
    while len(sequence) < sequence_length:
        test_integer = sequence[-1] + 1
        test_sums = list(map(lambda x: test_integer + x, sequence))
        while any(x in sums for x in test_sums):   # testing set membership is O(1)
            test_integer = test_integer + 1
            test_sums = list(map(lambda x: test_integer + x, sequence))
        sequence.append(test_integer)
        sums.update(test_sums)                     # update set items
    return sequence

您无法摆脱一个list调用来将map生成器转换为实际列表，因为如果没有冲突，则需要在update步骤中再次访问test_sums值。

Answer 2

为某个迭代器a计算x in a将消耗部分或全部a。并且评估CCD_ 18将消耗全部CCD_。在生成器(x in list(test_sums) for x in sums)中，表达式x in list(test_sums)对sums中的每个元素求值一次。

因此，如果你没有立即列出map的结果，那么你的检查(x in list(test_sums) for x in sums)就不会像预期的那样工作——当稍后测试sums中的元素时，test_sums已经被消耗，表达式list(test_sums)就是[]。我发现在口译员那里查一个这种情况的简单例子很有帮助。

Python实际上有一个内置的集合数据类型（链接）。确定集合中的成员身份是一个恒定的时间操作，所以如果你要进行大量的成员身份检查（比如这里），那么使用它们是个好主意。但我们实际上可以去掉any(x in a for x in b)构造（尽管它很漂亮），直接使用，因为Python也定义了集合上的交集和并集。如果a和b是两个集合，则a | b是它们的并集，a & b是它们的交集。

因此，使用集合的代码是：

def weakSidon(sequence_length):
    sequence = [1]
    sums = set()
    while len(sequence) < sequence_length:
        test_integer = sequence[-1] + 1
        test_sums = {test_integer + n for n in sequence}
        while test_sums & sums:
            test_integer += 1
            test_sums = {test_integer + n for n in sequence}
        sequence.append(test_integer)
        sums |= test_sums
    return sequence

（|=运算符对|的作用就像+=对+的作用一样）。

我以前从未听说过Sidon序列，但我认为Fibonaccis是一个序列真的很有趣。