python - 获取字典中与同一字典中其他键重叠的所有键

Question

我有一个如下所示的列表推导式:

cart = [ ((p,pp),(q,qq)) for ((p,pp),(q,qq))\
         in itertools.product(C.items(), repeat=2)\
         if p[1:] == q[:-1] ]

C 是一个字典，其键是任意整数的元组。所有元组的长度都相同。最坏的情况是所有组合都应该包含在新列表中。这种情况经常发生。

举个例子，我有一个这样的字典:

C = { (0,1):'b',
      (2,0):'c',
      (0,0):'d' }

我希望结果是:

cart = [ (((2, 0), 'c'), ((0, 1), 'b'))
         (((2, 0), 'c'), ((0, 0), 'd'))
         (((0, 0), 'd'), ((0, 1), 'b'))
         (((0, 0), 'd'), ((0, 0), 'd')) ]

因此，通过重叠，我指的是元组 (1,2,3,4) 和 (2,3,4,5) 有重叠部分 (2,3,4)。重叠部分必须位于元组的“边缘”。我只想要长度比元组长度短一个的重叠。因此 (1,2,3,4) 不与 (3,4,5,6) 重叠。另请注意，当删除元组的第一个或最后一个元素时，我们可能会得到非不同的元组，所有这些元组都必须与所有其他元素进行比较。 最后一点在我的第一个例子中没有强调。

我的代码执行时间的大部分时间花在了这个列表理解上。我总是需要 cart 的所有元素，因此在使用生成器时似乎没有加速。

我的问题是:是否有更快的方法？

我的一个想法是我可以尝试创建两个这样的新词典:

aa = defaultdict(list)
bb = defaultdict(list)
[aa[p[1:]].append(p) for p in C.keys()]
[bb[p[:-1]].append(p) for p in C.keys()]

并以某种方式将 aa[i] 中列表元素的所有组合与 bb[i] 中的列表元素合并为所有 i , 但我似乎也无法理解这个想法。

更新

tobias_k 和 shx2 添加的解决方案都比我的原始代码(据我所知)具有更好的复杂性。我的代码是 O(n^2) 而其他两个解决方案是 O(n)。然而，对于我的问题大小和组成，所有三个解决方案似乎或多或少同时运行。我想这与函数调用相关的开销以及我正在处理的数据的性质有关。特别是不同键的数量，以及键的实际组成，似乎有很大的影响。我知道后者是因为对于完全随机的 key ，代码运行速度要慢得多。我接受了 tobias_k 的回答，因为他的代码最容易理解。但是，我仍然非常欢迎有关如何执行此任务的其他建议。

Answer 1

您实际上是在正确的轨道上，使用字典来存储键的所有前缀。但是，请记住(据我了解这个问题)如果重叠小于 len-1，两个键也可以重叠，例如键 (1,2,3,4) 和 (3,4,5,6) 也会重叠。因此，我们必须创建一个包含所有键前缀的映射。 (如果我对此有误，只需删除两个内部 for 循环。)一旦我们有了这个映射，我们就可以再次遍历所有键，并检查它们是否有任何后缀是 prefixes 映射中的匹配键。 (更新:因为键可以重叠 w.r.t. 不止一个前缀/后缀，我们将重叠对存储在一个集合中。)

def get_overlap(keys):
    # create map: prefix -> set(keys with that prefix)
    prefixes = defaultdict(set)
    for key in keys:
        for prefix in [key[:i] for i in range(len(key))]:
            prefixes[prefix].add(key)
    # get keys with matching prefixes for all suffixes
    overlap = set()
    for key in keys:
        for suffix in [key[i:] for i in range(len(key))]:
            overlap.update([(key, other) for other in prefixes[suffix]
                                                      if other != key])
    return overlap

(请注意，为简单起见，我只关心字典中的键，而不关心值。扩展它以返回值，或者将其作为后处理步骤执行，应该是微不足道的。)

整体运行时间应该只有 2*n*k，n 是键的数量，k 是键的长度。空间复杂度(prefixes映射的大小)应该在n*k和n^2*k之间，如果key非常多具有相同的前缀。

注意:以上答案适用于重叠区域可以有任意长度的更一般情况。对于您认为仅重叠一个比原始元组短的更简单的情况，以下应该足够并产生示例中描述的结果:

def get_overlap_simple(keys):
    prefixes = defaultdict(list)
    for key in keys:
        prefixes[key[:-1]].append(key)
    return [(key, other) for key in keys for other in prefixes[key[1:]]]