6

私は持っています：

>>> As = [1, 2, 5, 6]
>>> Bs = [2, 3, 4, 5]

私は以下のようなものが欲しいですzip_fn：

>>> Rs = zip_fn(As, Bs, cmp)
>>> Rs
[(1, None), (2, 2), (None, 3), (None, 4), (5, 5), (6, None)]

つまり、2つの任意のシーケンスAsとが与えられた場合、満たす選択肢がペアになって独自のタプルになるようBsにタプルのリストを作成したいのですが、対応するものがある場合とない場合はそれぞれととして出力されます。Rscmp(a, b) == 0(a, b)AsBs(a, None)(None, b)

いくつかのポイント：

  • As重複がないので、重複については心配していBsません。
  • Rs同じシーケンスを生成するイテレータにすることができます。
  • の順序Rsは重要ではありません。

単純な事前ソートループを使用して機能要件を満たすものをすでに実装しましたが、約30行です。itertoolsビルトインまたはesqueライブラリをより有効に活用して、コードを短くし、（Cネイティブ）実行を高速化するものを探しています。

編集：

私はこれをもっと明確にすべきだった。上記の例では簡潔にするために単純な数値のリストを使用しましたが、実際に使用している要素はタプルでありcmp、タプルの一部のみが等しいかどうかをテストします。要素をレコードであり、キーフィールドcmpに一致するものと考える方が簡単な場合があります。要素をクラスにラップしてキーでハッシュ可能にすることもできますが、そのような設定は他には必要ないため、これを必要とするソリューションでは、追加のコードと実行時のオーバーヘッドとしてこれを取得します。

上記のいくつかへの追加のポイントとしてこれを要約します：

  • cmpこれは基本的な平等のテストではないため、比較に使用することが重要です。
  • 結果[(a, b)]では、は、の要素の1つと同じインスタンスであり、の要素の1つの同じインスタンスでaある必要があります（そうでない場合）。AsbBsNone
  • 内の要素Asとハッシュ可能でBsはありません。
4

5 に答える 5

2

私はこれがあなたがすでに持っているものに似ていると思います：

from collections import deque

def pairs(xs, ys):
    xs = deque(sorted(xs))
    ys = deque(sorted(ys))

    while xs and ys:
        c = cmp(xs[0], ys[0])
        if c == 0:
            yield xs.popleft(), ys.popleft()
        elif c < 0:
            yield xs.popleft(), None
        else: # c > 0:
            yield None, ys.popleft()

    for x in xs: yield x, None
    for y in ys: yield None, y


xs = [1, 2, 5, 6]
ys = [2, 3, 4, 5]        
print list(pairs(xs, ys))
# [(1, None), (2, 2), (None, 3), (None, 4), (5, 5), (6, None)]
于 2012-07-11T06:22:57.787 に答える
1

これはどう：

As = set([1, 2, 5, 6])
Bs = set([2, 3, 4, 5])
values = [(a, a) if a in Bs else (a, None) for a in As] + [(None, b) for b in Bs if b not in As]
>>> values
[(1, None), (2, 2), (5, 5), (6, None), (None, 3), (None, 4)]

またはセットの使用：

>>> values = [(a, a) for a in As.intersection(Bs)] + [(a, None) for a in As - Bs] + [(None, b) for b in Bs - As]
>>> values
[(2, 2), (5, 5), (1, None), (6, None), (None, 3), (None, 4)]
>>>

AsまたはBの重複はないので、心配していません。

したがって、セットを作成すると、ほぼ一定のルックアップ時間が得られます。

Rsの順序は重要ではありません。

したがって、AをチェックしてからBをチェックするだけです:)

これが正しいかどうかはわかりません。これは頭のてっぺんからです。問題がある場合は、お詫び申し上げます。

