13

リスト（配列）の要素を結合すると、文字列を連結するよりも数倍高速であることを明確に証明するさまざまな言語の例をいくつか見てきました。残念ながら、なぜ説明が見つかりませんでしたか？両方の操作で機能する内部アルゴリズムと、一方が他方よりも速い理由を誰かが説明できますか?

これが私が意味することのpythonの例です：

# This is slow
x = 'a'
x += 'b'
...
x += 'z'

# This is fast
x = ['a', 'b', ... 'z']
x = ''.join(x)

よろしくお願いします）

4

7 に答える 7

15

結合関数のコードは、連結を要求されているすべての文字列とそれらの文字列の大きさを事前に知っているため、操作を開始する前に最終的な文字列の長さを計算できます。したがって、最終的な文字列にメモリを 1 回割り当てるだけで、各ソース文字列 (および区切り文字) をメモリ内の正しい場所に配置できます。

一方、文字列に対する単一の += 操作は、2 つの文字列の連結である最終的な文字列に十分なメモリを単純に割り当てる以外に選択肢はありません。後続の += は同じことを行う必要があり、次の += で破棄されるメモリを割り当てます。増え続ける文字列がメモリ内のある場所から別の場所にコピーされるたびに。

于 2010-02-24T09:52:31.023 に答える
14

その理由は、Python (および他の多くの言語) の文字列は不変オブジェクトであるためです。つまり、一度作成すると、変更することはできません。代わりに、文字列を連結すると、実際には、連結される 2 つの小さい文字列の内容で構成される新しい文字列が作成され、古い文字列が新しい文字列に置き換えられます。

文字列の作成には一定の時間がかかるため (メモリの割り当て、文字列の内容のそのメモリへのコピーなど)、多くの文字列を作成すると、単一の文字列を作成するよりも時間がかかります。N回の連結を行うには、その過程でN 個の新しい文字列を作成する必要があります。join()一方、単一の文字列 (最終結果) を作成するだけでよいため、はるかに高速に動作します。

于 2010-02-24T09:51:52.333 に答える
3

これは、文字列の連結にメモリのチャンクをどんどん大きくする必要があるためです。

x = 'a' # String of size 1 allocated
x += 'b' # String of size 2 allocated, x copied, and 'b' added. Old x discarded
x += 'b' # String of size 3 allocated, x copied, and 'c' added. Old x discarded
x += 'b' # String of size 4 allocated, x copied, and 'd' added. Old x discarded
x += 'b' # String of size 5 allocated, x copied, and 'e' added. Old x discarded

つまり、大規模な割り当てとコピーを実行した後、向きを変えてそれらを破棄します。非常に無駄です。

x = ['a', 'b', ..., 'z'] # 26 small allocations
x = ''.join(x) # A single, large allocation
于 2010-02-24T09:51:00.383 に答える
3

Python 文字列結合のパフォーマンスと、それを非常によく説明している特定の anwser を参照してください。

アドバイスは、多くの文字列を連結することです。

s = s1 + s2 + ... + sn を計算するには、

1) + を使用します。新しい文字列 s1+s2 が作成され、次に新しい文字列 s1+s2+s3 が作成されます...など、多くのメモリ割り当てとコピー操作が必要です。実際、s1 は n-1 回コピーされ、s2 は n-2 回コピーされ、... などです。

2) "".join([s1,s2,...,sn]) を使用します。連結は 1 回のパスで行われ、文字列内の各文字は 1 回だけコピーされます。

于 2010-02-24T09:53:54.780 に答える
1

他の回答は基本的にそれをカバーしていますが、さらに詳細が必要な場合は、ジョエル・スポルスキーが「画家のアルゴリズムのシュレミエル」について説明している記事があります。これは非常に関連性が高く、この種の低レベルの実装の詳細を理解する理由をうまく説明しています。 Pythonのような高級言語で作業している場合でも、これは依然として非常に重要です。

于 2010-02-24T15:23:53.777 に答える
0

まあ、これは言語に大きく依存しますが、一般的には、1つの大きな操作が多くの小さな操作よりも高速であるという考えがあります。2番目の例では、結合は結合する必要のあるすべての要素を認識しているため、必要なリソースを割り当てて文字を入れることができます。最初の例の連結では、すべてのステップでリソースを再割り当てする必要があります（最悪の場合）。

于 2010-02-24T09:50:35.583 に答える
0

join の内部構造はわかりませんが、最初のバージョンでは += 演算子を呼び出すたびに新しい文字列を作成します。文字列は不変であるため、毎回新しいメモリが割り当てられ、コピーが作成されます。

現在、結合 (文字列メソッド) は、事前にサイズを計算できるため、単一の割り当てしか実行できませんでした。

于 2010-02-24T09:51:43.100 に答える