Pythonは可変引数連結演算子を実装

Question

明確化：彼らは考慮にネストしたリストを取ることはありませんので、

私はちょうど下の私の定義とコードを実現は、間違っているかもしれません。 concatenateの最終的な結果は、リストではないオブジェクトか、リストではない1つ以上のオブジェクトのリスト（ネストされたリストはありません）のいずれかになりたいと本当に思います。そして、空のリストはオブジェクトEmptyになるはずです。

---

しかし、ユーザーが、私はdenestedするためにそれらを必要とするような場合には、ネストされたリストからなる入力を提供することが可能です。これについて明確でないことに対する謝罪。

私は特定の型のオブジェクトを持っています（これも値としてEmptyを持つことができます）。そして、次の公理を満たすこれらのオブジェクトに対してバイナリ連結演算子を持っています（ここで[A、B]はAとB ）：

concatenate2(Empty, A) = concatenate2(A, Empty) = A 
concatenate2(A, [B, C]) = concatenate2([A, B], C) = [A, B, C] 
concatenate2(A, B) = [A, B] (if A, B do not match any of the previous cases). 

今、私はまた、任意に、多くの用語の連結を持つようにしたい：私はリストのコピー操作の数を最小限に抑える方法で、これらの演算子を実装したいと思います

concatenate([]) = Empty 
concatenate([A]) = A 
concatenate([A, B]) = concatenate2(A, B) 
concatenate([A, B, ...]) = concatenate([concatenate2(A, B), ...]) 

が、私はこのベストを行う方法がわかりませんPythonで。

def concatenate2(A, B): 
    if A == Empty: 
     return B 

    if B == Empty: 
     return A 

    if type(A) == list: 
     return concatenate(A + [B]) 

    if type(B) == list: 
     return concatenate([A] + B) 

    return [A, B] 

def concatenate(terms): 
    if terms == []: 
     return Empty 

    if len(terms) == 1: 
     return terms[0] 

    if len(terms) == 2: 
     return concatenate2(terms[0], terms[1]) 

    return concatenate(concatenate2(terms[0], terms[1]) + terms[2:]) 

これはかなりいいと明確に見えますが、私はそれがパフォーマンスとメモリ使用量の観点に立ってどれだけ知っていない：

私の現在の考えは、このような何かをすることでした。私はそれが各[...] + [...]操作の間にあまりにも多くのリストコピーを引き起こすかもしれないと心配です。

これらの操作を実装するより良い方法はありますか？

最終的には、実際にはconcatenate操作のみが必要であることに注意してください。 concatenate2演算子を使用して素敵な再帰的な定義を与えましたが、誰かがそれを使用しないより効率的なソリューションを提案できるなら、私もそれを受け入れます。

Answer 1

を単に可変長引数ではなく、また混合型シグネチャを持っています。

concatenate_all(*args)関数を定義して、そこにスローされたすべての引数を連結するとします。

あなたがconcatenate_allのすべての引数が配列であることに同意た場合、我々はそれらのうちの単一の配列を形成することができ、そして倍左にそれをconcatenateで：

import itertools 

# Pretend that concatenate_all is [[A]] -> [A] 
def concatenate_all(*seqs): 
    all_seqs = itertools.chain(*seqs) 
    return reduce(lambda acc, x: concatenate(acc, x), all_seqs, EMPTY) 

我々は一部のことを前提としていた場合は、 argsはスカラーであり、いくつかはリストであり、スカラーをリストにラップして同じトリックを使用することができます。

def concatenate_all(*scalars_or_seqs): 
    def to_list(x): 
     # TODO: should make it work with generators, too. 
     return x if isinstance(x, list) else [x] 

    # We use itertools to avoid creating intermediate lists. 
    all_items = itertools.chain(*scalars_or_seqs) 
    all_lists = itertools.imap(to_list, all_items) 
    return reduce(lambda acc, x: concatenate(acc, x), all_lists, EMPTY) 

我々はargsのいくつかは、我々がフラット化する必要がもネストされたリストであると仮定した場合、あなたもそれを処理するために上記のコードを更新することができます。

でも、その引数については、の関数を作成することに警告したいと思います。余分なマジックは最初はlook neatであるかもしれませんが、実際には、特に静的チェックがほぼゼロのPythonなどの非常に動的な言語を使用すると、実際には推論が難しくなります。ラッピングとフラット化を呼び出し側にプッシュし、明示的にする方が良いです。

Answer 2

繰り返し結合には+を使用するのが理想的ではありません。合成長さに関して2次の最悪の時間複雑度をもたらす各バイナリ連結に対して中間のオブジェクトを作成し続けます。より単純でより良いアプローチは、線形の複雑さを持つネストされた理解である。 これはまた、任意の数の引数解凍する*演算子を使用しています。あなたが望むように見える何

def concatenate(*terms): 
    return [x for t in terms for x in (t if isinstance(t, list) else [t])] 

>>> concatenate([3, 4], 5, [], 7, [1]) 
[3, 4, 5, 7, 1] 

>>> concatenate() 
[]