更新
これはもう少し難しいです。ハッシュ化できないため、基本的にO（n ** 2）でスタックしています。申し訳ありません:(

できるだけ最適化するように心がけました。

As = [1, 2, 5, 6]
Bs = [2, 3, 4, 5]

indicies_a, indicies_b, values = [], [], []
for index_a, a in enumerate(As):
    for index_b, b in enumerate(Bs):
        if cmp(a, b) == 0:
            values.append((a, b))
            indicies_a.append(index_a) 
            indicies_b.append(index_b)

values += [(As[index], None) for index in set(range(len(As))) - set(indicies_a)] + [(None, Bs[index]) for index in set(range(len(Bs))) - set(indicies_b)]

>>> values
[(2, 2), (5, 5), (1, None), (6, None), (None, 3), (None, 4)]
>>>

申し訳ありませんが、これ以上簡潔なバージョンを思い付くことができませんでした。ベストをできるだけ速くするために最善を尽くしました。

于 2012-07-11T05:31:46.627 に答える
1

これは操作を考慮していないことを私は理解していますcmp()が、うまくいけば少し役立つでしょう。

>>> As = [1, 2, 5, 6]
>>> Bs = [2, 3, 4, 5]
>>> result = []
>>> for n in set(As + Bs):
...     result.append((n if n in As else None, n if n in Bs else None))
...
>>> result
[(1, None), (2, 2), (None, 3), (None, 4), (5, 5), (6, None)]
>>>

リストコンプと同じもの：

>>> result = [ (n if n in As else None, n if n in Bs else None) for n in set(As + Bs)]
>>> result
[(1, None), (2, 2), (None, 3), (None, 4), (5, 5), (6, None)]
>>>
于 2012-07-11T05:37:30.480 に答える
1 
([(i,j) for i in As for j in Bs if cmp(i,j) == 0] +
[(i,None) for i in As if all(cmp(i,j) !=0 for j in Bs)] +
[(None, j) for j in Bs if all(cmp(i,j) !=0 for i in As)])

ただし、説明によれば、要素が他の要素よりも大きいかどうかがわからないため、時間計算量はn^2になります。

于 2012-07-11T06:50:01.120 に答える
0

@ thg435の答えと使用法（編集：@EOLが指摘したように変更）のようなものを使用することにしました。これにより、元々持っていたコードの多くを削減できました。deque list

私はこれらの理由でこれを選びました：

  • 時間計算量の計算は単純で、予測がかなり簡単です。
  • インターフェイスを変更する必要はありませんでした。
  • コードの量と予想される実行時の効率の間にはバランスが取れていると感じました。

実装は次のとおりです。

def izip_pairs(xs, ys, cmp):
    xs = list(reversed(sorted(xs, cmp)))
    ys = list(reversed(sorted(ys, cmp)))

    while xs or ys:
        delta = ((not xs) - (not ys)) or cmp(xs[-1], ys[-1])

        x = xs.pop() if delta <= 0 else None
        y = ys.pop() if delta >= 0 else None
        yield x, y

比較のために：

全員のセットベースの回答に触発され、比較のために、ハッシュルックアップベースのソリューションに対応して実装するようにインターフェイスを変更しました。

def izip_keys(xs, ys, key):
    xs = {key(x): x for x in xs}
    ys = {key(y): y for y in ys}

    for k in set(xs.keys() + ys.keys()):
        yield xs.get(k, None), ys.get(k, None)

時差：

以下の結果に関する私の結論は、ソートされたリストでのループは、要素の数が多いほどスケーリングがはるかに優れているのに対し、ハッシュルックアップは小さなNに対してのみ高速であるということです。

>>> xs = range(100, 200)
>>> ys = range(150, 250)
>>> xs = map(lambda n: tuple(range(n, n + 10)), xs)
>>> ys = map(lambda n: tuple(range(n, n + 10)), ys)

>>> def profile_pairing():
...     list(izip_pairs(xs, ys, lambda x, y: cmp(x[:4], y[:4])))
...
>>> def profile_keying():
...     list(izip_keys(xs, ys, lambda v: v[:4]))
...

>>> from timeit import Timer
>>> Timer(profile_pairing).timeit(1000)
0.575916051864624
>>> Timer(profile_keying).timeit(1000)
0.39961695671081543

>>> xs = map(lambda n: tuple(range(n, n + 10)), range(1000, 2000))
>>> ys = map(lambda n: tuple(range(n, n + 10)), range(1500, 2500))
>>> Timer(profile_pairing).timeit(100)
0.5289111137390137
>>> Timer(profile_keying).timeit(100)
0.4951910972595215

>>> xs = map(lambda n: tuple(range(n, n + 10)), range(10000, 20000))
>>> ys = map(lambda n: tuple(range(n, n + 10)), range(15000, 25000))
>>> Timer(profile_pairing).timeit(10)
0.6034290790557861
>>> Timer(profile_keying).timeit(10)
0.9461970329284668

>>> xs = map(lambda n: tuple(range(n, n + 10)), range(100000, 200000))
>>> ys = map(lambda n: tuple(range(n, n + 10)), range(150000, 250000))
>>> Timer(profile_pairing).timeit(1)
0.6421248912811279
>>> Timer(profile_keying).timeit(1)
1.253270149230957

（注：deque代わりに*を使用すると、list(reverse(...))すべてのケースで1％高速になりました。*いくつかの編集を参照してください）

于 2012-07-11T08:35:17.437 に答える