8

次のようなリスト内包表記があります。

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

C任意の整数のタプルであるキーを持つ dict です。すべてのタプルは同じ長さです。最悪の場合、すべての組み合わせを新しいリストに含める必要があります。これは非常に頻繁に発生する可能性があります。

例として、次のような辞書があります。

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 短い長さのオーバーラップのみが必要です。したがって(1,2,3,4)、 とは重複しません(3,4,5,6)。また、タプルの最初または最後の要素を削除すると、最終的に不明確なタプルになる可能性があることに注意してください。これらすべてを他のすべての要素と比較する必要があります。この最後の点は、最初の例では強調されていません。

私のコード実行時間の大部分は、このリストの理解に費やされています。のすべての要素が常に必要なcartので、代わりにジェネレーターを使用してもスピードアップはないようです。

私の質問は次のとおりです。これを行うより速い方法はありますか?

私が考えていたのは、次のような 2 つの新しい辞書を作成しようとすることでした。

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()]

そして、どういうわけか、リストの要素のすべての組み合わせをfor allaa[i]のリストとマージしますが、このアイデアに頭を悩ませることもできません。bb[i]i

アップデート

tobias_k と shx2 によって追加されたソリューションはどちらも、元のコードよりも複雑です (私が知る限り)。私のコードは O(n^2) ですが、他の 2 つのソリューションは O(n) です。ただし、私の問題のサイズと構成では、3 つのソリューションすべてが多かれ少なかれ同時に実行されているようです。これは、関数呼び出しに関連するオーバーヘッドと、使用しているデータの性質の組み合わせに関係していると思います。特に、キーの実際の構成だけでなく、異なるキーの数も大きな影響を与えているようです。後者は、完全にランダムなキーの場合、コードの実行がはるかに遅くなるためです。tobias_k の回答を受け入れたのは、彼のコードが最も理解しやすいためです。ただし、このタスクの実行方法に関する他の提案を大歓迎します。

4

2 に答える 2

2

あなたは実際に正しい方向に進んでおり、辞書を使用してキーのすべてのプレフィックスを保存していました。ただし、（質問を理解している限り）オーバーラップがキーよりも小さい len-1場合、2つのキーもオーバーラップする可能性があることに注意してください。たとえば、キー(1,2,3,4)も(3,4,5,6)オーバーラップします。したがって、キーのすべてのプレフィックスを保持するマップを作成する必要があります。（これについて間違えた場合は、2つの内側の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である必要があります。同じプレフィックスを持つキーが非常に多い場合は、スペースの複雑さ（マップのサイズ）をとの間にする必要があります。nkprefixesn*kn^2*k

注：上記の回答は、オーバーラップ領域が任意の長さになる可能性がある、より一般的なケースに対するものです。元のタプルよりも1つ短いオーバーラップのみを考慮する単純なケースでは、以下で十分であり、例で説明されている結果が得られます。

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

データを辞書に前処理するというあなたのアイデアは良いものでした。ここに行きます：

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 に答える