获取与同一个词典中的其他键重叠的词典中的所有键

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).然而,对于我的问题大小和组成,所有三种解决方案似乎或多或少同时运行.我想这与函数调用相关的开销和我正在使用的数据的性质有关.特别是不同键的数量以及键的实际组成似乎具有很大的影响.后者我知道,因为完全随机密钥的代码运行速度要慢得多.我接受了tobias_k的答案,因为他的代码是最容易理解的.但是,我仍然非常欢迎有关如何执行此任务的其他建议.

Answer 1

您实际上走在正确的轨道上，使用字典来存储键的所有前缀。但是，请记住（据我理解这个问题）如果重叠小于， len-1两个键也可以重叠，例如键(1,2,3,4)和(3,4,5,6)也会重叠。因此，我们必须创建一个包含所有键前缀的映射。（如果我弄错了，只需删除两个内部for循环即可。）一旦我们有了这个映射，我们就可以再次迭代所有键，并检查它们的任何后缀在映射中是否有匹配的键prefixes。（更新：由于键可以与多个前缀/后缀重叠，因此我们将重叠对存储在一组中。）

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

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

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:]]]