我有一个如下所示的列表推导式:
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 的回答，因为他的代码最容易理解。但是，我仍然非常欢迎有关如何执行此任务的其他建议。
最佳答案
您实际上是在正确的轨道上，使用字典来存储键的所有前缀。但是，请记住(据我了解这个问题)如果重叠小于 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:]]]
关于python - 获取字典中与同一字典中其他键重叠的所有键，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15292570/