8

我有一个看起来像这样的列表理解：

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 的回答，因为他的代码最容易理解。但是，我仍然非常欢迎有关如何执行此任务的其他建议。

4

2 回答 2

2

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

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:]]]
于 2013-03-08T16:04:07.250 回答
1

您将数据预处理为 dict 的想法是一个很好的想法。开始：

from itertools import groupby
C = { (0,1): 'b', (2,0): 'c', (0,0): 'd' }

def my_groupby(seq, key):
    """
     >>> group_by(range(10), lambda x: 'mod=%d' % (x % 3))
     {'mod=2': [2, 5, 8], 'mod=0': [0, 3, 6, 9], 'mod=1': [1, 4, 7]}
    """
    groups = dict()
    for x in seq:
        y = key(x)
        groups.setdefault(y, []).append(x)
    return groups

def get_overlapping_items(C):
    prefixes = my_groupby(C.iteritems(), key = lambda (k,v): k[:-1])
    for k1, v1 in C.iteritems():
        prefix = k1[1:]
        for k2, v2 in prefixes.get(prefix, []):
            yield (k1, v1), (k2, v2)

for x in get_overlapping_items(C):
    print x     

(((2, 0), 'c'), ((0, 1), 'b'))
(((2, 0), 'c'), ((0, 0), 'd'))
(((0, 0), 'd'), ((0, 1), 'b'))
(((0, 0), 'd'), ((0, 0), 'd'))

顺便说一句，而不是：

itertools.product(*[C.items()]*2)

做：

itertools.product(C.items(), repeat=2)
于 2013-03-08T16:09:59.967 回答