扁平嵌套循环/降低复杂性 - 互补对计数算法

Question

我最近试图解决Python中的一些任务,我发现解决方案似乎具有O(n log n)的复杂性,但我认为它对于某些输入(例如第一个参数存在0且pairs非常长)非常低效零列表).

它还有三个级别的for循环.我相信它可以进行优化,但目前我无法对其进行优化,我可能只是遗漏了一些明显的东西;)

所以,基本上,问题如下:

给定整数列表(values),函数需要返回满足以下条件的索引对的数量:

• 假设单个索引对是一个元组(index1, index2),
• 那values[index1] == complementary_diff - values[index2]是真的,

示例:如果给出类似[1, 3, -4, 0, -3, 5]as values和1as 的列表complementary_diff,则函数应该返回4(这是以下索引列表对的长度:) [(0, 3), (2, 5), (3, 0), (5, 2)].

这就是我到目前为止,它应该在大多数情况下完美地工作,但是 - 正如我所说的 - 在某些情况下它可以非常缓慢地运行,尽管它的复杂度近似为O(n log n)(它看起来像悲观的复杂性是O(n ^ 2)).

def complementary_pairs_number (complementary_diff, values):
    value_key = {} # dictionary storing indexes indexed by values
    for index, item in enumerate(values):
        try:
            value_key[item].append(index)
        except (KeyError,): # the item has not been found in value_key's keys
            value_key[item] = [index]
    key_pairs = set() # key pairs are unique by nature
    for pos_value in value_key: # iterate through keys of value_key dictionary
        sym_value = complementary_diff - pos_value
        if sym_value in value_key: # checks if the symmetric value has been found
            for i1 in value_key[pos_value]: # iterate through pos_values' indexes
                for i2 in value_key[sym_value]: # as above, through sym_values
                    # add indexes' pairs or ignore if already added to the set
                    key_pairs.add((i1, i2))
                    key_pairs.add((i2, i1))
    return len(key_pairs)

对于给定的示例,它的行为类似于:

>>> complementary_pairs_number(1, [1, 3, -4, 0, -3, 5])
4

如果您看到代码如何"扁平化"或"简化",请告诉我.

我不确定是否只是检查complementary_diff == 0等是最好的方法 - 如果您认为是,请告诉我.

编辑:我已经纠正了这个例子(谢谢,unutbu!).

Answer 1

我认为这将复杂性提高到O(n)：

• value_key.setdefault(item,[]).append(index)比使用块更快try..except。它也比使用collections.defaultdict(list). （我用 ipython %timeit 测试了这一点。）
• 原始代码访问每个解决方案两次。对于每个pos_value in value_key，都有一个唯一的sym_value关联 pos_value。sym_value也 有解决方案value_key。但是当我们迭代 中的键时value_key， pos_value最终会被分配给 的值sym_value，这使得代码重复已经完成的计算。pos_value因此，如果您可以停止与旧的相等，您可以将工作减少一半sym_value。我用 a 来实现它seen = set()来跟踪已看到的sym_values。

• 代码只关心len(key_pairs)，而不关心它们key_pairs本身。因此， set我们可以简单地跟踪计数（使用 ），而不是跟踪对（使用num_pairs）。所以我们可以将两个内部 for 循环替换为

  num_pairs += 2*len(value_key[pos_value])*len(value_key[sym_value])
  

  或“唯一对角线”情况下的一半，pos_value == sym_value。

def complementary_pairs_number(complementary_diff, values):
    value_key = {} # dictionary storing indexes indexed by values
    for index, item in enumerate(values):
        value_key.setdefault(item,[]).append(index)
    # print(value_key)
    num_pairs = 0
    seen = set()
    for pos_value in value_key: 
        if pos_value in seen: continue
        sym_value = complementary_diff - pos_value
        seen.add(sym_value)
        if sym_value in value_key: 
            # print(pos_value, sym_value, value_key[pos_value],value_key[sym_value])
            n = len(value_key[pos_value])*len(value_key[sym_value])
            if pos_value == sym_value:
                num_pairs += n
            else:
                num_pairs += 2*n
    return num_pairs