4

http://jaynes.colorado.edu/PythonIdioms.htmlから

「文字列をリストとして構築し、最後に ''.join を使用します。join は、リストではなくセパレーターで呼び出される文字列メソッドです。空の文字列から呼び出すと、セパレーターなしでピースが連結されます。これは Python の癖であり、むしろ最初は驚く. これは重要です: + を使用した文字列の構築は、線形ではなく二次時間です! 1 つのイディオムを学ぶ場合は、このイディオムを学びます。

間違っています: 文字列内の s: 結果 += s

右: result = ''.join(strings)"

なぜこれが本当なのかわかりません。結合したい文字列がある場合、それらをリストに入れてから ''.join. それらをリストに入れるとオーバーヘッドが発生しませんか? 明確にするために...

Python コマンドライン:

>>> str1 = 'Not'
>>> str2 = 'Cool'
>>> str3 = ''.join([str1, ' ', str2]) #The more efficient way **A**
>>> print str3
Not Cool
>>> str3 = str1 + ' ' + str2 #The bad way **B**
>>> print str3
Not Cool

Aは本当に線形時間で、Bは二次時間ですか?

4

5 に答える 5

14

はい。選択した例では、非常に短い文字列が 2 つしかないため、重要性が明確ではないため、追加がおそらく高速になります。

しかし、Python で文字列を扱うたびにa + b、新しい割り当てが発生し、a と b のすべてのバイトが新しい文字列にコピーされます。多くの文字列を含むループでこれを行うと、これらのバイトを何度も何度もコピーする必要があり、コピーする必要がある量が長くなるたびに。これにより、2次動作が得られます。

一方、文字列のリストを作成しても、文字列の内容はコピーされません。参照がコピーされるだけです。これは信じられないほど高速で、線形時間で実行されます。次に、join メソッドは 1 回だけメモリ割り当てを行い、各文字列を正しい位置に 1 回だけコピーします。これも線形時間しかかかりません。

したがって、''.join多数の文字列を扱う可能性がある場合は、イディオムを使用してください。2 つの文字列だけでは問題ありません。

さらに説得力が必要な場合は、1,000 万文字の文字列を作成してみてください。

>>> chars = ['a'] * 10000000
>>> r = ''
>>> for c in chars: r += c
>>> print len(r)

と比べて：

>>> chars = ['a'] * 10000000
>>> r = ''.join(chars)
>>> print len(r)

最初の方法は約 10 秒かかります。2 番目は 1 秒未満です。

于 2009-12-28T02:27:02.483 に答える
6

繰り返される連結は、Schlemiel the Painter のアルゴリズムであるため、2 次です(一部の実装ではこれを最適化して 2 次ではなくなることに注意してください)。join文字列のリスト全体を取得し、必要なスペースを割り当て、連結を 1 回のパスで行うため、これを回避します。

于 2009-12-28T02:24:10.597 に答える
4

をコーディングするときs1 + s2、Python は新しい文字列オブジェクトを割り当て、 のすべての文字をそのオブジェクトにコピーs1し、その後にのすべての文字をコピーする必要がありs2ます。この些細な操作は二次時間コストを負担しません: コストはO(len(s1) + len(s2))(プラス割り当てのための定数ですが、big-O では計算されません;-) です。

ただし、あなたが与えている引用のコードを考慮してください: for s in strings: result += s.

ここでは、新しいものが追加されるたびに、以前のものはすべて、新しく割り当てられたスペースに最初にコピーする必要があります (文字列は不変であるため、新しい割り当てとコピーを行う必要があります)。長さ L の N 個の文字列があるとします。最初に L 文字をコピーし、2 回目に 2 * L、3 回目に 3 * L をコピーします...全体として、文字がコピーされます...ええ、N では 2 次です。sresultL * N * (N+1) / 2

他のいくつかのケースでは、N の値が十分に小さい場合、二次アルゴリズムは線形アルゴリズムよりも高速である可能性があります (乗数と定数固定コストがはるかに小さい可能性があるため)。ただし、ここではそうではありません。割り当てにはコストがかかるためです (メモリが断片化する可能性があるため、直接的にも間接的にも)。それに比べて、文字列をリストに蓄積するオーバーヘッドは本質的に無視できます。

于 2009-12-28T02:28:58.127 に答える
1

Joel はBack to Basicsでこれについて書いています。

于 2009-12-28T02:34:33.653 に答える
0

他の人と同じことを指しているかどうかは明らかではありません。この最適化は、長さNのMなど、多くの文字列がある場合に重要です。それで

あ 

x = ''.join(strings) # Takes M*N operations

B

x = ''
for s in strings:
    x = x + s  # Takes N + 2*N + ... + M*N operations

実装によって最適化されていない限り、はい、Aは全長で線形でありT = M*N、BはT*T / N常により悪く、ほぼ 2 次ですM >> N。

さて、実際に非常に直感的な理由は次のとおりです。「私はいくつかの文字列を持っています」と言うとき、これは通常、文字列を返すイテレータjoinがあると言って形式化できます。さて、これはまさにあなたが渡すものです"string".join()

于 2009-12-28T02:23:15.373 に答える