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

Question

我最近试图用 Python 解决一些任务，我发现解决方案似乎具有 O(n log n) 的复杂性，但我认为它对于某些输入来说效率很低(例如第一个参数是 0 和 pairs 是很长的零列表)。

它还有三层for 循环。我相信它可以优化，但目前我无法对其进行更多优化，我可能只是遗漏了一些明显的东西；)

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

Given list of integers (values), the function needs to return the number of indexes' pairs that meet the following criteria:

• lets assume single index pair is a tuple like (index1, index2),
• then values[index1] == complementary_diff - values[index2] is true,

Example: If given a list like [1, 3, -4, 0, -3, 5] as values and 1 as complementary_diff, the function should return 4 (which is the length of the following list of indexes' pairs: [(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 block 。它也比使用 collections.defaultdict(list) 更快。 (我用 ipython %timeit 对此进行了测试。)
• 原始代码访问每个解决方案两次。对于每个 pos_value在 value_key 中，有一个唯一的 sym_value 与位置值。 sym_value 也有解决办法值键。但是当我们遍历 value_key 中的键时，pos_value最终被赋值给sym_value的值，这使代码重复它已经完成的计算。所以你可以如果你能阻止 pos_value 等于旧的 sym_value。我用 seen = set() 实现了它以保持看到的 sym_value 的轨迹。

• 代码只关心 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